《(2020年)价值管理半平面交的新算法及其实用价值》由会员分享，可在线阅读，更多相关《(2020年)价值管理半平面交的新算法及其实用价值（10页珍藏版）》请在金锄头文库上搜索。
1、半平面交的新算法及其实用价值 Keywords: Half-plane, Intersection, Feasible Region, Algorithm, Polygon, PracticalAbstract主旨:半平面的交是当今学术界热烈讨论的问题之一，本文将介绍一个全新的O(nlogn)半平面交算法，强调它在实际运用中的价值，并且在某种程度上将复杂度下降至O(n)线性。最重要的是，我将介绍的算法非常便于实现.1 introduces what half-plane intersection is. 2 prepares a linear algorithm for convex poly
2、gon 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 compares it with the older algorithm describe
3、d 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 HPI problem in Peking University Online Judg
4、e, 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 for short) as one side of this line. Notice t
5、hat 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 points that satisfying all the n inequation
6、s. 给定n个形如aix+biyci的半平面，找到所有满足它们的点所组成的点集As ! . describes, the feasible region, which is the intersection, forms a shape of convex hull but possibly unbounded. However, we shall add four h-planes forming a rectangle, which is large enough to make sure the area after intersections finite. In the follow
7、ing 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 polygon, hence, the convex region will be bounded by at most n edges. Pay attention the intersection sometimes yields a line, a
8、 ray, a line-segment, a point or an empty region. 每个半平面最多形成相交区域的一条边，因此相交区域不超过n条边。注意相交后的区域，有可能是一个直线、射线、线段或者点，当然也可能是空集。2. Convex Polygon Intersection (abbr. CPI)Intersecting two convex polygons A and B into a single one, can be properly solved via Line Segment Intersection in O(nlogn) time, when there
9、 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 edges as cutting points, and break boundaries of A and B, into outer edges and inner edges. The segments of inner edges esta
10、blish ties to each other, and form the shape of a polygon, which is the expected polygon after intersection. In ! ., inner edges are indicated by thick segments, which form a bold outline of the intersection. 主要思想: 以两凸边形边的交点为分界点，将边分为内、外两种。内边互相连接，成为所求多边形。Suppose there is a vertical sweep line, perfor
11、ming left-to-right sweep. The x-coordinates to be swept are called x-events. At anytime, there are at most four 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,
12、or else, we need good sense to judge a great many special cases.:假设有一个垂直的扫描线，从左向右扫描。我们称被扫描线扫描到的x坐标叫做x事件。任何时刻，扫描线和两个多边形最多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
13、for short)l to the lower hull of B (name that intersection Bl for short)BuAuBlAlSweep linePolygon APolygon B! .Look at ! ., 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中靠下
14、的，和Al、Bl中靠上的，组成了当前多边形的内部区域。Obviously, the sweep 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
15、: 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:Divide-and-Conquer Algorithm (abbr. D&Q)The basic approach is simple, depends on divide-and-conquer idea.l Divide: Partition the n h-planes into two sets of size and .l Conquer: Compute the feasible region (intersection) recursively of both two
