Различие простого выпуклого и простого невыпуклого многоугольника

Question

Для двух простых многоугольников P и Q, где P выпуклый, а Q нет, как быстро можно вычислить разницу $P - Q$ между P и Q, если P имеет n, а Q имеет m вершин?

Можно предположить, что полигоны заданы в виде списка вершин, упорядоченных по часовой стрелке.

Answer 1

"Как быстро" зависит от множества параметров, поэтому я думаю, что сначала мы должны начать с того, как это сделать.

Во-первых, я предполагаю, что многоугольники лежат на одной плоскости. Начните с вычисления конечного пересечения каждой линии P с каждой линией Q. Если пересечение существует и точка пересечения лежит на пересекающихся линиях (я имею в виду между началом и концом, а не на них), разделите линию на две и продолжите конечную линию- пересечения линий итеративно. Затем классифицируйте каждый сегмент линии (теперь я могу назвать их как сегмент, потому что они все разделены, если необходимо), используя точку в расчете многоугольника со средними точками сегментов.. Внутренний, Внешний или OnthePolygon... После категоризации создайте новый многоугольник из линий P, лежащих за пределами Q, и линий Q, лежащих внутри P. Здесь ваша задача будет касаться допусков и линий, лежащих друг на друге... На первый взгляд, общий алгоритм выглядит следующим образом..

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