CODEWITHSUNDEEP
algorithmgeospatialspatial
user3093455
user3093455

Reputation: 403

Fast spatial search algorithm/package

I have a dataset which has spatial objects (the red blobs in the picture below) that cover a number pixels or grid points - but has irregular shapes. I have another dataset which consists of points with 2D coordinates and I want to know whether each point in this dataset is within a certain distance from any pixel of any of the spatial objects. The main problem I have is that I have to explicitly look into each object struct to find its location and pixels. Is there a way for me to index the spatial information of the data such that I can perform this search more efficiently? Right now, I am doing it brute force, where given a point from the second dataset I have to loop through each object, check its location, check the location of its pixels, and then test if any one pixel is within a distance X from the point. I am using MATLAB but if there are any packages I could use in any language that would be great.

enter image description here

Upvotes: 0

Views: 439

Answers (1)

dpmcmlxxvi
dpmcmlxxvi

Reputation: 1302

There are many spatial indexing solutions, quadtrees, r-tree, and they are listed here. There are also tools with built-in tools like QGIS and GRASS. There are also heavy handed solution like PostGIS if you have lots of data.

However, looking at your image, and since you state that your objects are already rasterized, can you convert you objects image above to a binary image? Where your objects are 1 and background is 0? If your distance is a constant, then you could dilate your binary image by that size. Then to do a lookup all you have to do is rasterize your test point and see if it is 1 or 0. If your objects or distance threshold are varying in your problem then I would use one of the spatial indexes listed above.

Upvotes: 1

Related Questions