iOverlay – A Polygon Boolean Operations Library

[NailxSharipov]

Hi everyone,

I’d like to introduce my library iOverlay, designed for efficient 2D polygon Boolean operations. I believe this could be a valuable tool for geo-related tasks in the Rust ecosystem.

iOverlay has reached a stable version and is now ready for production use. Here are some of its key features:

• Precision: Utilizes fixed-point arithmetic for high accuracy and reliable results, particularly useful for complex geometries.
• Stability: No risk of deadlocks or crashes, ensuring robustness.
• Performance: Optimized for handling large datasets and intricate shapes. I’ve also included a detailed performance comparison that showcases its efficiency.
• Documentation: Comes with comprehensive explanations of how the library works and how to get started.

Here is also an Article how it works.

[michaelkirk]

I haven't had a chance to try this yet or look at the code, but I wanted to say that your write up is really clear and well done.

[michaelkirk]

@NailxSharipov - our existing boolean operations implementation aborts when it encounters certain floating point precision problems, which has been troublesome for some users.

It's been a while since I investigated the issue, but I recall that the problem was due to ambiguity in ordering intersections for our sweep line. This is a problem which your library seems to avoids.

My understanding is that, with i_overlay, the topology work happens only with integers. Because you use integer coordinates, you can avoid any problem of floating point ambiguity.

In order to accept f32/f64 input, i_overlay first scales the user's floating point input to an integer space. Then topology is computed with those integer coordinates. Finally, the output is un-scaled back to (something near) the original f32 or f64.

Is my understanding of your implementation correct?

Do you have any analysis about the loss of precision inherent in this approach? Typically it seems like it should be ok. Mainly I'm thinking about how to explain to users what domain their data needs to be in, in order to expect reasonable results.

For example, thought it's conceptually a tautology that A.union(A) == A, I expect that using i_overlay with sufficiently big/small/precise floating point coordinates: A.union(A) != A right? Do you have any guidelines around this behavior?

[michaelkirk]

You talk about this in the very first section of your article. I should have re-read after looking a bit at the code!

My understanding is:

• regardless of your input types, expect no greater than 32 bit fixed point precision.
• you offset the points based on the min x/y encountered in the input data, so as to best utilize that entire 32-bit dynamic range.

[NailxSharipov]

Yes, you got it mostly right.

I also started with the original sweep line algorithm that uses events to handle intersections. Like you mentioned, it has problems with sorting after splitting segments, and adding to a sorted list is very slow when there are a lot of intersection points. After trying out a few implementations, I found how to modify it to make it simple and more predictable. Now, the logic does not split segments while the sweep line moves. Instead, it just collects intersection points. Once all the intersections are collected, it becomes easier to update the original list of segments by only splitting the ones that need it. This approach has its own downsides, but it's simpler and usually at least twice as fast.

Another problem with the swipe approach. It is easy to see with integer geometry, but it is also present in float geometry. When we add a point to a geometry, we change the original one. And sometimes this is critical! This new point is not always exactly on the original segments. So this can generate a second level of intersections (which will not be present if we do not add this new point). What iOverlay does is for each new point, it stores information whether the new point is exactly on the original segment or not. If not, we repeat the whole intersection process again. In most cases, 2-3 waves of intersection are enough, but in rare cases (approximately 0.01% of all cases) it can take more than 100-1000. And this can be very time consuming. To avoid this, I found an interesting approach when the intersection of 2 segments is very close to one of its ends. I just move the intersection point to this end. And the snapping radius grows exponentially with the number of waves. This allows to limit the number of waves to 8-10.

I am going to up this problem in the next Article.

About precision, iOverlay uses a few tricks to avoid getting the wrong result, and it's not just about floating-point precision. Using integer operations makes it much easier to keep things accurate. One important thing about integer math is that operations are always commutative (a + b = b + a, and a * b = b * a). Without this property, things like figuring out if a point lies on a line become a lot more complicated.

Another big idea in iOverlay is that it avoids comparing values directly by their absolute numbers. In my article, I explain how we sort vertical segments, and in that example, you can see that there is no situation where we could end up with more than one "correct" result. This idea is used throughout iOverlay: it only provides a solution if the result is guaranteed in all cases.

Your point about converting f32/f64 geometry to i32 is correct too. First, we calculate a bounding box and shift it to the center. Then, using the larger side of the box, we figure out a scale factor to convert the floating-point values into integers, making sure we use as much of the i32 range as possible. This scale factor has to be a power of two to speed up the conversion, though in practice, the impact of using a power of two is pretty small. Of course, if the geometry is larger than the scale allows, we do lose some precision. Because of the differences in how integers and floating-point numbers represent values, you might see some differences like: float A -> int A -> float A*.