pymadcad
pymadcad copied to clipboard
new triangulation algorithm based on sweepline and retriangulation to tackle the current algorithm problems
This issue is to track advance in experimenting this particular algorithm. Its targets:
- being faster than the current algorithm (meaning should not have a $O(n^2)$ complexity), the current algorithm is alone responsible of the computation time of boolean operations
- being robust to all kind of degenerated and side cases
- output nice triangulations (with triangles the closest to equilateral triangles) so avoid loosing computation precision in operations on the resulting mesh
This should solve #79, #54 once it is done
The principle:
- [x] triangulate using sweepline algorithm $O(n log(n) )$
- [ ] rework the triangulation by propagating better pairing candidates $O(n)$
the sweepline triangulation seems to work
possible degenerated cases for sweepline
- [x] fix degenerated case of 2 edges at the same place
- [ ] fix degenerated case of a null-length edge
- [x] fix degenerated case of 2 monotonics with the exact same flat front, with one getting challenged by an edge of the other
- [x] fix degenerated case of empty loop
- [ ] fix degenerated case of split point on an edge