从列表中获得3个最常见的点

本文关键字：3个 常见 列表 Point | 更新日期: 2023-09-27 18:13:45

我有一个快速的问题，我还没有发现如何有效地做(在c#中)

我有一个点(X,Y)的列表数组。我需要找出哪三个点是最紧密的簇。这是一个映射项目。

最好的方法是什么?列表中只有6到9个项目。

提前感谢。

干杯!

从列表<Point>中获得3个最常见的点

对于这么小的数字，蛮力方法应该可以很好地工作。有6个点，3个点有20种可能的组合。有9个点，有84种可能的组合。我不建议在很多情况下使用这种方法，但只使用少数几个点，它就足够快了，而且编写起来非常简单。

您可以轻松地生成组合:

for (int i = 0; i < points.Length - 2; ++i)
{
    for (j = i + 1; j < points.Length - 1; j++)
    {
        for (k = j + 1; k < points.Length; k++)
        {
            // Here, your three points are
            // points[i], points[j], and points[k]
            // compute "tightness" and store
        }
    }
}

你需要一个结构来保存你的组合:

struct PointGroup
{
    public readonly int i;
    public readonly int j;
    public readonly int k;
    public readonly double tightness;
    public PointGroup(int i, int j, int k, double tight)
    {
        this.i = i;
        this.j = j;
        this.k = k;
        this.tightness = tight;
    }
}

如果您为每个组创建一个这样的结构，并将它们存储在数组中，您可以简单地对数组进行排序，并取最好的三个。

你更大的问题是想出一个"紧密群体"的定义。此外，你必须决定一个点是否可以出现在多个"最紧密"的组中。定义紧度的三种可能方法是:

  • 点之间的距离之和被最小化。
  • 每个点到组中心的平均距离最小。
  • 由三个点组成的三角形的周长被最小化。

如果这些点不相同，这就成为一种聚类分析的形式。

有各种各样的算法在如何测量和"聚类"点方面有所不同，尽管只有几个点，蛮力方法可能是最简单的…你可以测量每对点之间的距离，然后排序。

你可以把问题简化如下:

  1. 不要检查一个点对它自己;
  2. 利用对称性:从点i到点j的距离与点j到点i的距离相同

这些消除了许多组合。

但是，给定这些，你必须计算每对和排序之间的距离

相关文章：