《半平面交的新算法及其实用价值》由会员分享,可在线阅读,更多相关《半平面交的新算法及其实用价值(10页珍藏版)》请在金锄头文库上搜索。
1、 欢迎阅读本文档,希望本文档能对您有所帮助!半平面交的新算法及其实用价值 感谢阅读本文档,希望本文档能对您有所帮助! Keywords: Half-plane, Intersection, Feasible Region, Algorithm, Polygon, PracticalAbstract主旨:半平面的交是当今学术界热烈讨论的问题之一,本文将介绍一个全新的O(nlogn)半平面交算法,强调它在实际运用中的价值,并且在某种程度上将复杂度下降至O(n)线性。最重要的是,我将介绍的算法非常便于实现.1 introduces what half-plane intersection is. 2
2、 prepares a linear algorithm for convex polygon intersection (abbr. CPI). Equipped with such knowledge, a common solution for HPI is briefly discussed in 3. Then, my new algorithm emerges in 4 detailedly. Not only as a conclusion of the whole paper, 5 also discuss its further usage practically and c
3、ompares it with the older algorithm described in 3.1什么是半平面交. 2凸多边形交预备知识. 3简要介绍旧D&C算法. 4揭开我的新算法S&I神秘面纱. 5总结和实际运用.Timestamps: Came up with it in April 2005; implemented partly in June 2005 The sub-problem of HPI appeared in USA Invitational Computing Olympiad contest.; problem set in July 2005 Set an
4、HPI problem in Peking University Online Judge, with brief introduction about the algorithm.; publicized as a post in USENET, November 6, 2005 URL: http:/ IntroductionA line in plane is usually represented as ax+by=c. Similarly, its inequality form ax+byc represents a half-plane (also named h-plane f
5、or short) as one side of this line. Notice that ax+byc and -ax-by-c show opposite h-planes unlike ax+by=c and -ax-by=-c. Half-Plane Intersection (abbr. HPI) considers the following problem:众所周知,直线常用ax+by=c表示,类似地半平面以ax+by()c为定义。Given n half-planes, aix+biyci (1in), you are to determine the set of all
6、 points that satisfying all the n inequations. 给定n个形如aix+biyci的半平面,找到所有满足它们的点所组成的点集As Figure iTwo examples of HPI. (b) gives an example of unbounded intersection area. describes, the feasible region, which is the intersection, forms a shape of convex hull but possibly unbounded. However, we shall ad
7、d four h-planes forming a rectangle, which is large enough to make sure the area after intersections finite. In the following sections, we suppose the feasible region is bounded with a finite area.合并后区域形如凸多边形,可能无界。此时增加4个半平面保证面积有限! . (a) (b) Each h-plane builds up at most one side of the convex polyg
8、on, hence, the convex region will be bounded by at most n edges. Pay attention the intersection sometimes yields a line, a ray, a line-segment, a point or an empty region. 每个半平面最多形成相交区域的一条边,因此相交区域不超过n条边。注意相交后的区域,有可能是一个直线、射线、线段或者点,当然也可能是空集。2. Convex Polygon Intersection (abbr. CPI)Intersecting two co
9、nvex polygons A and B into a single one, can be properly solved via Line Segment Intersection in O(nlogn) time, when there are O(n) edges. We will sketch out an easier and more efficient way, named plane sweep method.求两个凸多边形A和B的交(一个新凸多边形)。我们描绘一个平面扫描法。The main idea is to calculate intersections of ed
10、ges as cutting points, and break boundaries of A and B, into outer edges and inner edges. The segments of inner edges establish ties to each other, and form the shape of a polygon, which is the expected polygon after intersection. In Figure ii How the sweep line works. “” potentially shows next x-ev
11、ent., inner edges are indicated by thick segments, which form a bold outline of the intersection. 主要思想: 以两凸边形边的交点为分界点,将边分为内、外两种。内边互相连接,成为所求多边形。Suppose there is a vertical sweep line, performing left-to-right sweep. The x-coordinates to be swept are called x-events. At anytime, there are at most four
12、 intersections from sweep line to either given polygon Assume there is no edge in polygons parallel to the sweep line. If such situation happens, we could rotate the plane in proper angle, or else, we need good sense to judge a great many special cases.:假设有一个垂直的扫描线,从左向右扫描。我们称被扫描线扫描到的x坐标叫做x事件。任何时刻,扫描
13、线和两个多边形最多4个交点l to the upper hull of A (name that intersection Au for short)l to the lower hull of A (name that intersection Al for short)l to the upper hull of B (name that intersection Bu for short)l to the lower hull of B (name that intersection Bl for short)BuAuBlAlSweep linePolygon APolygon B! .
14、Look at Figure ii How the sweep line works. “” potentially shows next x-event., the lower one between intersections Au and Bu, and the upper one between intersections Al and Bl, form an interval of the current inner region the red segment in bold. Au、Bu中靠下的,和Al、Bl中靠上的,组成了当前多边形的内部区域。Obviously, the sw
15、eep line may not go through all the x-event with rational coordinates. Call the edges where Au, Al, Bu and Bl are: e1, e2, e3 and e4 respectively. The next x-event should be chosen among four endpoints of e1, e2, e3 and e4, and four potential intersections: e1e3, e1e4, e2e3 and e2e4.当然,我们不能扫描所有有理数!称Au, Al, Bu, Bl所在的边叫做e1,e2,e3,e4,下一个x事件将在这四条边的端点,以及两两交点中选出。The above operation could be implemented with O(n) running time, since there are O(n) x-events, and the maintenance of Au, Al, Bu and Bl takes only O(1).3. Common solution: