Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
1 of 2 tasks
jimy-byerley opened this issue Oct 13, 2023 · 2 comments
Assignees
Labels
bug Something isn't working enhancement New feature or request

Comments

@jimy-byerley
Copy link
Owner

jimy-byerley commented Oct 13, 2023

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:

  • triangulate using sweepline algorithm $O(n log(n) )$
  • rework the triangulation by propagating better pairing candidates $O(n)$
@jimy-byerley jimy-byerley added bug Something isn't working enhancement New feature or request labels Oct 13, 2023
@jimy-byerley jimy-byerley self-assigned this Oct 13, 2023
@jimy-byerley
Copy link
Owner Author

the sweepline triangulation seems to work
image

@jimy-byerley
Copy link
Owner Author

possible degenerated cases for sweepline

  • fix degenerated case of 2 edges at the same place
  • fix degenerated case of a null-length edge
  • fix degenerated case of 2 monotonics with the exact same flat front, with one getting challenged by an edge of the other
  • fix degenerated case of empty loop
  • fix degenerated case of split point on an edge

@jimy-byerley jimy-byerley added this to in progress in global roadmap Dec 6, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working enhancement New feature or request
Projects
global roadmap
in progress
Development

When branches are created from issues, their pull requests are automatically linked.

1 participant