任意多边形费马点&点群中位中心求解

点群中位中心求解

1问题讨论

从上两式不难看出，空间点（x0,y0）可以取空间中任意一点有无穷种可能，因此难以求得精确。只能使用迭代的方式来求无限逼近的解，当然求用一些奇特的方法求近似解也是可以的。

       更加一般的，点群的中位中心问题是p-median问题d特例，即1-median问题。P-中值问题可以描述。而同样的问题放在多边形中，就变成了费马点的求解。

本文主要从底层讨论三种算法并给出其实现，同时指出其他算法可能性。

2算法

2.1 二分互垂近似算法

       基本思想为：做一组互垂的直线，两条直线均把把点群分成等数量两部分。取多组这样的直线，每组直线交点的平均中心即为点群中位中心的近似。

       算法步骤为：

STEP 1: 将点群副本绕原点顺时针旋转k*90o/n，横纵两个方向，用二分法扫描点群，找到横纵方向能把点群分为两个等数量部分直线，将直线交点逆时针旋转k*90o/n,记录旋转后的点;( k指旋转的次数,初始化为0。n-1指最大旋转次数也代表着求解精度。所谓二分法就是，根据横轴或纵轴区间对半切，判断那边的点多，对多的那一边再对半切，直到切完后直线两边点的数量相等)

STEP 2: 判断k是否不大于n-1，是则k++返回STEP1，否则输出交点的平均中心。

2.2 网格点近似算法

基本思想为：将点群所在的空间划分成小的网格，所有网格点中离点群总距离最近的点就是要求的点群中位中心的近似。

算法步骤为：

STEP 1: 扫描点群，找出其四至；

STEP 2: 根据输入精度n，计算点群四至矩形范围内均匀分布的格网点坐标；

STEP 3: 计算每个网格点与点群的总距离，取总距离最小的网格点作为近似的中位中心。

2.3 四方向变步长贪婪算法

基本原理：点群的中位中心和平均中心其实相隔的并不远，可以点群平均中心为起始点，以一定步长向四周移动，从中选择最优的点。如果当前点比所有移动点更优，说明移动的过分了，这时需要缩小步长继续移动搜索，直到精度达到要求。

算法步骤：