Нахождение того, находится ли отрезок линии полностью внутри многоугольника или нет

Question

Нахождение того, находится ли отрезок линии полностью внутри многоугольника или нет

Как я могу найти, является ли данная диагональ (отрезок, соединяющий две вершины многоугольника, кроме ребра многоугольника) действительной диагональю для данного многоугольника? Я пишу код в ЛЕДА. Есть ли какая-то особая функция в LEDA для проверки диагонали? нужна помощь.

0

algorithm leda

Источник

user2522266 27 окт '13 в 10:29

1 ответ

Решение

Другие вопросы по тегам algorithm leda

user2863401 28 окт '13 в 01:24 2013-10-28 01:24 · Accepted Answer · 2013-10-28 01:24

Вы можете позвонить intersection метод вашего полигона, который будет возвращать пересечения с сегментом. Если есть другие пересечения, кроме двух конечных точек (то есть более двух пересечений), то это недопустимо. Вот объявление функции:

list<POINT> Polygon.intersection(const SEGMENT& s)

ОБНОВЛЕНИЕ: Как указывал j_random_hacker, это может не сработать, если диагональ находится за пределами многоугольника. Для слабо простых многоугольников этого можно избежать, проверяя, находится ли внутренняя точка отрезка за пределами многоугольника.

bool   Polygon.outside(const POINT& p)

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