Точка в многоугольнике ИЛИ точка на многоугольнике с помощью LINQ

Question

Как отмечалось в предыдущем вопросе, Как Zip перечислим с собой , я работаю над некоторыми математическими алгоритмами, основанными на списках точек. В настоящее время я работаю над точкой в ​​многоугольнике. У меня есть код для того, как это сделать, и я нашел несколько хороших ссылок здесь, на SO, например, эту ссылку Hit test . Итак, я могу выяснить, есть ли точка в многоугольнике. Как часть определения этого, я хочу определить, действительно ли точка находится на многоугольнике. Это я тоже могу сделать. Если я смогу сделать все это, какой мой вопрос вы можете задать?

Могу ли я сделать это эффективно с помощью LINQ? Я уже могу сделать что-то вроде следующего (предполагая метод парного расширения, как описано в моем предыдущем вопросе, а также в ссылках, на которые ссылается мой вопрос / ответ, и предполагая тип позиции, который имеет члены X и Y). Я не проверял много, поэтому лямбда может быть не на 100% правильной. Кроме того, он не учитывает очень небольшие различия.

EDIT Обратите внимание, что последнее изменение этого кода было изменено с TakeWhile на TakeWhileInclusive. См. Метод расширения в конце этого поста.

//
// Extend a ray from pt towards the left.  Does this ray intersect the segment p1->p2?
// By definition, the ray extending from pt cannot intersect a horizontal segment, so our
// first check is to see whether or not the segment is horizontal.  
// If it is, there cannot be an intersection.
// If it is not, there could be an intersection.
//
public static bool PointIntersectSegment(Position p1, Position p2, Position pt)
{
  bool intersect = false;
  if (p1.Y != p2.Y)
  {
    // Is pt between (vertically) p1 and p2?  
    // If so, the ray from pt might intersect.  
    // If not, the ray from pt cannot intersect.
    if ((p1.Y >= pt.Y && p2.Y < pt.Y) || (p1.Y < pt.Y && p2.Y >= pt.Y))
    {
      if (p1.X < pt.X && p2.X < pt.X)
      {
        // If the segment is to the left of pt, then the ray extending leftwards from pt will intersect it.
        intersect = true;
      }
      else
        if ((p1.X < pt.X || p2.X < pt.X))
        {
          // If either end of the segment is to the left of pt, calculate intersection (x only) of the 
          // ray from pt and the segment.  If the intersection (x only) is to the left of pt, then
          // the ray extending leftwards from pt will intersect it.
          double inverseSlope = (p1.X - p2.X) / (p1.Y - p2.Y);
          double intersectionX = (pt.Y - p1.Y) * inverseSlope + p1.X;
          if (intersectionX < pt.X)
          {
            intersect = true;
          }
        }
    }
  }
  return intersect;
}

public static bool PointOnSegment(Position p1, Position p2, Position pt)
{
  // Obviously, this is not really going to tell us if pt is on the segment p1->p2.  I am still
  // working on that.  For testing the PointInPolygon algorithm, I can still simulate the "on"
  // case by passing in a pt that is equal to one of the points on the polygon.
  return (pt == p1 || pt == p2);
}

public static PointInPolygonLocation PointInPolygon(IEnumerable<Position> pts, GTPosition pt)
{
  //
  // Implemention of the Jordan Curve theorem to determine if a point is in a polygon.  In essence,
  // this algorithm extends a ray infinitely from pt.  In my implementation I am extending to the left.
  // If the point is inside the polygon, then the ray will intersect the polygon a odd number of times.
  // If the point is outside the polygon, then the ray will intersect the polygon an even number of times.
  // Ideally, we would be able to report not only if the point is inside or outside of the polygon, but
  // also if it is "on" the polygon (i.e. it lies on one of the segments).  Note that "on" and 
  // inside/outside are exlusive.  The point is either on the polygon or it is inside or outside, it
  // cannot be "inside and on" or "outside and on".
  // So, the algorithm is as follows:
  // 1.  Consider the points of the polygon as pairs making up the segments (p1->p2, p2->p3, etc).
  // 2.  For each segment, perform two calculations:  
  //       Does the ray extending left from pt intersect the segment?
  //       Is pt on the segment p[i], p[i+1]?
  // 3.  Count the total number of intersections.  If odd, point is inside.  If even, point is outside.
  // 4.  Here is the tricky part, if the point is on any segment, then we can stop.  If it is on the 
  //     first segment, then there is no need to go through the on/off calculation and the intersection
  //     calculation for the rest of the segments.
  //
  var result = pts.Pairwise( (p1, p2) =>
                         {
                           int intersect = 0;
                           int on = 0;

                           on = PointOnSegment(p1, p2, pt) ? 1 : 0;
                           if (on == 0)
                           {
                             //Don't really need to determine intersection if we already know that pt is on p1->p2.
                             intersect = PointIntersectSegment(p1, p2, pt) ? 1 : 0;
                           }
                           return new { on, intersect };
                         })
                         .TakeWhileInclusive((item) => item.on == 0) //Only consider segments until (or if) pt is on a segment.
                         .Aggregate((curr, next) => new     //Keep a running total of how many intersections.
                                                    { 
                                                      on = curr.on + next.on, 
                                                      intersect = curr.intersect + next.intersect 
                                                    });
  if (result.on != 0)
  {
    return PointInPolygonLocation.On;
  }
  else
  {
    return result.intersect % 2 == 0 ? PointInPolygonLocation.Outside : PointInPolygonLocation.Inside;
  }
}

Эта функция, PointInPolygon, принимает входную позицию Position, pt, выполняет итерацию по входной последовательности значений положения и использует метод Jordan Curve, чтобы определить, сколько раз луч, простирающийся от pt влево, пересекает многоугольник. Лямбда-выражение выдаст в «сжатый» список 1 для каждого пересеченного сегмента и 0 для остальных. Сумма этих значений определяет, находится ли pt внутри или снаружи многоугольника (нечетное == внутри, четное == снаружи). Пока все хорошо.

Теперь для любых последовательных пар значений положения в последовательности (т. Е. При любом выполнении лямбды) мы также можем определить, является ли pt ON сегментом p1, p2. Если это так, мы можем остановить вычисления, потому что у нас есть ответ.

В конечном счете, мой вопрос заключается в следующем: могу ли я выполнить этот расчет (возможно, с использованием Aggregate?) Так, чтобы мы повторяли последовательность не более 1 раза И можем ли мы остановить итерацию, если встретим сегмент с включенным pt ? Другими словами, если pt включен в самом первом сегменте, нет необходимости проверять остальные сегменты, потому что у нас есть ответ.

Вполне может быть, что эта операция (в частности, требование / желание, возможно, остановить итерацию раньше) не очень хорошо подходит для подхода LINQ.

Мне просто пришло в голову, что, возможно, лямбда-выражение может дать кортеж, значение пересечения (1 или 0 или, может быть, true или false) и значение «on» (true или false). Возможно тогда я мог бы использовать TakeWhile (anontype.PointOnPolygon == false). Если я суммирую кортежи и если ON == 1, то точка находится на многоугольнике. В противном случае, нечетность или четность суммы другой части кортежа говорит, находится ли точка внутри или снаружи.

EDIT Очистили форматирование кода, переместили лямбду в автономную функцию, добавили новую функцию, если точка находится на сегменте. Новая функция действительно пустая, она просто сравнивает входную точку с начальной и конечной точками сегмента и возвращает true, если любой из них равен. Таким образом, он, вероятно, должен называться PointIsOnEndpointOfSegment. Здесь уже много кода, и я не хотел затуманивать проблему с большим количеством дурачения с х и у, чтобы выполнить «настоящий» расчет ON.

С таким кодом, как сейчас, я могу сделать следующее: 1. Просмотр последовательности точек в виде последовательности пар (сегментов) (через Pairwise). 2. В селекторе результатов Pairwise я вычисляю анонимный тип, содержащий значение intersection = 1, если луч, идущий влево от pt, пересекает сегмент, и значение on = 1, если точка находится «на» сегменте. 3. Выразите пересечение / на анонимных типах как последовательность.

Я думал, что мог бы использовать TakeWhile, чтобы взять все анонимные типы, пока (или если) один из анонимных типов не покажет, что pt был включен сегментом. Затем, используя Aggregate, суммируйте значения пересечения и далее. Если сумма по! = 0, то точка находилась на одном из отрезков. В противном случае сумма пересечения скажет нам, находится ли точка внутри (нечетная) или снаружи (четная или нулевая).

К сожалению, я столкнулся с подобной проблемой с TakeWhile, как было описано здесь:

Как взять ПЛЮС еще один элемент .

My TakeWhile принимает все элементы от последовательности до, но не включая элемент (если есть), который указывает на пересечение. Поэтому, когда я объединяю результаты, пересекающегося элемента там нет.

Похоже, одним из способов, с помощью которого люди обрабатывали эту ситуацию раньше, было написание расширения TakeUntil, подобного TakeWhile, но оно включает первый элемент, который не соответствует предикату. Будет ли такое расширение TakeUntil вызывать оценку всей последовательности?

В основном это было упражнение, чтобы увидеть, может ли этот алгоритм быть реализован с использованием Linq с учетом следующих требований: 1. Вся последовательность входных точек повторяется ТОЛЬКО, если входная точка НЕ ​​находится ни на одном из сегментов. 2. Если точка входа находится на одном из сегментов, итерация точек ввода должна быть остановлена. Если входная точка находится на первом сегменте многоугольника в 1000 точек, нет необходимости выполнять вычисления пересечения и «включения» для остальных сегментов.

Мы реализовали этот алгоритм ранее в C ++, используя цикл for для точек, прерывая, если точка когда-либо находится на сегменте. Я, конечно, мог бы реализовать тот же способ, я просто хотел посмотреть, смогу ли я LINQify, если не вызову больше взаимодействий, чем «старый» путь цикла.

Я, вероятно, попробую подход TakeUntil только для ударов и посмотрю, что произойдет.

Редактировать

С этим кодом (TakeWhileInclusive IEnumerable, который практически идентичен TakeUntil, описанному в ссылке о TakeWhile PLUS, еще один элемент):

// Mimic TakeWhile's overload which takes an index as a parameter to the predicate.
public static IEnumerable<T> TakeWhileInclusive<T>(this IEnumerable<T> seq, Func<T, int, bool> predicate)
{
  int i = 0;
  foreach( T e in seq)
  {
    if (!predicate(e,i))
    {
      // If here, then this is first item to fail predicate.  Yield this item and then break.
      yield return e;
      yield break;
    }
    // yield each item from the input sequence until end of sequence or first failure (see above).
    yield return e;
    i++;
  }
}

//
// First saw this here: http://blog.foxxtrot.net/2009/06/inclusively-take-elements-using-linq-and-custom-extensions.html
// TakeWhileInclusive - IEnumerable extension to mimic TakeWhile, but also to return the first
// item that failed the predicate.
// e.g.  seq = 1 2 3 4
// TakeWhile(p => p != 3) will yield 1 2
// TakeWhileInclusive(p => p != 3) will yield 1 2 3
// e.g.  seq = 0 0 0 1 0
// TakeWhile(p => p == 0) will yield 0 0 0
// TakeWhileInclusive(p => p == 0) will yield 0 0 0 1
// Similar to TakeUntil from here: /1787865/kak-ya-mogu-vzyat-esche-1-predmet-iz-takewhile-linka
//
public static IEnumerable<T> TakeWhileInclusive<T>(this IEnumerable<T> seq, Func<T, bool> predicate)
{
  return seq.Select((x, i) => new { Item = x, Index = i })
            .TakeWhileInclusive((x, i) => predicate(x.Item))
            .Select(x => x.Item);
}

И соответствующее изменение в моем исходном коде (замените TakeWhile на TakeWhileInclusive), я могу получить ответ (либо точка находится на многоугольнике, либо она находится внутри или снаружи), и итерация останавливается (через TakeWhileInclusive) после того, как она достигает сегмент многоугольника, на котором точка включена. Еще раз отмечу, что мой код «PointOnSegment» является поддельным, но он подходит для тестирования, пока я проверяю точку, равную одной из точек многоугольника.

Я оставлю это на время, если кто-то еще захочет прокомментировать. Прямо сейчас я склонен принять свой собственный ответ, поскольку он делает то, что я намеревался сделать. Является ли этот конкретный подход в конечном итоге хорошим, я пока не знаю.

Answer 1

Я не совсем понимаю сам алгоритм, но думаю, что смогу помочь:
Что вам в основном нужно, предполагая, что я так много понимаю, так это проверить, соответствует ли какой-либо из кортежей определенному предикату. Затем вы можете поместить каждую пару позиций в кортеж и передать ее как IEnumerable<Tuple<Position, Position>>, на которой вы можете сделать. Любой (предикат идет сюда), чтобы посмотреть, соответствует ли какая-либо из них описанию (или, если вам нужно значение, для которого предикат был истинным, используйте .FirstOrDefault () и отметьте ноль)
Итак, ваш код будет выглядеть примерно так:

   public static PointInPolygonLocation PointInPolygon(IEnumerable<Position> pts, Position pt)
    {
        bool isIn = pts.Pairwise((p1, p2) => Tuple.Create(p1, p2)).Any(tuple => tuple.Item1.Y != tuple.Item2.Y &&
        ((tuple.Item1.Y >= pt.Y && tuple.Item2.Y < pt.Y) || (tuple.Item1.Y < pt.Y && tuple.Item2.Y >= pt.Y))
        && ((tuple.Item1.X < tuple.Item1.X && tuple.Item2.X < pt.X) || ((pt.Y - tuple.Item1.Y) * ((tuple.Item1.X - tuple.Item2.X) / (tuple.Item1.Y - tuple.Item2.Y)) * tuple.Item1.X) < pt.X));
        return isIn ? PointInPolygonLocation.Inside : PointInPolygonLocation.Outside;
    }

Я бы серьезно подумал добавить несколько комментариев к этому чудовищному предикату. Я как бы застегнул молнию. вложенные ifs превратились в && s и т. д. Вы, конечно, должны это проверить, но я на 90% уверен, что это то же самое, что и вы. Процитировать кнут: Beware of bugs in the above code; I have only proved it correct, not tried it.

Редактировать: Гораздо более читабельно, не правда ли?

   public static PointInPolygonLocation PointInPolygon(IEnumerable<Position> pts, Position pt)
    {
        bool isIn = pts.Pairwise((p1, p2) => Tuple.Create(p1, p2)).Any(tuple => ReadablePredicate(tuple.Item1, tuple.Item2, pt));
        return isIn ? PointInPolygonLocation.Inside : PointInPolygonLocation.Outside;
    }
    public static bool ReadablePredicate(Position p1, Position p2, Position pt)
    {
        if (p1.Y == p2.Y)
            return false;
        if (!((p1.Y >= pt.Y && p2.Y < pt.Y) || (p1.Y < pt.Y && p2.Y >= pt.Y)))
            return false;
        if (p1.X < pt.X && p2.X < pt.X) // Originally was (p1.X < p1.X && ...). that makes no sense, so I assumed you meant p1.X < pt.X
            return true;
        if ((p1.X < pt.X || p2.X < pt.X) && ((pt.Y - p1.Y) * ((p1.X - p2.X) / (p1.Y - p2.Y)) * p1.X) < pt.X)
            return true;
        return false;
    }

Answer 2

Я прошел через несколько итераций (ха-ха) этой проблемы. В итоге было два ключа:

1. Моя функция выбора результата вычисляет два значения на сегмент многоугольника. Пересекает ли луч, идущий влево от точки, отрезок? (1 или 0, чтобы облегчить суммирование через Aggregate позже). Точка на сегменте? (1 или 0, чтобы облегчить суммирование через Aggregate позже). Если точка на сегментном значении равна 1 (точка на сегменте), итерация должна остановиться.

2. Поскольку я хочу перебирать как можно меньше элементов, мне нужно ограничить последовательность в случае точки, находящейся на отрезке. Если дело не в каком-либо сегменте, у меня нет выбора, кроме как перебирать все сегменты. Если точка находится в сегменте, я хочу выйти, но мне также нужно объединить это последнее значение (что привело к сбою условия «итерация до точки в сегменте»). Я думал, что TakeWhile будет работать так же, как и пары {intersect, on}, пока == 1 (то есть до тех пор, пока точка не окажется на отрезке). К сожалению, TakeWhile обнаруживает это условие и останавливает итерацию, но мой вывод (который передает в Aggregate) не содержит условие «сбой», поэтому результаты Aggregate to не отражают, что точка была в сегменте.

Я подумал, что если бы я выполнил это через LINQ, мне пришлось бы выполнить итерацию по всей последовательности, а затем проверить результаты (совокупности), чтобы определить, попала ли точка в какой-либо из сегментов, над которыми я просто итерацию. Используя метод расширения TakeWhileInclusive, вдохновленный / скопированный из поста, указанного выше, и с веб-сайта, не принадлежащего SO, отмеченного в комментарии в коде, я могу получить необходимое мне поведение TakeWhile + 1.

Может быть, есть лучший способ сделать это? Я не знаю. Я действительно только начинаю. Парный шаблон хорошо работает для многих геометрических вычислений, которые включают последовательности точек. При заданной последовательности точек и алгоритме, выраженном в виде пар точек (p1-> p2, p2-> p3, p3-> p4 и т. Д.), Это может быть просто вопрос выражения алгоритма в лямбде (простые, такие как Расстояние) или в автономной функции (как в этом посте, Centroid и т. д.).

Я оставлю это на время, если кто-то еще захочет прокомментировать или внести предложения или предложить альтернативные ответы. В конечном счете, я, вероятно, приму этот ответ (как указано в дополнительном коде и комментариях в исходном вопросе.