Пересечение двух выпуклых многоугольников

Ответ 1

For each edge V1-V2 in the first polygon,
    Let H := Half-plane tangenting V1-V2, with the remaining
        vertices on the "inside".
    Let C := New empty polygon.
    For each edge V3-V4 in the second polygon,
        Let X := The intersection between V3-V4 and H.
        If V3 inside H, and V4 is outside H then,
            Add V3 to C.
            Add X to C.
        Else if both V3 and V4 lies outside H then,
            Skip.
        Else if V3 outside H, and V4 is inside H then,
            Add X to C.
        Else
            Add V3 to C.
    Replace the second polygon with C.

Это должно быть достаточно для простого использования; 10-20 вершин и не пересчитывать каждый кадр. — О (п ²)

Вот несколько ссылок:

• Компьютерная графика я – Обрезка и заполнение полигонов (pdf)
• rosettacode.org – Обрезка полигонов Сазерленд-Ходжман

Ответ 2

Вы можете воспользоваться тем, что оба полигона выпуклые. И с помощью этих знаний вы можете достичь времени O (n), используя алгоритм последовательной линии развертки:

Найти точки вершины в обоих многоугольниках. Для простоты предположим, что у вас нет горизонтальных кромок. Создайте списки краев, вносящих левую и правую границы многоугольника.

В то время как вы набрасываетесь, вы сохраняете 4 края. left_edge_C1, right_edge_C1, left_edge_C2, right_edge_C2. Вам не нужен какой-либо комплекс, чтобы рисовать ребра, потому что их всего четыре. Вы можете найти следующую точку события, просто повторяя все возможные варианты.

В каждой точке события на границе их пересечения появляется некоторое ребро. В принципе, в каждой точке события вы можете иметь один из свободных случаев (см. Рис.).

Ответ 3

Кроме того, @Yola nice plane-sweep description, существует алгоритм линейного времени, описанный в Вычислительная геометрия в C, глава 7. И доступен код C и Java (по той же ссылке). Существует несколько сложных дегенеративных случаев, например, когда два полигона пересекаются в точке или пересечение является отрезком.