线相交横向 [英] Line intersection transversal

问题描述

我有几个随机的线段.我必须检查任意两个线段之间是否有任何交集.线路可以连接或不连接.什么是解决这个问题的好算法?

I have several random line segments. I have to check if there is any intersection between any two line segments. Lines may be connected or not. What would be a good algorithm for this problem?

推荐答案

假设您在这里谈论线段(否则，只需比较线的斜率:如果它们的斜率不相等，它们就会相交).

Assuming you're talking about line segments here (otherwise, simply compare the slopes of the lines: if they have unequal slopes, they intersect).

要找出在一组2个或更多线段中是否存在[单个]交点，可以使用Shamos-Hoey算法.

To find out if a [single] intersection exists in a set of 2 or more line segments, you can use the Shamos-Hoey algorithm.

要查找一组2个或更多线段中的所有个交点，可以使用Bentley-Ottmann算法.

To find all intersections in a set of 2 or more line segments, you can use the Bentley-Ottmann algorithm.

这两种算法以及其他基于扫描线"的算法的实现

Implementation of the two, and other "sweep-line" based algorithms, are abundantly available on the internet.

这篇关于线相交横向的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！