Область пересечения ромба и прямоугольника

#алгоритм #математика #геометрия

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


    

Ответы

Ответ 1

Для нахождения пересечения произвольных выпуклых многоугольников, особенно если один
из них является осеориентированным прямоугольником, прекрасно работает алгоритм последовательного
отсечения (Sutherland–Hodgman algorithm). 

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


Ответ 2

Результат может быть выпуклым многоугольником с количеством вершин от 0 до 8. Чтобы
не анализировать все возможные случаи, можно использовать общий алгоритм пересечения
выпуклых многоугольников O'Rourke из книги Computational Geometry in C. 

Здесь есть ссылка на исходники. Результат - последовательность вершин в порядке обхода.

Если вероятность пересечения невелика, то вначале стоит проверить сам факт пересечения
(например, с помощью SAT - метода separating axes)