Arrangement_2 produces self-intersecting outer ccb.

[pentacular]

Issue Details

Given the set of segments provided, the arrangement produces a face with a self-intersection.

The output of running the below program locally is:

CGAL Version: 5.5.1
outer_ccb produced non-simple polygon
[22.6099, 87.6822],
[-28.6321, 67.9523],
[-12.4005, 24.8937],
[-27.6534, 66.5174],
[-27.6622, 66.5409],
[-27.6648, 66.5486],
[-27.6534, 66.5174],
[21.0261, -62.9908],
[21.0426, -63.8227],
[21.2151, -64.2804],

Note that [-27.6534, 66.5174] occurs twice.

See also: #7597

Source Code

#include <fstream>
#include <iostream>

#include <CGAL/Arrangement_2.h>
#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Polygon_2.h>

typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef CGAL::Arr_segment_traits_2<Kernel> Traits_2;
typedef CGAL::Arrangement_2<Traits_2> Arrangement_2;
typedef Kernel::Point_2 Point_2;
typedef Kernel::Segment_2 Segment_2;
typedef CGAL::Polygon_2<Kernel> Polygon_2;

#define XSTR(x) #x
#define STR(x) XSTR(x)

int main() {
  std::cout << "CGAL Version: " << STR(CGAL_VERSION) << std::endl;

  std::vector<Segment_2> segments {
    {{21.2151, -64.2804}, {22.6099, 87.6822}},
    {{22.6099, 87.6822}, {-28.6321, 67.9523}},
    {{-28.6321, 67.9523}, {21.2151, -64.2804}},
    {{21.0261, -62.9908}, {-27.6622, 66.5409}},
    {{-27.6622, 66.5409}, {-27.6648, 66.5486}},
    {{-27.6648, 66.5486}, {21.0959, -66.5148}},
    {{21.0959, -66.5148}, {21.0261, -62.9908}},
  };

  Arrangement_2 arrangement;
  insert(arrangement, segments.begin(), segments.end());
  for (Arrangement_2::Face_const_iterator face = arrangement.faces_begin();
       face != arrangement.faces_end(); ++face) {
    if (face->is_unbounded() || face->is_fictitious()) {
      continue;
    }
    Polygon_2 polygon;
    Arrangement_2::Ccb_halfedge_const_circulator start = face->outer_ccb();
    Arrangement_2::Ccb_halfedge_const_circulator edge = start;
    do {
      polygon.push_back(edge->source()->point());
    } while (++edge != start);
    if (!polygon.is_simple()) {
      std::cout << "outer_ccb produced non-simple polygon" << std::endl;
      for (const Point_2 point : polygon) {
        std::cout << "[" << point.x() << ", " << point.y() << "],"  << std::endl;
      }
      exit(1);
    }
  }
  std::cout << "All outer_ccb produced simple polygons" << std::endl;
  exit(0);
}

Environment

• Operating system (Windows/Mac/Linux, 32/64 bits): Linux 32 bit
• Compiler: g++
• Release or debug mode: Debug
• Specific flags used (if any): -lgmp -lmpfr
• CGAL version: 5.2.1
• Boost version:
• Other libraries versions if used (Eigen, TBB, etc.):

[pentacular]

FWIW, I've just replicated this with the current master.

CGAL Version: 6.0-I-900
outer_ccb produced non-simple polygon
[22.6099, 87.6822],
[-28.6321, 67.9523],
[-12.4005, 24.8937],
[-27.6534, 66.5174],
[-27.6622, 66.5409],
[-27.6648, 66.5486],
[-27.6534, 66.5174],
[21.0261, -62.9908],
[21.0426, -63.8227],
[21.2151, -64.2804],

[sloriot]

Let's take a simpler example:

  std::vector<Segment_2> segments {
    {{0,0}, {0,1}},
    {{0,0}, {1,0}},
    {{0,1}, {1,1}},
    {{1,0}, {1,1}},
    {{0.5,2 }, {0.5, 0.5}},
  };

There is no way the CCB could be a simple polygon. As Efi mentioned, you can have antennas.

[pentacular]

I understand that antenna are permitted, but this case doesn't seem to involve an antenna to me.

[22.6099, 87.6822],
[-28.6321, 67.9523],
[-12.4005, 24.8937],
[-27.6534, 66.5174], // point of self-intersection [A]
[-27.6622, 66.5409],
[-27.6648, 66.5486],
[-27.6534, 66.5174], // point of self-intersection [B]
[21.0261, -62.9908],
[21.0426, -63.8227],
[21.2151, -64.2804],

I see two non-zero area polygons joined at a corner -- A-through-B and B-through-A.

Do you see the same thing or have I misunderstood something?

[sloriot]

Note that an antenna is not necessarily an edge, it could be a polygon, like in your case. If I zoom to the point of self-intersection you are mentioning we see the following:

[pentacular]

I understood that an antenna would be composed of edges such that edge->face() == edge->twin()->face().

But this isn't the case for this construction, so I guess this definition is insufficient.

Could you point me at a definition of antenna that includes this non-zero area polygon case?

[sloriot]

I don't really have a clean definition of an antenna but you could see it as a sequence of halfedges that if removed from a CCB, make the CCB a closed sequence of halfedges. You of course need to update prev/next and requires that the antenna is connected at a single vertex.

[pentacular]

Thanks -- that makes sense. :)

It might be useful to make it clearer in the Arrangement_2 documentation that antenna with positive area are expected.

The only examples I see have zero area.

[sloriot]

Indeed you somehow have this figure showing it for a hole but it could be made more explicit.

[pentacular]

Ok, this understanding of antenna appears to be sufficient to produce well formed polygons with holes from arrangements.

Thanks.

[pentacular]

These non-zero area antenna are making it difficult to do face-level analysis.

Is there any reliable way to split them off into separate faces?

I do not see a way to duplicate a vertex, and without that, I do not see how I could reconnect the areas such that they would not again form an antenna.

[pentacular]

I guess the answer is to add custom data at the halfedge level to annotate each halfedge with suitable region id?