寻找非凸多边形的代表性内部点的平均值

Question

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

对于凸多边形，很容易找到一个平均内部点，因为它只是算术平均点（并且始终位于凸多边形内部），但是这种方法对于凹多边形将无法奏效，因为它不一定位于多边形内部。

这方面有什么帮助吗？谢谢。 :-)

- Ananth Saran

---

你如何表示你的多边形？我添加了标签“算法”，因为这基本上是一个算法问题。你能承受什么样的复杂度？ - Boris Strandjev

为什么必须是内部点？我想你要么想找到一个近似值，那么我不明白为什么需要内部点。或者一般情况下的最短路径，那么我不会使用平均代表，而是完全摆脱多边形，并将问题直接转化为TSP。 - Fiktik

你可能会对直骨架感兴趣。 - pmr

@Boris，我现在正在寻找一个好的解决方案，并且可以承受最多N^3的成本。 - Ananth Saran

@AnanthSaran 这样的点也可能在多边形外面。 - Xyand

Answer 1

如下：

1. 三角剖分多边形（O(N log(N))）
2. 选择面积最大的三角形（例如）（O(N)）
3. 在该三角形的重心处放置你的点。（常数时间）

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

- emsr

Answer 2

一个想法是构建每个多边形的凸包，然后使用凸包的中心点。理解这个想法就像是用橡皮筋包裹任何多边形，这会给你一个信封，你可以用它来找到感兴趣的点。我相信你应该能够使用CGAL计算出来。但如果你对每个多边形都这样做，速度不会很快。如果你建立一个三角剖分，那么你可以有效地找到原始多边形最靠近其凸包中心点的内部点作为附加步骤。

顺便说一句，我认为找到凸多边形的中心点的正确方法是找到切比雪夫中心，这对应于解决一个线性系统，你也可以使用CGAL来完成。寻找凸多边形的切比雪夫中心的线性规划问题在Boyd book中有明确定义。

- SkyWalker