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

Как-то появилась потребность определять принадлежность точки много угольнику. Естественно, прежде чем браться за разработку своего алгоритма было бы неплохо познакомиться с наработками в решении этой задачи. Что и сделал. полез в интернет. Одно из решений подобной задачи — метод трассировки луча. Купился я на посулы … Потратил рабочий день на него, прежде, чем понял насколько он глючный.

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

Утилита отмечает координаты мыши красным если false = точка вне многоугольника и зелёным (true), если «очень быстрый алгоритм» решает, что точка внутри многоугольника. Как видно из скриншота, в некоторых областях алгоритм врёт.

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

 Вывод один — «очень быстрый алгоритм» очень глючный. Глючит на горизонтальных участках многогранника (трассировочный луч идёт по горизонтали вправо).

Пробуем простой (не быстрый) алгоритм трассировки луча:

Вроде бы всё прекрасно, но:

опять же часть точек внутри и снаружи многоугольника обрабатывает неверно.

Другая фигура:

Слева вверху область обработана неверно.
Для большинства случаев сойдёт, но мне надо 100% уверенность, в принадлежности точки многоугольнику или не принадлежности. Поэтому делаем лёгкий «плевок» в сторону авторов подобного алгоритма с такими ошибками и быстренько пишем свой алгоритм со 100%-й точностью.

Успехов!

P.S.: Не всё что в сети — золото.

2 thoughts on “Задача о принадлежности точки многоугольнику”

  1. Здравствуйте. Нашел в интернете delphi-проект подобно тематики (содержится по ссылке: http://www.mathros.net.ua/perevirka-prynalezhnosti-tochky-bagatokutnyku.html). Реализует алгоритм трассировок луча. Подскажите пожалуйста, каким образом можно проверить правельнисть работы данного проекта? Хотелось чтобы при сдаче курсовой у преподавателя не возникало лишних вопросов.

    1. Алгоритм трассировок луча глючный. Он работает не со 100%-й точностью — см. в моей заметке/статье.
      Правильность реализации этого алгоритма (размещённого по вашей ссылке) вы можете проверить, написав программу на каком-нибудь языке программирования доступном вам.
      Я тут помочь вам не смогу (читаю только по-русски и по-английски).

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *