missinglink
commented
4 years ago Hi Max,
I believe that comment is there because the PolygonLookup.search() method has a default limit of 1.
What this means is that it'll only return a single match, I believe if you set that to -1 then it won't be an issue.
Under the hood it's using npm rbush which you may find suits your needs if you're not using Pelias specificially.
Generally speaking, the method I have found which provides the best performance point-in-polygon is:
- Use an r-tree (or r* tree) to index the bounding boxes (this takes almost no time to search, irrelevant of scale).
- For each of the candidate matches (much fewer now) do a proper PIP check using the classic ray-casting technique
For the above to be fast you'll likely want to load all the data into RAM to avoid disk I/O, which is what this library does.
For bonus points, you can optimize this further:
- Recursively split each polygon into halves/quarters until each 'shard' reaches a maximum vertex count
This method will give you a guarantee of linear <1ms performance even on large complex polygons (such as New Zealand).
maxhanglin
Hi there,
This is actually not a feature request, but a feature clarification question.
I would like to know the meaning of "works best for polygons with little overlap".
We need to find the set of polygons that a point exists within from a set of thousands of geographic polygons, many of which are layered on top if one another. So I was wondering if we could see problems of reliability, speed, or what issue when using your library this way.
Thank you very much in advance.