Should Arrangement_2 face outer_ccb be self-intersecting? #7597

pentacular · 2023-07-13T15:14:03Z

pentacular
Jul 13, 2023

I am observing a case where walking an Arrangement_2's bounded face outer_ccb produces a Polygon_2 that fails is_simple due to a self-intersection with a duplicate vertex.

I expected that an outer_ccb should be a simple polygon -- is my expectation incorrect?

efifogel · 2023-07-13T16:01:05Z

efifogel
Jul 13, 2023

An outer ccb cannot self untersect.

…

On Thu, Jul 13, 2023, 18:14 Brian Spilsbury ***@***.***> wrote: I am observing a case where walking an Arrangement_2's bounded face outer_ccb produces a Polygon_2 that fails is_simple due to a self-intersection with a duplicate vertex. I expected that an outer_ccb should be a simple polygon -- is my expectation incorrect? — Reply to this email directly, view it on GitHub <#7597>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABVBNOAGLNG3FJXO7PBJE53XQAGEXANCNFSM6AAAAAA2JDFEGU> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

1 reply

pentacular Jul 14, 2023
Author

Should outer_ccb also exclude antenna?

I ask because these would look like self-intersection with a duplicate vertex.

Or have I misunderstood?

efifogel · 2023-07-14T06:35:36Z

efifogel
Jul 14, 2023

Outer CCBs may have antennas. Halfedges on a CCB can overlap as long as the face that it bounds is always on the left.

…

On Fri, Jul 14, 2023, 03:31 Brian Spilsbury ***@***.***> wrote: Should outer_ccb also exclude antenna? I ask because these would look like self-intersection with a duplicate vertex. Or have I misunderstood? — Reply to this email directly, view it on GitHub <#7597 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABVBNOAKHMQ4VTXVFVYIEZLXQCHNHANCNFSM6AAAAAA2JDFEGU> . You are receiving this because you commented.Message ID: ***@***.***>

1 reply

pentacular Jul 14, 2023
Author

This is the code I am using -- I assume I am doing something wrong.

bool AreAllArrangementFaceOuterCcbsSimple(const Arrangement_2& arrangement) {
  for (Arrangement_2::Face_const_iterator face = arrangement.faces_begin();
       face != arrangement.faces_end(); ++face) {
    if (face->is_unbounded()) {
      continue;
    }
    Polygon_2 polygon_boundary;
    Arrangement_2::Ccb_halfedge_const_circulator start = face->outer_ccb();
    Arrangement_2::Ccb_halfedge_const_circulator edge = start;
    do {
      if (edge->twin()->face() == edge->face()) {
        // Skip antenna.
        continue;
      }
      const Point_2& point = edge->source()->point();
      polygon_boundary.push_back(point);
    } while (++edge != start);
    if (!polygon_boundary.is_simple()) {
      return false;
    }
  }
  return true;
}

I have a complete (although large) test case here
https://gist.github.com/pentacular/c85eea43509ce5ac83241ec1f3d5bf21

Please let me know if you see anything obviously wrong, or if I should promote this to an issue.

Thanks.

efifogel · 2023-07-14T17:58:06Z

efifogel
Jul 14, 2023

What are you trying to prove? Also, please provide a complete program.

…

On Fri, Jul 14, 2023, 13:37 Brian Spilsbury ***@***.***> wrote: This is the code I am using -- I assume I am doing something wrong. bool AreAllArrangementFaceOuterCcbsSimple(const Arrangement_2& arrangement) { for (Arrangement_2::Face_const_iterator face = arrangement.faces_begin(); face != arrangement.faces_end(); ++face) { if (face->is_unbounded()) { continue; } Polygon_2 polygon_boundary; Arrangement_2::Ccb_halfedge_const_circulator start = face->outer_ccb(); Arrangement_2::Ccb_halfedge_const_circulator edge = start; do { if (edge->twin()->face() == edge->face()) { // Skip antenna. continue; } const Point_2& point = edge->source()->point(); polygon_boundary.push_back(point); } while (++edge != start); if (!polygon_boundary.is_simple()) { return false; } } return true; } I have a complete (although large) test case here https://gist.github.com/pentacular/c85eea43509ce5ac83241ec1f3d5bf21 Please let me know if you see anything obviously wrong, or if I should promote this to an issue. Thanks. — Reply to this email directly, view it on GitHub <#7597 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABVBNOEN2YIGX3RSKOKNIEDXQEOPPANCNFSM6AAAAAA2JDFEGU> . You are receiving this because you commented.Message ID: ***@***.***>

2 replies

pentacular Jul 14, 2023
Author

I am trying to understand why I am not getting simple polygons from traversing Arrangement_2 faces in some cases.

The gist provided above contains a complete program.
Here is the link again:

https://gist.github.com/pentacular/c85eea43509ce5ac83241ec1f3d5bf21

pentacular Jul 15, 2023
Author

Tracing through the halfedges gives a clear story, I think.

Half-edge (-31.7101, -10.5587) -> (-31.7107, -10.5569) twin (-31.7107, -10.5569) -> (-31.7101, -10.5587)
Duplicate (-31.7107, -10.5569) # X
Half-edge (-31.7107, -10.5569) -> (-31.7106, -10.5574) twin (-31.7106, -10.5574) -> (-31.7107, -10.5569)
Half-edge (-31.7106, -10.5574) -> (-31.7109, -10.5563) twin (-31.7109, -10.5563) -> (-31.7106, -10.5574)
Half-edge (-31.7109, -10.5563) -> (-31.7107, -10.5569) twin (-31.7107, -10.5569) -> (-31.7109, -10.5563)
Duplicate (-31.7107, -10.5569) # X
Half-edge (-31.7107, -10.5569) -> (-31.7134, -10.543) twin (-31.7134, -10.543) -> (-31.7107, -10.5569)

So what we have here is a face which has comes into a point X, then loops around back to point X, then continues onward.

The loop in this case isn't an antenna, so antenna removal isn't appropriate.
I can split this excursion off into a separate polygon, but I understood that Arrangement_2 shouldn't be producing this kind of structure in the first place.

Is my understanding correct -- should this excursion from X back to X be a separate face in the Arrangement_2?
Or have I misunderstood something fundamental about Arrangement_2?

efifogel · 2023-07-15T06:39:36Z

efifogel
Jul 15, 2023

It is also a separate face. There is nothing wrong with that.

…

On Sat, Jul 15, 2023, 08:22 Brian Spilsbury ***@***.***> wrote: Tracing through the halfedges gives a clear story, I think. Half-edge (-31.7101, -10.5587) -> (-31.7107, -10.5569) twin (-31.7107, -10.5569) -> (-31.7101, -10.5587) Duplicate (-31.7107, -10.5569) # X Half-edge (-31.7107, -10.5569) -> (-31.7106, -10.5574) twin (-31.7106, -10.5574) -> (-31.7107, -10.5569) Half-edge (-31.7106, -10.5574) -> (-31.7109, -10.5563) twin (-31.7109, -10.5563) -> (-31.7106, -10.5574) Half-edge (-31.7109, -10.5563) -> (-31.7107, -10.5569) twin (-31.7107, -10.5569) -> (-31.7109, -10.5563) Duplicate (-31.7107, -10.5569) # X Half-edge (-31.7107, -10.5569) -> (-31.7134, -10.543) twin (-31.7134, -10.543) -> (-31.7107, -10.5569) So what we have here is a face which has comes into a point X, then loops around back to point X, then continues onward. The loop in this case isn't an antenna, so antenna removal isn't appropriate. I can split this excursion off into a separate polygon, but I understood that Arrangement_2 shouldn't be producing this kind of structure in the first place. Is my understanding correct -- should this excursion from X back to X be a separate face in the Arrangement_2? Or have I misunderstood something fundamental about Arrangement_2? — Reply to this email directly, view it on GitHub <#7597 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABVBNOBBN2M725DZWG4LE3TXQISJRANCNFSM6AAAAAA2JDFEGU> . You are receiving this because you commented.Message ID: ***@***.***>

1 reply

pentacular Jul 15, 2023
Author

Hmm, I understand the code above to be building the polygon by traversing the outer_ccb of single face.

I understood that face->outer_ccb() should be a loop around that face and only that face.

Can you help me understand where the separate face is coming into it?

efifogel · 2023-07-15T08:56:35Z

efifogel
Jul 15, 2023

The separate face is just another face. If the manual doesn't help, read the book below, or at least the first 3 chapters. Efi Fogel <https://dblp.org/pid/93/800.html>, Dan Halperin, Ron Wein <https://dblp.org/pid/22/2837.html>: CGAL Arrangements and Their Applications - A Step-by-Step Guide. Geometry and Computing <https://dblp.org/db/series/gac/index.html> 7, Springer 2012, ISBN 978-3-642-17282-3, pp. I-XIX, 1-293

…

On Sat, Jul 15, 2023, 10:35 Brian Spilsbury ***@***.***> wrote: Hmm, I understand the code above to be building the polygon by traversing the outer_ccb of single face. I understood that face->outer_ccb() should be a loop around that face and only that face. Can you help me understand where the separate face is coming into it? — Reply to this email directly, view it on GitHub <#7597 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABVBNOF6GVCNCQHXKAC6VSLXQJB2PANCNFSM6AAAAAA2JDFEGU> . You are receiving this because you commented.Message ID: ***@***.***>

1 reply

pentacular Jul 15, 2023
Author

It is also a separate face.

I can't find any evidence to support that.

All of the halfedges I have shown above have the same halfedge->face() value.

So, what leads you to believe "it is also a separate face"?

efifogel · 2023-07-15T09:51:51Z

efifogel
Jul 15, 2023

Brian, read the manual.

…

On Sat, Jul 15, 2023, 12:26 Brian Spilsbury ***@***.***> wrote: It is also a separate face. I can't find any evidence to support that. All of the halfedges I have shown above have the same halfedge->face() value. So, what leads you to believe "it is also a separate face"? — Reply to this email directly, view it on GitHub <#7597 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABVBNOHXTTMVZ3OMFLEAOHLXQJO5VANCNFSM6AAAAAA2JDFEGU> . You are receiving this because you commented.Message ID: ***@***.***>

1 reply

pentacular Jul 15, 2023
Author

Everything I read in the manual supports the idea that there is a 1:1 relationship between outer_ccb and face, with the exception of unbounded and fictitious faces, for which there is no meaningful outer_ccb.

If this is not true, please let me know which part of the manual covers that, because I really cannot find it.

From what you have said above it appears to me that you are claiming that multiple faces can share the one outer_ccb(), even though all of halfedges on that outer ccb all report being on the same face.

Is this the claim you are making?

If not, then what does "It is also a separate face" mean in reference to a portion of a traversal of a single outer_ccb?

efifogel · 2023-07-15T18:50:03Z

efifogel
Jul 15, 2023

Let's reset. A face in the plane is bounded by at most one outer ccb and zero or more inner ccbs. A ccb is a chain of halfedges in the same direction. A face is always to left of the halfedge that bounds it. In the plane we refer to inner ccbs as holes. A face may also have isolated vertices. As you observed, if you consider vertices to be part of ccbs, then the same vertex may appear more than once, and twin (opposite) halfedges may appear on the same ccb. The shortest inner ccb, for example, consists of 2 twin halfedges.

…

On Sat, Jul 15, 2023, 13:59 Brian Spilsbury ***@***.***> wrote: Everything I read in the manual supports the idea that there is a 1:1 relationship between outer_ccb and face, with the exception of unbounded and fictitious faces, for which there is no meaningful outer_ccb. If this is not true, please let me know which part of the manual covers that, because I really cannot find it. From what you have said above it appears to me that you are claiming that multiple faces can share the one outer_ccb(), even though all of halfedges on that outer ccb all report being on the same face. Is this the claim you are making? If not, then what does "It is also a separate face" mean in reference to a portion of a traversal of a single outer_ccb? — Reply to this email directly, view it on GitHub <#7597 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABVBNOH5JCZVOJMBVREWYTLXQJZ2TANCNFSM6AAAAAA2JDFEGU> . You are receiving this because you commented.Message ID: ***@***.***>

1 reply

pentacular Jul 16, 2023
Author

That makes sense, however I believe I am detecting duplicate vertices that aren't involved in bridges or antennae.

https://gist.github.com/pentacular/bae9cf8d7ba07bd82bf2ce80c7982110

        if (edge->twin()->face() == edge->face()) {
          std::cout << "Found bridge or antenna: " << source << std::endl;
        }
        const Point_2& source = edge->source()->point();
        if (!seen.insert(source).second) {
          std::cout << "Found duplicate vertex: " << source << std::endl;
        }

produces

Found duplicate vertex: -31.7107 -10.5569
Found duplicate vertex: 10.4022 96.8514
Found duplicate vertex: 28.5973 36.1924

Assuming the logic above is correct, then I believe we have duplicate vertices that are not (a) isolated, or (b) involved with a twin.

I see a structure like as a single face, where I expected to see two faces.

I understood that an arrangement would not bridge two faces through a corner.

Can you see the error in my understanding?

efifogel · 2023-07-16T07:19:28Z

efifogel
Jul 16, 2023

who said that a duplicate vertex must be involved with a twin? At least look at the figures in the manual...

…

On Sun, Jul 16, 2023, 09:46 Brian Spilsbury ***@***.***> wrote: That makes sense, however I believe I am detecting duplicate vertices that aren't involved in bridges or antennae. https://gist.github.com/pentacular/bae9cf8d7ba07bd82bf2ce80c7982110 if (edge->twin()->face() == edge->face()) { std::cout << "Found bridge or antenna: " << source << std::endl; } const Point_2& source = edge->source()->point(); if (!seen.insert(source).second) { std::cout << "Found duplicate vertex: " << source << std::endl; } produces Found duplicate vertex: -31.7107 -10.5569 Found duplicate vertex: 10.4022 96.8514 Found duplicate vertex: 28.5973 36.1924 Assuming the logic above is correct, then I believe we have duplicate vertices that are not (a) isolated, or (b) involved with a twin. I see a structure like as a single face, where I expected to see two faces. I understood that an arrangement would not bridge two faces through a corner. Can you see the error in my understanding? — Reply to this email directly, view it on GitHub <#7597 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABVBNOHZ4ML252YQFFHDAKLXQOE4XANCNFSM6AAAAAA2JDFEGU> . You are receiving this because you commented.Message ID: ***@***.***>

1 reply

pentacular Jul 16, 2023
Author

[... elided points ...]
  [-31.7101, -10.5587],
  [-31.7107, -10.5569], // A
  [-31.7106, -10.5574],
  [-31.7109, -10.5563],
  [-31.7107, -10.5569], // B
  [-31.7134, -10.543]
[... elided points that loop back to the elided points at the top ...]

These are the points on the outer ccb where I am seeing the duplicate vertex.

I have included a visualization of these points above.

My understanding is that the region from A-through-B should be a distinct face within the arrangement.

Can you point me at something in the manual that explains how A-through-B can be in the same face and outer ccb as B-through-A ?

efifogel · 2023-07-16T11:39:58Z

efifogel
Jul 16, 2023

It's hard to map the coordinates to the picture, but from a brief inspection I don’t see any case similar to what you described. If you want, attach a complete minimal program that reproduces the problem and that can be compiled. Notice that you must use the exact predicate exact construction kernel.

…

On Sun, Jul 16, 2023, 10:55 Brian Spilsbury ***@***.***> wrote: [image: Screenshot from 2023-07-16 16-46-23] <https://user-images.githubusercontent.com/33278307/253791768-3c2008f0-4836-4387-8ca6-3ccf02fc9f54.png> [... elided points ...] [-31.7101, -10.5587], [-31.7107, -10.5569], // A [-31.7106, -10.5574], [-31.7109, -10.5563], [-31.7107, -10.5569], // B [-31.7134, -10.543] [... elided points that loop back to the elided points at the top ...] These are the points on the outer ccb where I am seeing the duplicate vertex. I have included a visualization of these points above. My understanding is that the region from A-through-B should be a distinct face within the arrangement. Can you point me at something in the manual that explains how A-through-B can be in the same face and outer ccb as B-through-A ? — Reply to this email directly, view it on GitHub <#7597 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABVBNOAJB2IDHNY55ALDOW3XQOM6LANCNFSM6AAAAAA2JDFEGU> . You are receiving this because you commented.Message ID: ***@***.***>

1 reply

pentacular Jul 18, 2023
Author

I've opened issue #7602 for this as it seems to show incorrect behavior.

Although I still suspect I am doing something wrong.

pentacular · 2023-08-04T04:40:58Z

pentacular
Aug 4, 2023
Author

To answer this:

Arrangement_2 may produce antenna with positive area.

e.g., a face may be shaped like <><> with two areas joined through a zero distance gap.

To produce simple polygons the outer_ccb will require splitting at the zero distance gaps.

0 replies

efifogel · 2023-08-04T07:53:32Z

efifogel
Aug 4, 2023

This <><> is 2 faces and another one that contains the 2 faces.

…

On Fri, Aug 4, 2023, 07:41 Brian Spilsbury ***@***.***> wrote: To answer this: Arrangement_2 may produce antenna with positive area. e.g., a face may be shaped like <><> with two areas joined through a zero distance gap. To produce simple polygons the outer_ccb will require splitting at the zero distance gaps. — Reply to this email directly, view it on GitHub <#7597 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABVBNOHQS7YBVEKHEHUDBJ3XTR4OJANCNFSM6AAAAAA2JDFEGU> . You are receiving this because you commented.Message ID: ***@***.***>

0 replies

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Should Arrangement_2 face outer_ccb be self-intersecting? #7597

{{title}}

Replies: 11 comments 10 replies

{{title}}

{{title}}

{{title}}

{{title}}

{{editor}}'s edit

{{editor}}'s edit

{{title}}

{{title}}

{{title}}

{{title}}

{{title}}

{{title}}

{{title}}

{{title}}

{{title}}

{{title}}

{{title}}

{{title}}

{{title}}

{{title}}

{{title}}

{{editor}}'s edit

{{editor}}'s edit

{{title}}

{{title}}

Select a reply

Should Arrangement_2 face outer_ccb be self-intersecting? #7597

Replies: 11 comments · 10 replies

pentacular Jul 14, 2023 Author

pentacular Jul 14, 2023 Author

pentacular Jul 14, 2023 Author

pentacular Jul 15, 2023 Author

pentacular Jul 15, 2023 Author

pentacular Jul 15, 2023 Author

pentacular Jul 15, 2023 Author

pentacular Jul 16, 2023 Author

pentacular Jul 16, 2023 Author

pentacular Jul 18, 2023 Author

pentacular Aug 4, 2023 Author

Replies: 11 comments 10 replies

pentacular Jul 14, 2023
Author

pentacular Jul 14, 2023
Author

pentacular Jul 14, 2023
Author

pentacular Jul 15, 2023
Author

pentacular Jul 15, 2023
Author

pentacular Jul 15, 2023
Author

pentacular Jul 15, 2023
Author

pentacular Jul 16, 2023
Author

pentacular Jul 16, 2023
Author

pentacular Jul 18, 2023
Author

pentacular
Aug 4, 2023
Author