CODEWITHSUNDEEP
geometrypolygonpointvertexpolygons
topherg
topherg

Reputation: 4303

Determining which polygons a point is within from a large set of polygons

Say I have a 2D plane, covered with polygons (identified as an array of vertexes), analogous to:

enter image description here

Lets say I also have a point with coordinates on this plane, what is the easiest method to return which of the polygons the point is present in?

Although this example lists 4 polygons, it would be simple to run a check on each polygon to see if the point is within it, but I am building a system that presently has about 150 polygons, and could extend up to thousands, so doing it that way could become very slow.

So, are there any solutions to doing this that do not incur iterating through all available polygons, and checking if the point is present?

Upvotes: 1

Views: 321

Answers (1)

Cybercartel
Cybercartel

Reputation: 12592

You can use a kd-tree or a r-tree. It can reduces the search space. You can also look for a quadtree. You can choose the quad size to fit the polygons and to minimize overlapping bounding boxes.

Upvotes: 1

Related Questions