Нахождение общей внутренней точки для двух полигонов

Question

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

Предполагая, что они перекрываются, и наши многоугольники определяются своими наборами вершин в 3D.

Answer 1

Можно использовать вариант алгоритма отсечения полигонов Ватти. Алгоритм Ватти - это алгоритм линии сканирования, который в основном означает сканирование вершин обоих многоугольников, скажем, слева направо, а также любых пересечений между их границами. Между вертикальными линиями, проходящими через любые два последовательных этих "события", вы затем исследуете трапеции / треугольники, созданные полигонами. Как только вы найдете трапецию, которая является частью обоих, вы можете просто вывести ее центроид.