Обнаружение цикла, заданного отрезками линии

Question

Я работаю над реализацией алгоритма декомпозиции Slab, для point location, и я застрял на одном из его заключительных шагов. У меня есть список вершин, а также список соседей вершин (например, сосед [0] имеет все вершины, которые связаны с вершиной 0). Я могу создать плиты, описанные в алгоритме, просто отлично, но после того, как я обнаружил, между точками линии есть точка, я не знаю, как получить весь раздел/цикл/грань, в которой находится точка.

В принципе , у меня есть этот

И это то, что я хочу

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

Заранее спасибо

Answer 1

Вы можете хранить в planar straight-line graph как doubly connected edge list. Соответствующая функция представления DCEL является то, что базовый объект будет полуребро (каждый сегмент приводит к двум противоположно ориентированным полуреберам, с хвостом и головой) с двумя операциями:

DNext(HalfEdge e) - returns the next half-edge with the same head as e 
        in counterclockwise order around the head 
Sym(HalfEdge e) - returns the oppositely oriented half-edge 
        corresponding to the same edge. 

Тогда вы может выполнять итерацию по полуребрам, содержащим грань, с e = Sym(DNext(e)), пока e не вернется к исходному значению.

Для вычисления представления DCEL в первую очередь необходимо отсортировать полуребра по углу и затем соединить их вместе. Есть способ сравнить углы двух полуребер, используя вычисление определителя 2x2 (избегая арктангенса, если это имеет для вас отношение).