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

open_edges: consider when initializing checking against bounding box first #16

Open
TaipanRex opened this issue Oct 21, 2016 · 1 comment

Comments

@TaipanRex
Copy link
Owner

TaipanRex commented Oct 21, 2016

When open_edges is initialized, the scanline checks intersection against all Edges in graph. It might be faster on graphs with many obstacle polygons to check if the scanline crosses the bounding box of each polygon first. For the boxes it does not cross, all edges in that polygon can be ignored.

@TaipanRex
Copy link
Owner Author

Using line_profiler to profile visible_vertices(), about 10% of running time is spent on initializing open_edges, so any improvements won't have a dramatic effect, but still worth exploring. (interesting note: 58% of time is spent on insort and bisect).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant