找到一个非代表性的平均值INTERIOR点
我试图解决C ++中的旅行推销员问题，但我必须遍历一组poylgons之间的最短距离，而不是一组点。 要做到这一点，我试图用代表性的“平均”内部点来表示每个多边形，以便我可以在这些平均内部点上做TSP。
我很容易在凸多边形中找到一个平均内点，因为它仅仅是算术平均点（并且对于凸多边形总是位于内部），但这种方法对于凹多边形不起作用，因为它不一定适用于凹多边形在多边形的内部。
帮助这个？ 谢谢。 :-)
怎么样：
由于整个非凸多边形的真正重心（可能）位于多边形之外，因此我认为对于“代表性”点的另一个定义并不适用于我，这比我更有意义。
一个想法是构造每个多边形的凸包，然后使用凸包的中心。 要理解这个想法就像是用橡皮筋包裹多边形一样，这给你一个信封，你可以用它来找到感兴趣的点。 我相信你应该能够使用CGAL来计算。 但是如果你为每个多边形做这个，它不会超快。 如果您构建三角剖分，那么您可以高效地找到原始多边形的最靠近的内点与其凸包的中心点，作为额外的步骤。
顺便说一句，我认为正确的方法来找到一个凸多边形的点中心是找到切比雪夫中心，这对应于解决一个线性系统，你也可以使用CGAL。 在Boyd书中已经很好地定义了寻找凸多边形Chebyshev中心的线性规划问题。
链接地址: http://www.djcxy.com/p/67205.html