半平面求交算法.docVIP

Step 1: Separate the h-planes into two sets. One has polar angles of (-?π, ?π], the other has those of (-π, -?π]∪(?π, π]. 将半平面分成两部分，一部分极角范围(-?π, ?π]，另一部分范围(-π, -?π]∪(?π, π] Step 2: Consider the set of h-planes in (-?π, ?π] (the other set should also go through step 3 and 4 similarly). Sort them by the polar angle. For the h-planes with the same polar angle, we can keep only one down (delete all others) according to the constant of these h-planes 考虑(-?π, ?π]的半平面(另一个集合类似地做Step3/4)，将他们极角排序。对极角相同的半平面，根据常数项保留其中之一。 Step 3.1: Starting from two h-planes with the least polar angle, compute their intersection. Push them two into a stack. 从排序后极角最小两个半平面开始，求出它们的交点并且将他们押入栈。 Step 3.2: Each time, add one more h-plane by increasing order of polar angles, and calculate the intersection of it and the top h-plane in stack. 每次按照极角从小到大顺序增加一个半平面，算出它与栈顶半平面的交点。 Step 3.3: If this intersection is to the right of the intersection of top two h-planes in stack, we pop the stack once. 如果当前的交点在栈顶两个半平面交点的右边，出栈（pop）。 Step 4.1: Intersections of adjacent h-plane pairs in stack form half a convex polygon. For the two sets, we have two halves – (-?π, ?π] gives an upper hull and (-π, -?π]∪(?π, π] gives a lower hull. 相邻半平面的交点组成半个凸多边形。我们有两个点集，(-?π, ?π]给出上半个，(-π, -?π]∪(?π, π]给出下半个 Step 4.2: At the beginning, four pointers p1, p2, p3 and p4 indicate leftmost/rightmost edges of both upper and lower hulls. p1 and p3 move rightwards, while p2 and p4 walks leftwards. 初始时候，四个指针p1, p2, p3 and p4 指向上/下凸壳的最左最右边 p1, p3向右走，p2, p4向左走 Step 4.3: At anytime, if the leftmost intersection is against the feasible region provided by p1 or p3, we are sure the leftmost one is to be removed. Naturally, p1 or p3 walks rightwards to its adjacent edge. 任意时刻，如果最左边的交点不满足p1/p3所在半平面的限制，我们相信这个交点需要删除 p1或p3走向它右边的相邻边 The judgment holds analogously for rightmost intersection with p2 and p4. 类似地我们处理最右边的交点 Step 4.4: Do the above removing repeatedly until there is no more update. 重复运作直到不再有更新出现——迭代 Everything except so