Polygon Boolean Operations Library - iOverlay

[NailxSharipov]

Hi OpenRoad Community,

I’d like to introduce my library iOverlay, which provides efficient 2D polygon Boolean operations. I believe this library could be particularly valuable for GDSII-related tasks and other polygon manipulations in EDA tools.

Over the past year, I’ve worked on implementing DRC rules and found that existing libraries often struggled with precision and performance, especially with large datasets. That’s why I developed iOverlay.

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.
• Industry Standard Compatibility: iOverlay operates using (i32, i32) for points, which aligns with GDSII standards.
• 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.

You can also read my Article for more information on how it works.

Looking forward to hearing your thoughts!

[maliberty]

You have a nice algorithm description. We currently use Boost polygon for this purpose. Do you have a comparison of performance and features? Is there a C++ API?

[NailxSharipov]

I haven’t directly compared it with Boost Polygon yet, but I’m going to test it. Currently, there isn’t a C++ API, as I’ve primarily focused on Rust, considering the C++ ecosystem already has several mature options.

[maliberty]

C++ API would be needed for anything to happen here as that's our development language. MT could be an advantage.

[maliberty]

A curiosity question: you use i32 for coordinates but how you handle intersection points that don't fall on an integer value when splitting segments? For example the self-intersecting (0,0) (3,1) (0,3) (3,0) (0,0) ?

[NailxSharipov]

Yes, for intersection points, the library snaps them to the nearest integer grid corner. This isn't a truncation but a proper rounding to the nearest value, ensuring precision. To handle that, I implemented a custom 128-bit integer division to maintain accuracy.

The library offers three precision levels:

Absolute, Average and Auto.

Here I show 2 result:

1 with absolute presicion and 2 with Auto.

And of course nobody use this scale in practice. The library has f32/f64 api and it automatic rescale.

But it is still intresting to discuss.

[NailxSharipov]

The second good question will be what will happen when we change original geometry (by snaping it to a grid) and it generate a second level of intersection points.

[NailxSharipov]

@maliberty Finally, I found time to test the Boost library. Based on the results, it looks like Boost is an outsider in this race. I’m not a C++ expert, so there’s a small chance I may have done something wrong.

However, I think it’s better to attract some attention to this. It might make more sense to switch to Clipper2.

Here are the tests I conducted: Performance Tests

[stefanottili]

You seem to use boost.geometry, please compare with boost.polygon.
If you have orthogonal or 45 degree data, take advantage of polygon90/45.
Recent technologies only allow orthogonal geometry.