举例，多段线（ polyline ） A 和 B 都由 4 个节点组成，A 的四个节点坐标为(1,1) (2,1) (3,4) (4,4)，B 的四个节点坐标为(1,4) (2,2) (4,3) (3,1)， 这两条线是存在一个交点的，怎么求这个交点的精确坐标？
PS：如果要求再提高，比如 B 的四个节点坐标为(1,4) (2,2) (4,3) (1,0)，此时它们存在三个交点，怎么把他们都求出来？
9 条回复 • 2024-03-30 14:04:37 +08:00
 |
1
hefish 31 天前
穷举一下。 大不了就是求 12 对直线看相交不相交，相交的是否在线段上。
|
 |
2
NessajCN 31 天前 via Android
这不中学解几题吗…
用两组分段一元一次函数表示线段方程， 找出同定义域内是否存在解 |
 |
3
kalinzhang 31 天前  1
顺时针遍历一个 polygon 的所有顶点，联立方程求交点即可。套现成的公式，算两个行列式就完事了。
如果要优化的话，可以先判断一下两个 polygon 是否可能相交（例如算下 AABB ）再联立解方程，但其实解方程计算量也不大。 再扩展一下如果要做复杂 polygon 的相交测试的话，要考虑 polygon 是否有自交、是否是凹的、是否有多个 polygon 嵌套等情况，比较复杂了 |
 |
4
rabbbit 31 天前
https://paulbourke.net/geometry/pointlineplane/
往下翻 Intersection point of two line segments in 2 dimensions |
 |
5
Eloxt 31 天前
Java 的话可以用 JTS 库运算
https://github.com/locationtech/jts |
 |
6
SmiteChow 31 天前
shapely intersection result bound coords
|
 |
7
luassuns 31 天前
|
 |
8
ttentau1 31 天前
真好，你现在发问还有人回答，我之前在这里问都没人回答，自己弄了好久才弄出来
我参考了这个回答： https://stackoverflow.com/questions/37127144/how-can-i-fill-enclosed-shapes-in-a-line  我实现了一个比较完整的相交检测，可以查看这里的代码，https://github.com/zyronon/open-design/blob/01b0b80de453d97032357283fcdc35b37d1929e9/src/lib/designer/shapes/Pen.ts#L250 |
 |
9
akira 31 天前
2 条直线求相交点会吧
2 个线段求相交点会吧 1 个线段和 3 个 线段 分别求交点 会吧 3 个线段和 3 个 线段 分别求交点 会吧 那就做完了啊。。 |
Select Language