Сегментация пространства на многоугольные области с приближением Ворони по набору точек

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

Я пытался использовать Boost::Voroni для этой цели, но результат использования этой библиотеки сложен и требует много дополнительных усилий, чтобы получить то, что я хочу.

Мне было интересно, знает ли кто-нибудь, как лучше всего получить то, что я хочу, из диаграммы BOOST::voroni, или знает ли кто-нибудь более простую библиотеку, чем может получить то, что я ищу напрямую?

Вот код, показывающий, что я пытаюсь сделать,

voronoi_diagram< float > vd;
construct_voronoi( gridPointPos.begin(), gridPointPos.end(), &vd );

int index = 0;
for (voronoi_diagram<float>::const_cell_iterator it = vd.cells().begin();
    it != vd.cells().end(); ++it, ++index ) {

    // if the voroni cell has infinite edges,
        // then clip them to a finite length

    // extract the voroni vertices of this cell

    // create a boost polygon from the extracted edges
}

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


c++ boost voronoi boost-polygon
person MVTC    schedule 17.06.2015    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Вы можете попробовать мою реализацию инкрементного алгоритма Бойера-Ватсона для триангуляции Делоне в PHP, он также находит диаграмму Вороного. Его можно загрузить с сайта codeplex.com (http://voronoi.codeplex.com/).

person Gigamegs    schedule 17.06.2015

arrow_upward
0
arrow_downward

У меня был тот же вопрос, но я не мог найти ничего достаточно легкого на мой вкус. Поэтому я создал свою собственную реализацию C (один заголовочный файл), см. https://github.com/JCash/voronoi< /а>

Учитывая массив точек и некоторую функцию draw_triangle:

    jcv_diagram diagram;
    memset(&diagram, 0, sizeof(jcv_diagram));
    jcv_diagram_generate(count, (const jcv_point*)points, width, height, &diagram );

    const jcv_site* sites = jcv_diagram_get_sites( &diagram );
    for( int i = 0; i < diagram.numsites; ++i )
    {
        const jcv_site* site = &sites[i];

        unsigned char color_tri[3] = { 127, 127, 127 };
        const jcv_graphedge* e = site->edges;
        while( e )
        {
            draw_triangle( &site->p, &e->pos[0], &e->pos[1], image, width, height, 3, color_tri);
            e = e->next;
        }
    }

    jcv_diagram_free( &diagram );
person JCash    schedule 23.09.2015