已知两个相交的 polyline 的坐标点集合，怎么求交点的精确坐标？坐标点不在点集里

[WangLiCha]

举例，多段线（ 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)，此时它们存在三个交点，怎么把他们都求出来？

[hefish]

穷举一下。 大不了就是求 12 对直线看相交不相交，相交的是否在线段上。

[NessajCN]

这不中学解几题吗…
用两组分段一元一次函数表示线段方程，
找出同定义域内是否存在解

[kalinzhang]

顺时针遍历一个 polygon 的所有顶点，联立方程求交点即可。套现成的公式，算两个行列式就完事了。
如果要优化的话，可以先判断一下两个 polygon 是否可能相交（例如算下 AABB ）再联立解方程，但其实解方程计算量也不大。
再扩展一下如果要做复杂 polygon 的相交测试的话，要考虑 polygon 是否有自交、是否是凹的、是否有多个 polygon 嵌套等情况，比较复杂了

[rabbbit]

https://paulbourke.net/geometry/pointlineplane/
往下翻 Intersection point of two line segments in 2 dimensions

[Eloxt]

Java 的话可以用 JTS 库运算
https://github.com/locationtech/jts

[SmiteChow]

shapely intersection result bound coords

[luassuns]

opencascade 可以用 https://dev.opencascade.org/doc/refman/html/class_geom2d_a_p_i___inter_curve_curve.html#a9b569dd0038675203dbee5c33f6849d2

[ttentau1]

真好，你现在发问还有人回答，我之前在这里问都没人回答，自己弄了好久才弄出来

我参考了这个回答： 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

[akira]

2 条直线求相交点会吧
2 个线段求相交点会吧
1 个线段和 3 个 线段 分别求交点 会吧
3 个线段和 3 个 线段 分别求交点 会吧
那就做完了啊。。