Проверка принадлежности точки многоугольнику методом луча

Метод трассировки луча (или метод луча) — один из классических методов определения принадлежности точки многоугольнику. Суть метода заключается в следующем: через точку проводится воображаемый луч в каком-либо направлении (например, горизонтально вправо), и считается количество пересечений этого луча с границами многоугольника. Если количество пересечений нечётное, то точка находится внутри многоугольника, иначе — снаружи.

Предположим, что нам необходимо определить принадлежность точки A полигону P. Для этого из некоторой удаленной точки проведем прямую линию в точку A. На этом пути может встретиться нуль или несколько пересечений границы полигона: при первом пересечении мы входим внутрь полигона, при втором — выходим из него, при третьем пересечении снова входим внутрь и так до тех пор, пока не достигнем точки A. Таким образом каждое нечетное пересечение означает попадание внутрь полигона P, а каждое четное — выход из него. Если мы попадаем в точку A с нечетным числом пересечений границы полигона, то точка A лежит внутри полигона, а если получается четное число пересечений, то точка находится вне полигона P.

Например, на рис.1 луч RA пересекает границу только однажды, поскольку единица число нечетное, то точка A находится внутри полигона. Относительно точки B мы придем к заключению, что она лежит вне полигона, поскольку луч RB пересекает границу четное число раз (дважды).


Рис.1. Каждый луч, исходящий из точки A, пересекает границу нечетное число раз, а каждый луч, исходящий из точки B - четное число.

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

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

Относительно горизонтального луча RA, направленного вправо, будем различать три типа ребер полигона:

  1. касательное ребро, содержащее точку A;
  2. пересекающее ребро, не содержащее точку A;
  3. безразличное ребро, которое совсем не имеет пересечения с лучом RA.

Например, на рис. 2 ребро с - пересекающее, ребро d — касательное, а ребро е — безразличное.


Рис.2. Ребро с является пересекающим ребром, ребро d — касательным, ребро е — безразличным.

Весь алгоритм удобно разложить на три функции:

  1. pointlnPolygon решает задачу о принадлежности точки A полигону P.
  2. edgeType - классифицирует тип ребра (касательное, пересекающее, безразличное).
  3. classify - анализирует расположения точки (слева от ребра, справа от ребра, на ребре).
// Задаем многоугольник P координатами вершин
var P = [
  { x: 10, y: 10 },
  { x: 30, y: 30 },
  { x: 50, y: 30 },
  { x: 30, y: 50 },
  { x: 20, y: 40 },
  { x: 10, y: 50 },
]
 
// Задаем проверяемые точки
A = { x: 15, y: 30 }; // Внутренняя точка
B = { x: 45, y: 30 }; // Точка на ребре
C = { x: 5, y: 30 };  // Точка снаружи
 
// Выводим результат проверки в консоль браузера
console.log(pointInPolygon(P, A)); // 1 - Точка внутри
console.log(pointInPolygon(P, B)); // 2 - Точка на ребре
console.log(pointInPolygon(P, C)); // 0 - Точка снаружи
 
// Основная функция проверки принадлежности точки многоугольнику
function pointInPolygon(pol, point) {
  var parity = 0, et;
  // Обход ребер полигона
  for (var i = 0; i < pol.length - 1; i++) {
    // Определяем тип ребра в переменную et: касательное (0), пересекающее (1), безразличное (2)
    et = edgeType(point, pol[i], pol[i + 1]);
    if (et == 0)
      return 2; // Точка на ребре
    else if (et == 1)
      parity = 1 - parity; // Четность
  }
  // Проверка для последнего ребра, соединяющего последнюю вершину с первой
  et = edgeType(point, pol[i], pol[0])
  if (et == 0)
    return 2;
  else if (et == 1)
    parity = 1 - parity;
  return parity;
}
 
// Функция классификации типа ребра
function edgeType(pointA, pointE, pointC) {
  var cl = classify(pointA, pointE, pointC);
  // Если точка A слева от EC
  if (cl > 0) 
    // и внутри отрезка по y, то горизонтальная прямая пересекает грань
    return ((pointE.y < pointA.y) && (pointA.y <= pointC.y)) ? 1 : 2; 
  else
    // иначе, если точка A справа от EC 
    if (cl < 0) 
    // и внутри отрезка по y, то горизонтальная прямая пересекает грань
      return ((pointC.y < pointA.y) && (pointA.y <= pointE.y)) ? 1 : 2; 
    else
      return 0; // Точка на ребре
}
 
// Функция анализа расположения точки
function classify(pointA, pointE, pointC) {
  // Если точка лежит на уровне горизонтального ребра
  if ((pointA.y == pointE.y) && (pointA.y == pointC.y )) {
    // Проверяем ее положение относительно вершин ребра
    if (pointA.x<pointE.x) return 1;  // Точка A слева от ребра EC
    else if (pointA.x>pointC.x) return -1;  // Точка A справа от ребра EC
    else return 0;
  }
  // в остальных случаях
  else {
  // Считаем косое произведение векторов AC и EC
  var pr = (pointA.x - pointC.x) * (pointE.y - pointC.y) - (pointA.y - pointC.y) * (pointE.x - pointC.x);
  if (pr > 0)
    return 1; // Точка A слева от ребра EC
  else if (pr < 0)
    return -1; // Точка A справа от ребра EC
  else 
    return 0; // Точка A на ребре EC
  }
}

Основная функция pointlnPolygon реализовывает алгоритм проверки принадлежности точки A полигону P.

В процессе работы алгоритм производит обход ребер полигона и переключает переменную parity для каждого обнаруженного факта пересечения ребра лучом. Возвращает значение 1, если окончательное значение число пересечений нечетно, или возвращает 0, если - четно. Если обнаруживается касательное ребро, то функция сразу возвращает значение 2 без дальнейшего обхода.

Функция PointInPolygon( Многоугольник pol, Точка point)
1. Четность = 0;
2. Цикл по всем ребрам многоугольника (Начало)
3. Берем очередное ребро
4. Анализируем положение точки относительно этого ребра с помощью функции edgeType
5. Если положение точки КАСАТЕЛЬНОЕ, то ТОЧКА НА РЕБРЕ (конец работы)
6. Если положение точки ПЕРЕСЕКАЮЩЕЕ, то меняем четность.
7. Конец цикла (2).
8. Анализ четности, возвращение результата работы алгоритма, если нечетно то внутри, если четно снаружи.

Функция edgeType(Точка A, Точка E, Точка C) классифицирует положение ребра EC относительно горизонтального луча RA, направленного вправо, возвращая значения касательное(0), пересекающее(1) или безразличное(2). Определение функции edgeType несколько хитроумное, поскольку функция pointInPolygon должна правильно обрабатывать особые ситуации, возникающие при прохождении луча RA точно через вершины.

Рассмотрим рис.3. В случае (а) бит четности должен быть переключен — луч пересекает границу только однажды, хотя при этом на самом деле пересекает два ребра.

В случаях (б) и (в) четность не изменяется. Это может быть достигнуто путем некоторого уточнения схемы классификации ребер:

  • Ребро е — касательное ребро, если оно содержит точку A.
  • Ребро е — пересекающее ребро, если
    (1) ребро е не горизонтальное и
    (2) луч RA пересекает ребро е в некоторой точке, отличающейся от его нижней конечной точки.
  • Ребро е — безразличное, если оно не касательное и не пересекающее.

Рис.3. Специальные случаи: (а) и (г) — переменная parity переключается однажды; (6) и (д) - parity не изменяется, (в) и (е) — parity переключается дважды и ситуация остается без изменения

Обращаясь к рис.3, мы можем видеть, что в случае (а) переменная parity должна переключиться однажды, в случае (б) parity не изменяется, в случае (в) parity переключается дважды и ситуация остается без изменения.

Заметим, что горизонтальное ребро, не включающее точку A, считается безразличным и оно игнорируется функцией pointInPolygon. Поэтому случаи (г), (д) и (е) обрабатываются точно так же, как соответствующие случаи (а), (б) и (в).

Функция edgeType(Точка A, Точка E, Точка C)
1. Вызываем функцию classify анализа расположения точки A относительно ребра EC
3. Если точка A слева от ребра EC: ребро ПЕРЕСЕКАЕТСЯ, если Точка A находится в проекции Y ребра CE, в противном случае БЕЗРАЗЛИЧНО.
4. Если точка A справа от ребра EC: ребро ПЕРЕСЕКАЕТСЯ, если Точка A находится в проекции Y ребра EC, в противном случае БЕЗРАЗЛИЧНО.
5. Если точка совпадает с точками E,C или лежит на отрезке, то ребро КАСАТЕЛЬНОЕ
6. Во всех остальных случаях БЕЗРАЗЛИЧНО

Направление: 
Вычислительная геометрия