如何找到给定点上方和下方的最近点？

Question

我有一个由以下顶点定义的多边形，由它们的 X 和 Y 值和 sorted 以逆时针顺序表示：

{ 20, 10},
{110, 10},
{100, 40},
{ 80, 50},
{ 40, 50},
{ 20, 30}

我还有一个 List<int> 包含他们的索引。如果我想在跟踪原始顺序的同时重新排序这些点，我可以将两个列表压缩在一起。

我应该如何获得给定点上方和下方的最近点，以便输入：

point = {115, 30}

将输出：

closestAbove = {100, 40}, index = 2
closestBelow = {110, 10}, index = 1

性能并不重要，因此在列表中多次迭代不是问题。

Answer 1

首先，让我们达成共识：

  // I've put named tuples, but you can use a different type for points
  (double x, double y)[] points = new (double x, double y)[] {
    (  20, 10 ), 
    ( 110, 10 ), 
    ( 100, 40 ), 
    (  80, 50 ), 
    (  40, 50 ), 
    (  20, 30 ),
  };

  // Euclidian distance
  Func<(double x, double y), (double x, double y), double> distance = (p1, p2) =>
    Math.Sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));

  (double x, double y) point = (115, 30);

然后借助Linq进行查询；即使 ArgMin 未通过标准 Linq 实现，也可以借助 Aggregate:

轻松完成

  var above = points
    .Select((p, index) => new {
      p,
      index
    })
    .Where(item => item.p.y > point.y) // change to < for below
    .Aggregate((distance: 0.0,
                x: 0.0,
                y: 0.0,
                index: -1),
               (s, a) => s.index < 0 || s.distance > distance(point, a.p)
                  ? (distance(point, a.p), a.p.x, a.p.y, a.index)
                  : s);

一起来看看：

  Console.Write($"Point #{above.index} ({above.x}, {above.y}) is the closest point to the ({point.x}, {point.y})");

结果：

Point #2 (100, 40) is the closest point to the (115, 30)

如何找到给定点上方和下方的最近点？

How to find the closest points above and below a given point?

c#

coordinates