Currently the algorithm is relatively slow because checking each probe is expensive — you have to loop through all polygon points to do two things:
- Determine if the probe is inside or outside the polygon.
- Find the distance from the probe to the polygon.
In theory, we could make this much faster by indexing polygon segments with RBush (or any fast RTree index in other impementations), and then do the above with:
- A zero-height bbox query that loops through all intersecting edges (very fast for all practical polygons) to determine if inside or outside.
- A kNN-like tree search to find the closest edge for point-to-polygon calculation. Can be borrowed from Concaveman.
The current algorithm is O(NM), where M is the number of probes.
The new one would be O(N log N) for indexing + O(M log N) for checking probes, or O((M + N) log N in average, which should be MUCH faster.
cc @urschrei @chau-intl
Currently the algorithm is relatively slow because checking each probe is expensive — you have to loop through all polygon points to do two things:
In theory, we could make this much faster by indexing polygon segments with RBush (or any fast RTree index in other impementations), and then do the above with:
The current algorithm is
O(NM), where M is the number of probes.The new one would be
O(N log N)for indexing +O(M log N)for checking probes, orO((M + N) log Nin average, which should be MUCH faster.cc @urschrei @chau-intl