CGAL: All of Arrangement_2's Children Need an Exact Kernel

This comes up on the CGAL mailing list fairly often: why does the package XXX need an exact kernel? (Or the more common form: why does the package XXX exhibit some strange behavior if I use an inexact kernel?)

Well, if this package is based on the package Arrangement_2, then it inherited a requirement for exact constructions. Two examples include: some forms of Minkowski sum (the sum is built by building a preliminary shape and dumping it into an arrangement where it can be analyzed for self-intersections and winding counts found) and polygon boolean operations (where the arrangement contains each region intersecting any polygon with any other).

So why does arrangement_2 require exact constructions? Well, here's a layman's answer...I write this because I spent a good amount of effort a few years ago trying to write one that would work with floating point, and I hit just about every horrible problem that this "naive" case creates.

• First, there is repeatability of insertion. If you want to insert a line segment AB into your arrangement multiple times, you want the subsequent inserts of AB to be no-ops (since AB is already present). Even better, if you have some kind of "notifier" API you want to get back all of the edges in the arrangement that AB was cut into.

  But...what if there was a crossing segment CD that intersects AB at a point P such that...P cannot be collinear to AB because we ran out of bits of precision?

  If you take the naive approach and insert AP and PB you now have segments that are close to AB but not quite AB.

  Go back and insert AB again and you are really in for a world of hurt: AB originates with AP and runs a line almost the same, except for a single bit of floating point precision. I promise you that your attempt to figure out how to relate AB and AP to each other is going to go very, very badly.

• The above case gets even worse when you consider that you may be inserting overlapping lines (and not just the same line over and over). If your definition isn't overlapping, you'll simply be inserting lines so close together that a single line crossing them all produces a single point.

• Arrangements and planar maps save topology information (e.g. who is on what side of something else). The geometry information defines the map, but the topology information guides operations. In other words, we don't even try to check for an intersection unless the topology information says there couldbe an intersection. (This is pretty important for the speed of the map.)

  This is where a lack of stability in floating point calculations becomes a problem. If a floating point geomtry check is close but inexact, equivalent tests may produce inconsistent results.

  If the first result of a test is used to store topology information, we may not even try the second, inconsistent test.

My strategy at the time to deal with this was an ugly one: the map was only guaranteed to work for a very, very limited number of cases...the list was something like this:

• Operations on horizontal and vertical segments were guaranteed to work in just about every case, because we could do an exact test if at least one segment were horizontal or vertical.
• Insertion of segments was guaranteed to work if the original input list didn't come close to the limits of floating point , wasn't degenerate in any way, and we did the inserts by breaking up intersections in a single pass, then inserting.

This makes the API not very useful at all - looking at what I use Arrangement_2 for now, we violate these conditions all the time. Such limits certainly aren't appropriate for a general-purpsoe package like CGAL.

Consider for example, the trivial case of finding the union of two overlapping polygons. If any two edges are degenerate (e.g. nearly parallel, but the difference in slope is close to the limit in floating point precision) my limited API will fail, even for a trivial case where one polygon fully contains the other.

As a final thought: it probably is possible to build an API for an arrangement based on inexact geometry. The API would "leak" all of its geometry problems, e.g. the insertion of a curve could fail due to precision limits, and tests (is the curve in or out) would give inexact errors (E.g. "it's close to here but we're not really sure.")

Such an API would be fast (it'd be only floating point) and possibly even robust, but it would leak a ton of abstraction problems right up to the next level of code. For some limited classes of problems this might be acceptable, but often I think the speed boost of floating point would be lost, since most high performance higher level algorithms (like sweeps) are written assuming robust geometry.

Connected Networks, Shaping Points, and WED

I implemented connected networks in WED and I'm about to go rip the code out and try again. What went wrong?

Well, first, to be clear:

• A "curve" in computational geometry terms is just a line you could draw without lifting your pen. So a line segment, a bezier curve, a circle, or a Z shape, those are all "curves".
  
• A connected network is a series of curves where each curve ends in a node. Two curves starting/ending at the same point share the node at that point. (In other words, two curves may cross without a node, but if two curves end at a node, the node is always shared.)
• A shaping point is a point on a curve used to define the curve (like a sharp corner in our "Z" shape) that is not a node. Conceptually the lines on both sides of the shaping point are part of the same curve.

This concept is already used in X-Plane - it is the foundation for the road grid system. (Nodes represent the real junctions where a car can make a decision.) One note from the X-Plane road system: since shaping points don't define a break between two curves, but rather the shape of one big curve, we need to insert a node if the road is going to change types at a point. In other words, we need a node to start/end a road, have an intersection with another road, or change types. Otherwise a shaping point is fine.

I was working on connected networks support in WED. WED has an underlying set of geometric primitives. Putting new editing features in is trivially easy when the geometric primitives exist. (For example, overlay editing uses the same geometry as airports, so it was an easy feature.) But WED does not yet have connected network support. We need it to edit road grids and we will probably need it to define the taxi paths of AI airplanes in the future.

The Naive Approach

So the first thing I did was define an "edge" type. Its interface is a point sequence, but it had the special property that its end nodes were shared points, while its internal (shape) points were "contained" inside the primitive.

This worked and I can edit using this type, but it turns out it doesn't really work very well. Here are all of the reasons why this turned out to be a poor design choice:

• The user interface doesn't make obvious distinctions between nodes and shaping points, but the data model does. This means that a lot of operations have to convert nodes to shape points or vice versa. Thus the editing logic spends a lot of time trying to 'maintain' the rules about nodes vs. shape points.
• To make it worse, since nodes are not part of a curve but shape points are, it means our points are constantly appearing and disappearing from the hierarchy of editing primitives as a shape point becomes a node (which can have a real name) or not. Furthermore, the number of edges is constantly changing. The change in the hierarchy presented to the user makes sense if you are familiar with topology theory...which is to say, it doesn't make much sense at all.
• The internal code for the edge itself has a lot of special cases because the end nodes and internal nodes are different. This starts to matter when we consider several bezier curves ending at a single point. Normally WED keeps the curve control handle with the point, but if a point is shared, this doesn't work, so this information has to belong to the edge.

Take 2

So the new design will try a different assumption: no shape points. Every point will split a curve into two parts whether it's a shaping point or not. The good:

• All nodes are handled the same, and no rules have to be enforced. Every point is a node, and we're done. Every segment is a bezier curve, with the control handles owned by the edge.

And the bad:

• We have to merge edges into shape points on export. This is actually not very hard and is the least of our problems.
• We need to provide a really good interface for working with multiple edges, since a single edge is almost always going to be a smaller unit of work than the user wants to deal with. This means selecting an entire string of edges (not hard) but also having edit-multiple-entities work well. (This feature is a little bit borked right now.)
• It will be possible for the user to "create" more entities by not keeping meta-data for a string of edges in sync. This kind of "accidental split" wasn't possible with the old design.

So we've traded a series of invariance bugs (e.g. the risk of WED data model not meeting requirements that aren't enforced by the compiler) for a series of usability bugs (e.g. users getting annoyed that it's hard to use the program).

Ignorance is Bliss (Until It's Not)

Here comes another quote...

Never ignore a bug you don't understand.

A bug you don't understand is an opportunity to turn code you don't understand into code that you do understand. In particular, the next swing you get at this bug might be in a much uglier situation that's much harder to reproduce or diagnose.

So better to at least do the diagnostic part of the bug fix immediately. You never know: maybe what you thought was cosmetic and trivial was a symptom of something much worse.

Once you understand the bug completely, then you can say "let's not fix this just now."