Гео-Ограждение - указывает на внутренний/внешний полигон

Касание kobers отвечает, что я разработал его с большим количеством читаемого чистого кода и изменил долготы, который пересекает границу даты:

public bool IsPointInPolygon(List<PointPosition> polygon, double latitude, double longitude)
{
  bool isInIntersection = false;
  int actualPointIndex = 0;
  int pointIndexBeforeActual = polygon.Count - 1;

  var offset = calculateLonOffsetFromDateLine(polygon);
  longitude = longitude < 0.0 ? longitude + offset : longitude;

  foreach (var actualPointPosition in polygon)
  {
    var p1Lat = actualPointPosition.Latitude;
    var p1Lon = actualPointPosition.Longitude;

    var p0Lat = polygon[pointIndexBeforeActual].Latitude;
    var p0Lon = polygon[pointIndexBeforeActual].Longitude;

    if (p1Lon < 0.0) p1Lon += offset;
    if (p0Lon < 0.0) p0Lon += offset;

    // Jordan curve theorem - odd even rule algorithm
    if (isPointLatitudeBetweenPolyLine(p0Lat, p1Lat, latitude)
    && isPointRightFromPolyLine(p0Lat, p0Lon, p1Lat, p1Lon, latitude, longitude))
    {
      isInIntersection = !isInIntersection;
    }

    pointIndexBeforeActual = actualPointIndex;
    actualPointIndex++;
  }

  return isInIntersection;
}

private double calculateLonOffsetFromDateLine(List<PointPosition> polygon)
{
  double offset = 0.0;
  var maxLonPoly = polygon.Max(x => x.Longitude);
  var minLonPoly = polygon.Min(x => x.Longitude);
  if (Math.Abs(minLonPoly - maxLonPoly) > 180)
  {
    offset = 360.0;
  }

  return offset;
}

private bool isPointLatitudeBetweenPolyLine(double polyLinePoint1Lat, double polyLinePoint2Lat, double poiLat)
{
  return polyLinePoint2Lat <= poiLat && poiLat < polyLinePoint1Lat || polyLinePoint1Lat <= poiLat && poiLat < polyLinePoint2Lat;
}

private bool isPointRightFromPolyLine(double polyLinePoint1Lat, double polyLinePoint1Lon, double polyLinePoint2Lat, double polyLinePoint2Lon, double poiLat, double poiLon)
{
  // lon <(lon1-lon2)*(latp-lat2)/(lat1-lat2)+lon2
  return poiLon < (polyLinePoint1Lon - polyLinePoint2Lon) * (poiLat - polyLinePoint2Lat) / (polyLinePoint1Lat - polyLinePoint2Lat) + polyLinePoint2Lon;
}

На сегодняшний день лучшее объяснение и реализацию можно найти на Точка во включении числа обмоток многоугольника

В конце хорошо объясненной статьи есть даже реализация на C ++. Этот сайт также содержит несколько отличных алгоритмов / решений для других проблем, основанных на геометрии.

Я модифицировал и использовал реализацию C ++, а также создал реализацию C #. Вы определенно захотите использовать алгоритм числа витков, поскольку он более точен, чем алгоритм пересечения границ, и очень быстр.

Если у вас есть простой многоугольник (ни одна из линий не пересекается) и у вас нет отверстий, вы также можете триангулировать многоугольник, что вы, вероятно, собираетесь сделать в любом случае в приложении ГИС, чтобы нарисуйте ИНН, затем проверьте наличие точек в каждом треугольнике. Если у вас небольшое количество ребер многоугольника, но большое количество точек, это быстро.

Для интересной точки в треугольнике см. текст ссылки

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

Проблема будет проще, если ваш многоугольник выпуклый. Если это так, вы можете провести простой тест для каждой линии, чтобы увидеть, находится ли точка внутри или за пределами этой линии (простираясь до бесконечности в обоих направлениях). В противном случае для вогнутых многоугольников нарисуйте воображаемый луч от точки до бесконечности (в любом направлении). Подсчитайте, сколько раз он пересекает границу. Нечетный означает, что точка находится внутри, четный означает, что точка находится снаружи.

Этот последний алгоритм сложнее, чем кажется. Вы должны быть очень осторожны с тем, что произойдет, когда ваш воображаемый луч точно попадет в одну из вершин многоугольника.

Если ваш воображаемый луч идет в направлении -x, вы можете выбрать только подсчет строк, которые включают хотя бы одну точку, Координата y строго меньше координаты y вашей точки.

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

Если ответ нечетный, вы внутри. Если ответ четный, значит, вы на улице.

Edit: Да, что он сказал ( Wikipedia ):

Check if a point is inside a polygon or not -

Consider the polygon which has vertices a1,a2,a3,a4,a5. The following set of steps should help in ascertaining whether point P lies inside the polygon or outside.

Compute the vector area of the triangle formed by edge a1->a2 and the vectors connecting a2 to P and P to a1. Similarly, compute the vector area of the each of the possible triangles having one side as the side of the polygon and the other two connecting P to that side.

For a point to be inside a polygon, each of the triangles need to have positive area. Even if one of the triangles have a negative area then the point P stands out of the polygon.

In order to compute the area of a triangle given vectors representing its 3 edges, refer to http://www.jtaylor1142001.net/calcjat/Solutions/VCrossProduct/VCPATriangle.htm