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

Question

Приветствия,

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

Фигура

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

Answer 1

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

Answer 2

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

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