c# Best way/datastructure to find all polygons that contain a coordinate?

Question

I have about 10'000 polygons consisting of lat/long points. Each polygon has metadata about what it is and what it contains. All polygons can intersect each other.

What I want to do now is to get all polygons that contain a specifc lat/long point.

What would be an efficient way to do that? Is there a faster way than going through all the polygons and checking them all separately? Is there some kind of intelligent indexing datastructure, where I can store the polygons so I can do such a query in C#?

Answer 1

First, if you do not already do this, you should give each polygon a bounding box. This is the minimum rectangle that completely contains the polygon. You assign the bounding box when you create the polygon and resize the BB if you resize the polygon.

It is quick to check whether each polygon might contain the point:

// untested code
// in scope is pointOfInterest
var candidatePolygons = from poly in allPolygons
                           where poly.BoundingBox.contains(pointOfInterest)
                           select poly;

. . .

// method of BoundingBox class
public Boolean contains(LatLongClass pointOfInterest)
{
   return pointOfInterest.Longitude.AsX >= this.minX &&
          pointOfInterest.Longitude.AsX <= this.maxX &&
          pointOfInterest.Latitude.AsY >= this.minY &&
          pointOfInterest.Latitude.AsY <= this.maxY;
}

For each polygon, this proves that the polygon definitely does not contain the point, and it should quickly eliminate most of your polygons.

There will be some polygons in which the bounding box does contain the point but the polygon does not. These will have to be checked using the slower method, but at least you are not using the slower method on all of them.

Also, if you are not already, use PLinq (from poly in allPolygons.AsParallel() ) for both filters (bounding box and the slower test).

See http://msdn.microsoft.com/en-us/library/dd997425.aspx and How exactly does AsParallel work?

Along the lines of Sinatr's comment, if you pick an axis (probably the x axis) by which to order your polygon collection (say orderby boundingbox.MinX), then you can SkipWhile pointOfInterest.Longitude.AsX < poly.boudingBox.MinX. This should give you a performance boost depending on where the pointOfInterest falls within your dataset's footprint.

One last thing: Not only should you have a bounding box for each polygon, but consider having a bounding box for your whole dataset. This way, if a caller sends you a point that is way outside of your footprint, you can eliminate all of your polygons with the very fast check against the big "global" bounding box with a not-noticable addition in processing time for in-footprint points.