是否有一种简单的算法可以找到两个多边形之间的分隔线，使它们位于线的两侧？或者最好有人知道做这种事情的图书馆吗？任何帮助，将不胜感激
编辑：
我的解决方案：
我用过 JTS： http: //www.vividsolutions.com/jts/JTSHome.htm
使用这个库创建了两个多边形并运行 DistanceOp 来找到多边形之间最近的两个点（不一定是顶点）。然后简单地计算一条垂直线到连接它们的线。
问问题
731 次
2 回答
3
让A和B成为你的两个多边形。首先找到每个C(A)和C(B)的凸包。显然，将A与 B 分开的线也将C(A)与C(B)分开。设a为 C(A) 上的一个点，b为C(B)上的一个点。可以绕着边界走a和b ，直到找到穿过a和b的分隔线。这可以在线性时间内完成，但我现在不会描述。
于 2013-05-05T22:09:56.857 回答
2
假设您有一个带有点 A1、A2、A3、...、AN 的多边形 A 和一个带有点 B1、B2、B3、...、BM 的多边形 B。
您可以做的是为每个可能的组合（A1 和 B1、A1 和 B2、... AN 和 BM）描述从点 AX 到 BX 的线。
这样的线可以用参数格式描述：SomePoint = InicialPoint + Direction * t 并且可能是“分隔线”的候选者。收下！
现在你要做的是描述从每个多边形的每个点到这条候选线的另一个向量。每一条线都有它的方向向量。
如果每条线的方向向量与候选的方向向量的叉积具有相同的方向（Z 正或 Z 负），则表示这些点在分隔线的同一侧（仍为候选）。
现在检查您为每个多边形的每个点描述的所有线。您可以确定多边形 A 的所有点是否都在一侧，多边形 B 中的所有点是否都在另一侧...然后您找到了所需的线。如果没有，您必须尝试下一条候选线（AX-BX）。如果您没有找到任何这些组合与所有可能的候选线，则意味着您在多边形之间存在交集。
我不确定它是否是最好/最快的算法，但我确信它有效。
于 2013-05-05T18:38:59.047 回答