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