pymadcad icon indicating copy to clipboard operation
pymadcad copied to clipboard

new triangulation algorithm based on sweepline and retriangulation to tackle the current algorithm problems

Open jimy-byerley opened this issue 2 years ago • 2 comments

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)$

jimy-byerley avatar Oct 13 '23 18:10 jimy-byerley

the sweepline triangulation seems to work image

jimy-byerley avatar Oct 13 '23 18:10 jimy-byerley

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

jimy-byerley avatar Oct 14 '23 09:10 jimy-byerley