Skip to content

Make the algorithm faster with a spatial index #7

@mourner

Description

@mourner

Currently the algorithm is relatively slow because checking each probe is expensive — you have to loop through all polygon points to do two things:

  1. Determine if the probe is inside or outside the polygon.
  2. 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:

  1. A zero-height bbox query that loops through all intersecting edges (very fast for all practical polygons) to determine if inside or outside.
  2. 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

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions