给定N个点(在2D中)，分别带有x和y坐标。您必须找到一个点P(在N个给定的点中)，以使从其他(N-1)个点到P的距离之和最小。
对于前。给定p1(x1，y1)，p2(x2，y2)...... pN(xN，yN)的N个点。
我们在p1，p2 .... PN中找到了一个点P，其与所有其他点的距离之和最小。
我使用了蛮力方法，但是我需要一个更好的方法。我还尝试通过找到中位数，均值等来进行尝试，但是它不适用于所有情况。
然后我想到了将X视为多边形的顶点并找到该多边形的质心的想法，然后从Y中选择一个最接近质心的点。但是我不确定质心是否将其到多边形顶点的距离之和最小化，所以我不确定这是否是一种好方法？有解决这个问题的算法吗？
最佳答案
如果您的点分布均匀，并且其中的点太多，以至于蛮力(计算每个点到每个其他点的总距离)不那么吸引人，那么以下内容可能会给您一个足够好的答案。 “很好地分布”是指(大约)均匀或(大约)随机，并且在多个位置没有明显的聚类。
在您的空间上创建一个统一的k*k网格，其中k是一个奇数整数。如果您的点分布良好，那么您正在寻找的点(可能)在此网格的中心单元中。对于网格中的所有其他单元格，计算每个单元格中的点数，并估计每个单元格中点的平均位置(使用单元格中心或计算该单元格中点的平均(x,y))。
对于中心单元中的每个点，计算到中心单元中每个其他点的距离，以及到其他单元中的点的加权平均距离。当然，这将是从点到其他单元中点的“平均”位置的距离，并由其他单元中的点数加权。
您必须权衡k的较高值的更高准确性与增加的计算负荷，并找出最适合您的点的方法。如果跨单元的点分布远非均匀，则此方法可能不合适。
这种方法已广泛用于大规模仿真中，在这些仿真中，点具有随距离而变的特性，例如重力和电荷。不知道它是否适合您的需求。
关于algorithm - 找到最接近其他点的点，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10310013/