computational-geometry - 找到两个多边形之间的分隔线

Question

是否有一个简单的算法可以在两个多边形之间找到一条分隔线，使它们位于线的两侧？或者最好有人知道做这种事情的图书馆吗？任何帮助，将不胜感激

编辑:

我的解决方案:

我用过 JTS:http://www.vividsolutions.com/jts/JTSHome.htm

使用这个库创建了两个多边形并运行 DistanceOp 来找到多边形之间的两个最近点(不一定是顶点)。然后简单地计算与连接它们的线的垂直线。

Answer 1

让 A 和 B 成为你的两个多边形。先找到convex hull C(A) 和 C(B)。
显然，将 A 与 B 分开的线也将 C(A) 与 C(B) 分开。
设 a 是 C(A) 上的一个点，b 是 C(B) 上的一个点。一个人可以走a和b
边界，直到找到通过 a 和 b 的分隔线。这可以是
在线性时间内完成，但我现在不会描述。