What is an offset bisector in 2D polygon skeletonization?

Question

I'll be referring to the definition of the offset bisector from the definitions section of CGAL's 2D Straight Skeleton and Polygon Offsetting module.

The halfplane to the bounded side of the line supporting a contour edge is called the offset zone of the contour edge.

The bounded side means the interior of the polygon built on the given contour.

Any two contour edges define an offset bisector, as follows: If the edges are non-parallel, their bisecting lines can be decomposed as 4 rays originating at the intersection of the supporting lines. Only one of these rays is contained in the combined offset zone of the edges (which one depends on the possible combinations of orientations).

There seems to be a problem with that definition: it's not always true that the bisector rays are contained in the offset zone as stated.

Here's a counterexample that doesn't match the definition: Take an equilateral triangle, and choose any two of its edges as the ones in question. The intersection point from which the bisector rays originate is the shared vertex of the two edges - as that vertex happens to be the intersection of the infinite lines that support the edges.

No matter how we understand the "combined offset zone of the edges", there is no single ray that is somehow special. Let's examine the possibilities:

1. The "combined" offset zone is the intersection of the offset zone half-planes on the two edges. No bisector rays are contained in such a zone:

   

2. The "combined" offset zone is the union of the offset zone half-planes. All bisector rays are contained in such a zone:

   

Even if we ignored the "intersection of the supporting lines", as a presumed slip of the keyboard, the bisectors will produce undistinguished rays, with no immediately apparent reason to favor one of.

So, the definition provided in CGAL's documentation seems wrong. How should it be fixed so that it makes sense? Or is my understanding of it somehow completely lopsided?

Answer 1

(I'm the author of that CGAL package)

The problem is that this section is actually missing a definition, without which the case of (point) intersecting lines (i.e. non-collinears) is unclear.

It says:

The bisecting lines of two edges are the lines bisecting the supporting lines of the edges

But there is no definition of "lines bisecting the supporting lines", and, furhermore, phrased like that, it seems those are perpendicular to those supporting lines. Which is exactly what you understood, and indeed, nothing that follows makes any sense if those are the bisectors.

I only noticed when looking at your drawing.

I'll try again...

The second statement should read:

Two non-parallel lines, intersecting at a point, are bisected by two other lines passing through that intersection point and bisecting the angles made by the intersecting lines. These are angular bisectors.

The next two are correct as is, but then it should read:

The bisecting line or lines of two edges are the bisecting line or lines of the supporting lines of the edges, following each of the three cases defined above. That is:

For edges on intersecting lines, these bisecting lines are angular bisectors.

For collinear edges having the same orientation, there is just one bisecting line which is perpendicular to the line supporting the edges. For collinear edges having the opposite orientation, the bisecting line is the line supporting the edges.

For parallel edges, the bisecting lines is a parallel line equidistant to both supporting lines.

If you look as close as before, you might notice that these new definitions still don't quite cut it for a complete understunding of all the details, and is even wrong in the case of parallel edges that happen to have the same orientation (which is a situation that is not important for this algorithm). A more complete set of definitions requires a different and more general approach but is out of the scope of this answer.

I will try to change the CGAL manuals with the more general and complete definitions, but this here should get you started.

Best