Получить номера вершин пересечения полигонов CGAL - PullRequest
Новая
       7

Получить номера вершин пересечения полигонов CGAL

0 голосов
/ 04 марта 2019

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

Таким образом, у меня есть многоугольник P и Q при t = 0, это должно дать мне номер вершины [1,2,3] дляP и [2] для многоугольника Q, см. Изображение для пояснения.При t = 1 я бы получил [1,2] для P и [2] для Q.

Intersecting polygons at two timesteps

В настоящее время я сначала получаю пересечение и затемдля обоих полигонов проведите цикл по вершинам и используйте функцию has_on_boundary, чтобы определить, является ли она частью пересечения, и сохраните номер вершины.См. Код: 

//Standard Includes
#include <iostream>
using std::cout;
using std::endl;

//Include CGAL options
#define CGAL_HEADER_ONLY 1 //Defining to use the CGAL library as header only
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Boolean_set_operations_2.h>
#include <CGAL/Constrained_Delaunay_triangulation_2.h>

//Typedefs for CGAL Uses.
typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef Kernel::Point_2                                 Point_2;
typedef CGAL::Polygon_2<Kernel>                         Polygon_2;
typedef CGAL::Polygon_with_holes_2<Kernel>              Polygon_with_holes_2;
typedef std::vector<Polygon_with_holes_2>               Pwh_list_2;

int main() {
    Polygon_2 P;
    P.push_back(Point_2(-1, 1));
    P.push_back(Point_2(-0.01, -1));
    P.push_back(Point_2(0, -1));
    P.push_back(Point_2(0.01, -1));
    P.push_back(Point_2(1, 1));

    Polygon_2 Q;
    Q.push_back(Point_2(-1, -1));
    Q.push_back(Point_2(1, -1));
    Q.push_back(Point_2(0, 1));

    Pwh_list_2 polygon_intersections;
    CGAL::intersection(P, Q, std::back_inserter(polygon_intersections));
    //For ease now only assume one intersection
    Polygon_2 intersection = polygon_intersections[0].outer_boundary();

    //Get vertex number of P in intersection
    int vertex_nr = 0;
    std::set<int> overlapping_vertices_P;
    cout << "Find intersection vertices of Polygon P" << endl;
    for (auto it = P.vertices_begin(); it != P.vertices_end(); ++it, ++vertex_nr)   {
        if (intersection.has_on_boundary(*it)) {
            overlapping_vertices_P.insert(vertex_nr);
            cout << vertex_nr << endl;
        }
    }

    //Get vertex number of Q in intersection
    vertex_nr = 0;
    std::set<int> overlapping_vertices_Q;
    cout << "Find intersection vertices of Polygon Q" << endl;
    for (auto it = Q.vertices_begin(); it != Q.vertices_end(); ++it, ++vertex_nr)   {
        if (intersection.has_on_boundary(*it)) {
            overlapping_vertices_Q.insert(vertex_nr);
            cout << vertex_nr << endl;
        }
    }
    return 0;
}

Вопрос: Это работает, но мне кажется очень неэффективным.Есть ли лучший способ сделать это?

Любая помощь или предложения высоко ценятся.

...