Известны вершины ромба и прямоугольника. Какой наиболее простой и эффективный способ нахождения области их пересечения(координат вершин фигуры, которая одновременно принадлежит и ромбу и прямоугольнику)? Ромб и прямоугольник всегда имеют такую ориентацию, меняются только их размеры и расположение на плоскости(надеюсь, правильно выразился).
Ответ
Для нахождения пересечения произвольных выпуклых многоугольников, особенно если один из них является осеориентированным прямоугольником, прекрасно работает алгоритм последовательного отсечения (Sutherland–Hodgman algorithm).
Вы просто выбираете один из многоугольников в качестве отсекаемого, а затем в цикле последовательно "отрезаете от него все лишнее" прямыми, содержащими стороны второго (отсекающего) многоугольника. В вашем случае естественным решением будет выбрать именно прямоугольник в качестве отсекающего: отсечение горизонтальными и вертикальными прямыми выполняется тривиальным образом.
Комментариев нет:
Отправить комментарий