CODEWITHSUNDEEP
google-mapsgisgeospatialcomputational-geometry
numan salati
numan salati

Reputation: 19494

Point in polygon algorithm for multiple polygons

I've a google maps with bunch of polygons on it.

Here is a problem I'm interested in: Given a lat,lng point, what's the best way to determine all the polygons that this point lies in.

The obvious way is to run "point in polygon" algorithm iteratively for each polygon, but I was wondering if there an efficient algorithm to answer such queries esp if you have thousands of polygons.

Upvotes: 3

Views: 1504

Answers (2)

yosukesabai
yosukesabai

Reputation: 6244

I dont know what underneath it, but applying spatial filter to the layer containing polygon feature pre-select polygons for me... Example is this one, void GRLayer::SetSpatialFilter ( OGRGeometry * poFilter) http://www.gdal.org/ogr/classOGRLayer.html#0b4ab45cf97cbc470f0d60474d3e4169. I'd imagine many GIS environment has similar feature.

Upvotes: 0

Paul Sasik
Paul Sasik

Reputation: 81429

The only way to improve on "for each polygon" algorithm would be to create a set of metadata which would allow you to skip some polygons. For example, if for your thousands of polygons you had a list, or set of lists, of all polygons that overlapped each other then you would be able to eliminate many point-in-polygon comparisons quickly. I.e. Find first polygon that contains a point, then compare only polygons that intersect/overlap that initial polygon because any polygon that contains the point would also have to overlap some other polygon that contains it. The worst case would be N comparisons e.g. your for each implementation.

You could also create logical/physical regions of polygons, such as quadrants for example, of polygons in a certain area. In the quadrant example you would/should be able to eliminate 3/4 of polygons for comparison. This all depends on how your polygons are arranged though.

But in any case, I think an improvement to the for-each algorithm lies in the creation/organization of some logical groups among your polygon collection.

Upvotes: 0

Related Questions