Paw*_*ski 10 gis algorithm optimization geometry
我有一组(X)点(不是很大,比如1-20分)和第二组(Y),更大的点数.我需要从Y中选择一个点,从X 到X的所有点的距离总和是最小的.
我想出了一个想法,我将X视为多边形的顶点并找到该多边形的质心,然后我将从Y最接近质心的位置选择一个点.但我不确定质心是否最小化了它到多边形顶点的距离之和,所以我不确定这是否是一个好方法？有没有解决这个问题的算法？
点由地理坐标定义.
小智 4
多边形的质心可能不正确，但这样的点是存在的。
在论文：n-椭圆和最小距离问题中，表明如果点（称为焦点，您的 X 集）不共线，那么
有一个独特的点（称为中心），其距离总和最小。该点使得从该点到焦点的单位向量之和为零！
距离总和恒定的点的轨迹是包含中心的凸曲线（称为 n 椭圆）
距离 D 的 n 椭圆完全包含任何其他距离 D' 的 n 椭圆，其中 D' < D。
因此，您可以执行某种类型的爬山算法来找到中心。
当然，这些 n 个椭圆不一定是圆形，因此仅选择最接近中心的点可能行不通，但可能是一个很好的近似值。
您也许可以对 20 个点（如果这些点是固定的）进行一些预处理，以找出一个好的分区方案（基于上述信息）。
希望有帮助。