Как найти ближайшие точки выше и ниже заданной точки?

Question

У меня есть многоугольник, определяемый следующими вершинами, представленными их значениями X и Y и , отсортированными в порядке против часовой стрелки:

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

У меня также есть List<int>, содержащий их индексы . Я могу сжать два списка вместе, если я хочу изменить порядок точек, следя за исходным порядком.

Как мне go узнать о получении ближайших точек выше и ниже заданной точки, чтобы ввести:

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)