6

Допустим есть многоугольник из N (и это главное) вершин. И есть точка в произвольном месте. Необходимо определить принадлежит она ему или нет. Точки представлены в виде структуры:

struct point{ unsigned int x; unsigned int y;};

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

Я остановился на идеи подсчитать сколько сторон луч выпущенный из точки пройдет. если четное число - не в многоугольнике. если не четное - в многоугольнике. То есть нам надо указывать вершины по часовой стрелке. Сделать структуру сторон. Но как проверять? Как расчитать эти стороны и сделать пересечение?

2 ответа 2

12

Плохо ищете.

bool result = false;
int j = size - 1;
for (int i = 0; i < size; i++) {
    if ( (p[i].Y < point.Y && p[j].Y >= point.Y || p[j].Y < point.Y && p[i].Y >= point.Y) &&
         (p[i].X + (point.Y - p[i].Y) / (p[j].Y - p[i].Y) * (p[j].X - p[i].X) < point.X) )
        result = !result;
    j = i;
}
  • p - список точек
  • size - количество точек
  • result - входит ли точка в многоугольник

Первая строка условия проверяет попадание point.Y между значениями p[i].Y и p[j].Y, контролирует направление прохода вершины и обеспечивает ненулевой знаменатель основной формулы.

Вторая строка проверяет нахождение стороны p[i]p[j] слева от точки point.

Третья строка формирует отрицательный ответ при чётном количестве сторон слева и положительный — при нечётном.

5
  • А есть какой либо еще способ? 8 ноя 2015 в 17:20
  • @ParanoidPanda Вроде, всегда этот используют. Можно оптимизировать, заранее вычислив описывающую фигуру (прямоугольник), тогда большинство проверок будет быстрыми.
    – Kyubey
    8 ноя 2015 в 17:23
  • данный способ основывается не на "выпуске луча" на сколько я понимаю 8 ноя 2015 в 17:24
  • 1
    @ParanoidPanda Горизонтальный луч же, если мне не изменяет зрение.
    – Kyubey
    8 ноя 2015 в 17:34
  • 1
    ru.wikibooks.org/wiki/…
    – vovkas
    18 ноя 2017 в 13:49
4

Пусть луч направлен горизонтально вправо.

Для каждой пары смежных точек:

  1. Сначала проверяете, лежит ли пара точек (краев отрезка) по одну сторону луча. Если по одну сторону - то луч не пересекает сторону.
  2. Если по разные стороны - нужно найти точку пересечения луча и прямой, проходящей через две данные точки. Это аналитическая геометрия, по сути, решение приводить не буду. Если точка пересечения правее точки, откуда исходит луч - значит пересечение есть.

Нужно учитывать специальный случай, когда луч проходит через вершину многоугольника:

  1. Если вторые точки обоих отрезков, которым принадлежит данная вершина находятся по одну сторону от луча, то считать это двумя пересечениями (или отсутствием пресечения - четность будет та же)
  2. Если вторые точки по разные стороны луча - считать одним пересечением.

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

1
  • Ещё к специальному случаю относится сторона целиком лежащая на луче
    – sercxjo
    10 окт 2016 в 5:42

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.