@Ckworec

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

Доброго времени суток! Решаю задачу на поиск пересечения/объединения двух полигональных областей, заданных множеством точек. Для этого хочу создать копии областей с добавленными в них точками пересечения и при обходе области при обнаружении точки пересечения перескакивать на другую область, в случае объединения, и использовать алгоритм Уайлера — Атертона для поиска пересечения. Функция поиска точки пересечения понятна в большинстве случаев, но не во всех, например если стороны областей пересекаются по отрезку, то как определить какую точку брать в качестве точки пересечения?655f84ee5e5c1564080943.jpeg
В данном случае в многоугольник AIJH должны добавится точки B, K, G и в многоугольник ABCDEFGH должна добавится точка K.
Алгоритм Уайлера — Атертона: https://www.geeksforgeeks.org/weiler-atherton-poly...
  • Вопрос задан
  • 104 просмотра
Пригласить эксперта
Ответы на вопрос 2
wataru
@wataru Куратор тега C++
Разработчик на С++, экс-олимпиадник.
Я бы в таком случае добавлял обе вершины от второго многоугольника, которые лежат на первом. Так все новые ребра каждого многоугольника или целиком не пересекаются со вторым, или целиком лежат внутри него, или целиком на его границе.

Т.е. действительно, в вашем случае надо в AIJH добавить точки ABKJH.

Образуются ребра длины 0 - значит повторяющиеся вершины надо просто выкинуть.
Ответ написан
Комментировать
mayton2019
@mayton2019
Bigdata Engineer
Я обычно договаривался сам с собой что прямоугольник будет включать в себя левую и верхнюю сторону
а правая и нижняя при этом будут считаться не входящей в его площать. На языке математики это как-то так:

( x1 >= x > x2, y1 >= y > y2 )

Это дает возможновть в любых координатах в int, double e.t.c. считать плотно рядышком стоящие
прямоугольники не пересекающимися вообще.
Ответ написан
Комментировать
Ваш ответ на вопрос

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

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