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

Perform clipping / splitting on general polygons and then triangulate #4

Closed
gkjohnson opened this issue Jun 17, 2022 · 5 comments
Closed
Labels
help wanted Extra attention is needed performance

Comments

@gkjohnson
Copy link
Owner

gkjohnson commented Jun 17, 2022

Perhaps it can be drop in replaceable for the triangle splitter

@gkjohnson gkjohnson added this to the Future milestone Jun 17, 2022
@gkjohnson gkjohnson added the help wanted Extra attention is needed label Jun 20, 2022
@gkjohnson
Copy link
Owner Author

gkjohnson commented Jun 22, 2022

Relating to #49 - implementing a better strategy for clipping and then triagulating polygons will leave more edges full intact and ultimately afford more connectivity in addition to being faster. Polygon splitting should occur by gathering all intersections edges with triangles and deriving new polygon boundaries from those connected lines.

@gkjohnson
Copy link
Owner Author

@gkjohnson
Copy link
Owner Author

  • Construct polygon edge sets with a set of pre-connected edges for the triangle
  • When a splitting by a triangle
    • Find the intersection edge overlap
    • If the edge intersects another edge then split it into two edges and connect it to the split side edges
    • Unconnected edges should be added to a list so they can be easily found for future splits

@johncalvinyoung
Copy link

Notably, Earcut is fast (and is technically a separate library vendored into Three: https://github.com/mapbox/earcut), but it is far, far from ideal/Delaunay triangulation.

@gkjohnson gkjohnson changed the title Perform clipping / splitting an general polygons and then triangulate Perform clipping / splitting on general polygons and then triangulate Aug 29, 2022
@gkjohnson
Copy link
Owner Author

Closing in favor of #51

@gkjohnson gkjohnson removed this from the v0.0.x milestone Sep 12, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
help wanted Extra attention is needed performance
Projects
None yet
Development

No branches or pull requests

2 participants