lukecampbell
commented
2 years ago Jotting down some ideas before they're lost to time:
Ideas for algorithmic approach for 2D polygon subsetting:
- Mask all triangles whose axis-aligned bounding box doesn't intersect the axis-aligned bounding box of the query polygon.
- Get convex hull for query polygon
- Mask triangles external to convex hull using separating axis theorem approach
At this point we have a polygon, and masked most of the triangles that definitely don't intersect. Approaches from this point forward that could be explored:
- Create delaunay triangulation of polygon and test remaining sets of triangles.
- Or compute convex hull decomposition of polygon and do SAT test for each convex hull in the decomposition.
I know this is going to stay on the back burner for a while, but I hope we can keep it in mind -- so I thought I'd put in this issue.
I think subsetting to a polygon is a really import use-case -- there are times, where a rectangular subset might be massively larger and more complex than what is needed -- it can also create disconnected domains -- which I'm not sure are a real problem, but still ugly.
It's possible that keeping polygons in mind might lead to different design decisions -- it's also possible that it wouldn't be a huge lift: you could subset to the bounding box of the polygon first, and then subset tot he polygon with a less efficient algorithm -- maybe that would be good enough for a first pass.