寻找代表性意味着非凸多边形的INTERIOR点

Question

我试图解决c ++中的旅行商问题,但我必须遍历一组poylgons而不是一组点之间的最短距离.为此,我试图通过代表性的"平均"内部点来表示每个多边形,以便我可以在这些平均内部点上执行TSP.

我很容易在凸多边形中找到一个平均内点,因为它只是算术平均点(并且总是位于凸多边形的内部),但这种方法不适用于凹多边形,因为它不一定在多边形的内部.

帮忙吗？谢谢.:-)

Answer 1

怎么样：

1. 对多边形进行三角剖分（N 阶 log(N)）
2. 选择面积最大的三角形（例如）（N 阶）
3. 在该三角形的重心处选择您的点。（常量）

由于整个非凸多边形的真正重心（可能）位于多边形之外，我认为对于“代表性”点来说，没有其他定义比这更有意义。