topic Re: Intersection of a point and a shapefile feature in Java Maps SDK Questions

Intersection of a point and a shapefile feature

JulienTroudet — Wed, 07 Jan 2015 16:46:00 GMT

Hello,

I'm not very experienced with the Arcgis SDK, so please excuse me if my questions are not perfectly understandable.

For a research project I have a dataset of points all over the world with lat-long coordinates. I also have a grid, in the form of a shapefile with multiple polygons, that covers all of the earth. The shapefile spatial reference is Eckert-IV.

An illustration of my data could be this (with a lot more point in each square) :

I must find for each of my points the name of the square (polygon) he is in, and add this in a file. The name is a property of each of my features in the shapefile.

For the moment I proceed like this :

For each point{

Convert the point to Eckert-IV as newPoint

For Each feature in my shapefile{

Geometry intersection = GeometryEngine.intersect(feature.getGeometry(), newPoint, eckert-IV);

if(intersection is not empty){

assign the name of the feature to the point

break;

}

This is pseudocode, but I think you get the idea.

This works, I tested it, but it takes a long time to test every point (my feature are 100*100km squares, so there a lot of them)

And at least but not last, I have to do this for more tan 500 millions point. And i cant let run my code for more than a year

So my question is : What are the alternatives ? I suppose I'm not the first to try this sort of thing so I suppose there's already a bunch of tools or algorithms that will do this more efficiently.

If some people here have an idea of how I can proceed I would be very happy !

Thanks for your time !

Re: Intersection of a point and a shapefile feature

VijayGandhi — Wed, 07 Jan 2015 23:21:29 GMT

Hi Julien,

There is a lot of computation here that could be avoided. Instead of checking intersection of every point with every polygon, you could create a spatial index using the polygons and then check every point against the spatial index. The complexity for the first case is O(n points x m polygons). In the second case, it could be reduced to O(m) + O(n x log m) (O(m) for building the index).

The polygons in your data seem to be static, so a spatial index such as a grid-based or a quad-tree could be a good fit. An example of quad tree implementation is at http://gamedevelopment.tutsplus.com/tutorials/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space--gamedev-3… ). Another spatial index at aled/jsi · GitHub

Some other thoughts:

1) You could spawn multiple threads that run concurrently.

2) In general, using Geometry.intersects() takes less time compared to Geometry.intersect() followed by checking whether it returned something.

Vijay

Re: Intersection of a point and a shapefile feature

JulienTroudet — Thu, 08 Jan 2015 09:12:21 GMT

Thanks for your answer !

I will look into this and try what you suggest.

I'll update my progress here.