Reputation: 4303
Say I have a 2D plane, covered with polygons (identified as an array of vertexes), analogous to:
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
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