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

Объясните как реализуется метод углов и что это такое ?
  • Вопрос задан
  • 342 просмотра
Пригласить эксперта
Ответы на вопрос 2
ManWithBear
@ManWithBear
Swift Adept, Prague
Прочитайте вот эту статью: https://habrahabr.ru/post/144921/
Должно стать понятнее.
Ответ написан
Комментировать
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Я так понимаю, что это метод "подсчитать, сколько оборотов делает многоугольник вокруг точки".
Для этого берем каждое ребро многоугольника (в каком-то порядке обхода, т.е. каждая точка для одного ребра первая, для другого - вторая), и считаем под каким углом этот отрезок виден из точки. Важный трюк тут - угол со знаком. Т.е. +30 градусов, если отрезок идет от первой точки ко второй против часовой стрелки, и -30, если точно такой же отрезок развернут.

Для этого нужно взять векторное и скалярные произведения векторов на точки - это будут синус и косинус угла, умноженные на длины векторов. Их, даже не деля на длины, можно передать в функцию atan2(), и она даст вам значение угла. уже с правильным знаком. Хотя можно подстраховаться - угол должен быть от -пи до +пи. Если он больше пи, то нужно вычесть из него 2пи, если меньше -пи, то прибавить.

Все эти углы просто суммируем. Если точка лежит снаружи, то ответ будет 0. Если точка внутри, то ответ будет +-2пи. Если точка лежит на границе - то черт его знает, но этот случай легко обнаружить. Если какой-то из суммируемых углов равен +-пи, то точка на отрезке. Еще отдельно надо бы проверить случай, что точка совпала с одной из вершин многоугольника. Там будет нулевой вектор, и atan не сработает.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы