So the task is simple: I want to take a point shapefile as input and remove all of the points that are not contained within a polygon.

I'm using DotSpatial to do this, but the catch is that there are millions of points, and it's just... hilariously slow.

I'm using some code that looks like this:

for (int i = 0; i < points.ShapeIndices.Count - 1; i--)
    if (polygons.ShapeIndices[activeRow].Intersects(points.ShapeIndices[i]))

This takes minutes to do 80,000 points. There's obviously something janky with their implementation but I don't have time to run it down.

So my question is, if you had to get this done and introduce minimal dependencies, how would you do it? I could install PostGIS and load the shapefiles into PostGIS to do the contains operation, but I am loath to introduce a database into this project.

  • Is there an envelope (extent) intersects operator? That's a bit more lightweight. The logic is if a point falls within a polygons' extent then test for inside, obviously if the point is outside the extent then no point checking for inside the polygon. – Michael Stimson Jul 14 '14 at 21:54
  • @MichaelMiles-Stimson it's a very good suggestion, but most of the points are valid, and the ones that aren't valid are very close to the boundaries of the polygon, so I'd guess that in this instance, it might actually cost time rather than save it... – canisrufus Jul 14 '14 at 21:59
  • Sorry, I was expecting a more random sort of distribution of the points, you could consider dicing the polygons to make them simpler, thereby quicker to resolve. Another thing that might help is merging the polygons into a super polygon; some operations in OGR get quicker with a single multi-part polygon over many single part polygons so that might help. Inside is a fairly mathematical process, if the polygons are complex it will take a long time. – Michael Stimson Jul 14 '14 at 22:08
  • @MichaelMiles-Stimson this is also a really plausible sounding suggestion, but I think figuring that out would take longer than just doing it with PostGIS. Against my hopes, I'm biting this particular bullet... thanks for your help. – canisrufus Jul 14 '14 at 22:44

You can try the computational geometry method Point-in-Polygon (PIP) to identify if the point is inside the polygon. It is the raw math and it must be extremely fast.

https://stackoverflow.com/questions/11716268/point-in-polygon-algorithm - this algorithm tests point position relative to each polygon side by the means of vector math.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.