пересечение сегмент-полигон

Question

Привет,

Я бы хотел определить, касается ли сегмент только многоугольника или пересекает его.

Фигура

объясняет мое сомнение. Как узнать разницу между случаями A и B? Обратите внимание, что в обеих ситуациях красная линия пересекает многоугольники в двух вершинах, одна из которых касается снаружи, а другая - внутри. У меня есть алгоритм пересечения сегмент-сегмент, но я не знаю, как его правильно использовать. Любая помощь приветствуется.

Answer 1

Я думаю, что не может быть более простого подхода, чем вычисление деталей на низком уровне. Во-первых, вам понадобится надежный код для вычисления пересечения между двумя сегментами. Это обсуждается (с кодом) здесь . Как только у вас есть точки пересечения, вам нужно вычислить, как граница многоугольника взаимодействует с вашим сегментом в окрестностях тех точки пересечения. Это по сути повторил LeftOf( ) вычисления, используя обозначения в моей книге. На вашем изображении сегмент проходит через вершину b , а соседние вершины a и c (в последовательной последовательности ( a, b, c )) оба находятся на одной стороне b . Следовательно, сегмент не проникает внутрь полигона в окрестности b . Но если a и c были на противоположных сторонах сегмента, то он должен проникнуть.

Answer 2

Обобщая, пересечение может содержать много точек.Например, см. http://cagd.cs.byu.edu/~557/text/ch7.pdf, в котором обсуждается, как пересекаются плоские кривые, и говорится, что касательные кривые пересекаются в двух точках, «правильно подсчитанных», что противоречит интуиции.В случае выпуклого многоугольника с линией выпаса, есть ли на пересечении две точки, «правильно подсчитанные»?В вашем случае, есть два пересечения с двумя точками в каждом?

Итак, проф. О'Рурк дает алгоритм для вычисления, так сказать, количества точек в пересечении.Прагматически, должен ли пакет для вычисления пересечений возвращать количество точек в каждом пересечении?