CGAL可见性计算错误的可见性多边形（简单多边形可见性算法）

问题描述

我必须计算给定多边形的某些顶点的可见性多边形。我正在使用CGAL的可见性计算库，但对于及其第35个顶点（以及更多点），以下内容（显然是错误的），其中可见性多边形的一个边缘与原始多边形的一个边缘相交。

I have to compute the visibility polygons of some vertices of a given polygon. I'm using CGALs visibility computation library, but for this example polygon and its 35th vertex (and a few more points), the following (obviously wrong) result is computed, where one edge of the visibility polygon intersects an edge of the original one.

I使用以下代码进行构造：

I used the following code for construction:

typedef CGAL::Arrangement_2<CGAL::Arr_segment_traits_2<Epeck>> Arrangement_2;

Arrangement_2 polygon_arr;
CGAL::insert(polygon_arr, polygon.edges_begin(), polygon.edges_end());

Arrangement_2 vp_output;
CGAL::Simple_polygon_visibility_2<Arrangement_2, CGAL::Tag_false> non_regular_visibility(polygon_arr);


// ci is vertex circulator
Arrangement_2::Halfedge_const_handle preceding_he =
    std::find_if(polygon_arr.halfedges_begin(),polygon_arr.halfedges_end(),
        [&ci](const typename Arrangement_2::Halfedge &e) {
            return !e.face()->is_unbounded() && e.target()->point() == *ci;
         }
);

non_regular_visibility.compute_visibility(*ci, preceding_he, vp_output);
for (auto eit = vp_output.edges_begin(); eit != vp_output.edges_end(); ++eit)
{
    segments.push_back(eit->curve());
}

这是CGALs实现中的错误还是代码中的错误？

Is that a bug in CGALs implementation or is it a bug in my code?

编辑：
将算法更改为
CGAL :: Triangular_expansion_visibility_2< Arrangement_2> tev（polygon_arr）; （l。7）解决了这个问题，所以它可能是CGAL中的错误。

Changing the algorithm toCGAL::Triangular_expansion_visibility_2<Arrangement_2> tev(polygon_arr); (l. 7) solves the problem, so it's probably a bug in CGAL.

推荐答案

您是对的，这是CGAL中的错误。我为此创建了一个问题：

You are right, it is a bug in CGAL. I created an issue for this : https://github.com/CGAL/cgal/issues/4289

这篇关于CGAL可见性计算错误的可见性多边形（简单多边形可见性算法）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！