Как извлечь ребра из графика сегмента delaunay в CGAL?

Question

Мне нужно найти медиальную ось вогнутого многоугольника с отверстиями. Я использую CGAL. Мой текущий подход:

1. Построить 2D segment delaunay graph полигона
2. Извлечь результирующие выходные сегменты (биссектрисы)
3. Тестовые каждый сегмент, чтобы найти, если он находится внутри многоугольника
4. Результирующий набор сегментов будет сформировать медиальную ось многоугольника

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

Как это сделать? Я даже на правильном пути?

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

Answer 1

Вы можете использовать функции draw_dual() или draw_skeleton(). Дуга параболы будет аппроксимирована сегментами. Вы можете посмотреть на реализацию метода, если вам нужно больше контроля над выходом.

Вы можете использовать этот класс для сбора объектов:

struct Collector 
{ 
    std::vector<Ray_2> rays; 
    std::vector<Line_2> lines; 
    std::vector<Segment_2> segs; 

    void operator<<(const Ray_2& p){rays.push_back(p);} 
    void operator<<(const Line_2& p){lines.push_back(p);} 
    void operator<<(const Segment_2& p){segs.push_back(p);} 
};