我们已经讨论了这个问题，以检测 两条给定线段是否相交 .在这篇文章中，我们扩展了这个问题。这里我们给出了n条线段，我们需要找出任意两条线段是否相交。 朴素算法 解决这个问题的一个简单方法是检查每一对线，并检查这对线是否相交。 我们可以在O（1）时间内检查两条线段 因此，这种方法需要O（n 2. ). 扫描线算法： 我们可以在短期内解决这个问题 O（nLogn） 时间使用扫描线算法。该算法首先沿x轴从左到右对端点进行排序，然后从左到右通过一条垂直线穿过所有点，并检查交点。以下是详细的步骤。 1) 让n个给定的行。必须有2n个端点才能代表n条线。根据x坐标对所有点进行排序。排序时，保留一个标志，指示该点是其直线的左点还是右点。 2) 从最左边的点开始。对每一点都要遵循 ….. （a） 如果当前点是其线段的左侧点，请检查其线段与其正上方和下方线段的交点。并将其行添加到 忙碌的 线段（可以看到左端点，但尚未看到右端点的线段）。注意，我们只考虑那些仍然活跃的邻居。 …. b） 如果当前点是右点，请从活动列表中删除其线段，并检查其两个活动相邻点（正上方和下方的点）是否相交。 第二步就像从最左边的点到最右边的点，从所有点穿过一条垂直线。这就是为什么这个算法被称为扫描线算法。扫描线技术在许多其他几何算法中都很有用，比如计算二维Voronoi图 高效实施应该使用什么数据结构？ 在步骤2中，我们需要存储所有活动线段。我们需要高效地执行以下操作： a） 插入新线段 b） 删除线段 c） 根据y坐标值查找前置和后续 上述操作的明显选择是自平衡二叉搜索树，如AVL树、红黑树。使用自平衡BST，我们可以在O（Logn）时间内完成上述所有操作。 此外，在步骤1中，我们可以使用最小堆数据结构，而不是排序。构建一个min堆需要O（n）时间，而每个extract min操作需要O（Logn）时间（参见 这 ). 伪代码： 以下伪代码不使用heap。它只是对数组进行排序。
sweepLineIntersection(Points[0..2n-1]):1. Sort Points[] from left to right (according to x coordinate)2. Create an empty Self-Balancing BST T. It will contain all active line Segments ordered by y coordinate.// Process all 2n points 3. for i = 0 to 2n-1 // If this point is left end of its line if (Points[i].isLeft) T.insert(Points[i].line()) // Insert into the tree // Check if this points intersects with its predecessor and successor if ( doIntersect(Points[i].line(), T.pred(Points[i].line()) ) return true if ( doIntersect(Points[i].line(), T.succ(Points[i].line()) ) return true else // If it's a right end of its line // Check if its predecessor and successor intersect with each other if ( doIntersect(T.pred(Points[i].line(), T.succ(Points[i].line())) return true T.delete(Points[i].line()) // Delete from tree4. return False
例子： 让我们考虑下面的例子 在这里 .有5条线段 1. , 2. , 3. , 4. 和 5. .绿色虚线表示扫掠线。
以下是算法的步骤。从左到右的所有点都会逐个处理。我们维护一个自平衡二叉搜索树。
处理线段1的左端点 : 1被插入到树中。这棵树包含 1. .没有交叉路口。
处理线段2的左端点 : 交叉点 1. 和 2. 检查完毕。 2. 插入树中。找到了1和2的交集（“请注意，上面的伪代码此时返回”）。我们可以从这里继续报告所有交叉点。这棵树包含 1. , 2. .
处理线段3的左端点： 交叉点 3. 具有 1. 检查完毕。没有交叉路口。 3. 插入树中。这棵树包含 2. , 1. , 3. .
处理线段1的右端点： 1. 已从树中删除。交叉点 2. 和 3. 检查完毕。交叉点 2. 和 3. 据报道。这棵树包含 2. , 3.
处理线段4的左端点 : 直线交点 4. 用台词 2. 和 3. 检查过了。没有交叉路口。 4. 插入树中。这棵树包含 2. , 4. , 3. .
处理线段5的左端点 : 交叉点 5. 具有 3. 检查完毕。没有交叉路口。 5. 插入树中。这棵树包含 2, 4, 3, 5 .
处理线段5的右端点： 5. 已从树中删除。这棵树包含 2. , 4. , 3. .
处理线段4的右端点： 4. 已从树中删除。这棵树包含 2. , 4. , 3. .交叉点 2. 具有 3. 检查完毕。交叉点 2. 具有 3. 报告（请注意，2和3的交集再次报告。我们可以添加一些逻辑来检查重复项）。这棵树包含 2. , 3. .
处理线段2和3的右端点： 两者都从树中删除，树变为空。
C++14
#include <bits/stdc++.h> using namespace std; // A point in 2D plane struct Point { int x, y; }; // A line segment with left as Point // with smaller x value and right with // larger x value. struct Segment { Point left, right; }; // An event for sweep line algorithm // An event has a point, the position // of point (whether left or right) and // index of point in the original input // array of segments. struct Event { int x, y; bool isLeft; int index; Event( int x, int y, bool l, int i) : x(x), y(y), isLeft(l), index(i) {} // This is for maintaining the order in set. bool operator<( const Event& e) const { if (y==e.y) return x<e.x; return y < e.y; } }; // Given three collinear points p, q, r, the function checks if // point q lies on line segment 'pr' bool onSegment(Point p, Point q, Point r) { if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) && q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y)) return true ; return false ; } // To find orientation of ordered triplet (p, q, r). // The function returns following values // 0 --> p, q and r are collinear // 1 --> Clockwise // 2 --> Counterclockwise int orientation(Point p, Point q, Point r) { // for details of below formula. int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y); if (val == 0) return 0; // collinear return (val > 0)? 1: 2; // clock or counterclock wise } // The main function that returns true if line segment 'p1q1' // and 'p2q2' intersect. bool doIntersect(Segment s1, Segment s2) { Point p1 = s1.left, q1 = s1.right, p2 = s2.left, q2 = s2.right; // Find the four orientations needed for general and // special cases int o1 = orientation(p1, q1, p2); int o2 = orientation(p1, q1, q2); int o3 = orientation(p2, q2, p1); int o4 = orientation(p2, q2, q1); // General case if (o1 != o2 && o3 != o4) return true ; // Special Cases // p1, q1 and p2 are collinear and p2 lies on segment p1q1 if (o1 == 0 && onSegment(p1, p2, q1)) return true ; // p1, q1 and q2 are collinear and q2 lies on segment p1q1 if (o2 == 0 && onSegment(p1, q2, q1)) return true ; // p2, q2 and p1 are collinear and p1 lies on segment p2q2 if (o3 == 0 && onSegment(p2, p1, q2)) return true ; // p2, q2 and q1 are collinear and q1 lies on segment p2q2 if (o4 == 0 && onSegment(p2, q1, q2)) return true ; return false ; // Doesn't fall in any of the above cases } // Find predecessor of iterator in s. set<Event>::iterator pred(set<Event> &s, set<Event>::iterator it) { return it == s.begin() ? s.end() : --it; } // Find successor of iterator in s. set<Event>::iterator succ(set<Event> &s, set<Event>::iterator it) { return ++it; } // Returns true if any two lines intersect. int isIntersect(Segment arr[], int n) { unordered_map<string, int > mp; // to note the pair for which intersection is checked already // Pushing all points to a vector of events vector<Event> e; for ( int i = 0; i < n; ++i) { e.push_back(Event(arr[i].left.x, arr[i].left.y, true , i)); e.push_back(Event(arr[i].right.x, arr[i].right.y, false , i)); } // Sorting all events according to x coordinate. sort(e.begin(), e.end(), [](Event &e1, Event &e2) { return e1.x < e2.x;}); // For storing active segments. set<Event> s; int ans=0; // Traversing through sorted points for ( int i=0; i<2*n; i++) { Event curr = e[i]; int index = curr.index; // If current point is left of its segment if (curr.isLeft) { // Get above and below points auto next = s.lower_bound(curr); auto prev = pred(s, next); // Check if current point intersects with // any of its adjacent bool flag= false ; if (next != s.end() && doIntersect(arr[next->index], arr[index])){ string s=to_string(next->index+1)+ " " +to_string(index+1); if (mp.count(s)==0){mp[s]++;ans++;} //if not already checked we can increase count in map } if (prev != s.end() && doIntersect(arr[prev->index], arr[index])){ string s=to_string(prev->index+1)+ " " +to_string(index+1); if (mp.count(s)==0){mp[s]++;ans++;} //if not already checked we can increase count in map } // if same line segment is there then decrease answer as it got increased twice if (prev != s.end() && next != s.end() && next->index==prev->index)ans--; // Insert current point (or event) s.insert(curr); } // If current point is right of its segment else { // Find the iterator auto it=s.find(Event(arr[index].left.x, arr[index].left.y, true , index)); // Find above and below points auto next = succ(s, it); auto prev = pred(s, it); // If above and below point intersect if (next != s.end() && prev != s.end()) { string s=to_string(next->index+1)+ " " +to_string(prev->index+1); string s1=to_string(prev->index+1)+ " " +to_string(next->index+1); if (mp.count(s)==0&&mp.count(s1)==0&&doIntersect(arr[prev->index], arr[next->index])) ans++; mp[s]++; } // Remove current segment s.erase(it); } } //print pair of lines having intersection for ( auto &pr:mp){ cout<<pr.first<< "" ; } return ans; } // Driver code int main() { Segment arr[] = { {{1, 5}, {4, 5}}, {{2, 5}, {10, 1}},{{3, 2}, {10, 3}},{{6, 4}, {9, 4}},{{7, 1}, {8, 1}}}; int n = sizeof (arr)/ sizeof (arr[0]); cout<<isIntersect(arr, n); return 0; } |
输出：
0
时间复杂性： 第一步是排序，这需要O（nLogn）时间。第二步处理2n个点，处理每个点需要O（Logn）时间。因此，总体时间复杂度为O（nLogn） 参考资料： http://www.cs.uiuc.edu/~jeffe/teaching/373/notes/x06 sweedline。pdf http://courses.csail.mit.edu/6.006/spring11/lectures/lec24.pdf http://www.youtube.com/watch?v=dePDHVovJlE http://www.eecs.wsu.edu/~库克/aa/讲座/l25/节点10。html 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
