7

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

我很容易在凸多边形中找到平均内部点，因为它只是算术平均点（对于凸多边形，它总是位于内部），但是这种方法不适用于凹多边形，因为它不一定在多边形内部。

这方面的帮助？谢谢。:-)

4

2 回答 2

3

怎么样：

  1. 三角多边形（阶数 N log(N)）
  2. 选择面积最大的三角形（比方说）（N阶）
  3. 在该三角形的重心处选择您的点。（常量）

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

于 2012-12-13T13:39:14.213 回答
1

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

顺便说一句，我认为找到凸多边形点中心的正确方法是找到切比雪夫中心，这对应于求解线性系统，您也可以使用 CGAL 来解决。寻找凸多边形切比雪夫中心的线性规划问题在Boyd 书中得到了很好的定义。

于 2012-12-13T13:33:26.633 回答