You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
hi, guys. For there are so many edge cases in polygon boolean operation, I created a new algorithm to do boolean operation.
The algorithm is easy to write (only 500 lines core code) and it should have no edge cases and no invalid results.
I have basic implementation for the algorithm now. And it's mainly based on boost geometry. (https://github.com/fililili/best_clipper/blob/main/test.cpp, you can just paste the code to gdb online with c++20.)
The algorithm has two steps:
Do snap rounding, which is implemented in CGAL, but I will use rtree to find intersection points of segments to avoid edge cases. After that, I can build a graph.
Use planar face graph to traversal the graph to calculation how many times the face is circled (I named it face power), (the algorithm has implemented in boost graph lib, but the algorithm doesn't take contain relations in mind, so I write a new one). We handle graph, of course, graph doesn't have edge cases. After we know face power, we can know which face we want and merge left faces.)
So, the algorithm has no edge cases. And the it's fast, too. We only use rtree to find intersected segments. Traversal planar face use O(n) time. (n is the number of all endpoints and intersection points)
If anybody has interest, please contact me, thanks a lot.
reacted with thumbs up emoji reacted with thumbs down emoji reacted with laugh emoji reacted with hooray emoji reacted with confused emoji reacted with heart emoji reacted with rocket emoji reacted with eyes emoji
-
hi, guys. For there are so many edge cases in polygon boolean operation, I created a new algorithm to do boolean operation.
The algorithm is easy to write (only 500 lines core code) and it should have no edge cases and no invalid results.
I have basic implementation for the algorithm now. And it's mainly based on boost geometry. (https://github.com/fililili/best_clipper/blob/main/test.cpp, you can just paste the code to gdb online with c++20.)
The algorithm has two steps:
So, the algorithm has no edge cases. And the it's fast, too. We only use rtree to find intersected segments. Traversal planar face use O(n) time. (n is the number of all endpoints and intersection points)
If anybody has interest, please contact me, thanks a lot.
Beta Was this translation helpful? Give feedback.
All reactions