Whether a point lies within a rectangle (Fast solution)
31 visualizaciones (últimos 30 días)
Mostrar comentarios más antiguos
vivek
el 22 de Oct. de 2014
Respondida: Hary
el 15 de Jul. de 2024
I have a large list of points and a large list of rectangles.I want to find the number of points inside each rectangle.I have a working solution which is very TPT heavy.
Is there a faster way of implementing this.
What I am doing now : Assume point P’s coordinate is (xp,yp), and the rectangle’s lower left point is (x1,y1) and upper right point is (x2,y2):if (xp is between x1 and x2) AND (yp is between y1 and y2) then the point(xp,yp) is inside the rectangle.The issue is i have a large set of points (> 20000) and a larger set of rectangles(lets say also > 2000)
Now i can loop over each rectangle to caluclate the the number of points in each
for ii=1:20000
ind = Xcord>Rects(ii,1) & Xcord<Rects(ii,3) & Ycord>Rects(ii,2) & Ycord<Rects(ii,4);
count = sum(ind);
end
2 comentarios
Guillaume
el 22 de Oct. de 2014
Do the rectangles overlap?
Are the coordinates integer or floating point?
Respuesta aceptada
Star Strider
el 22 de Oct. de 2014
Editada: Adam Danz
el 20 de Jun. de 2020
3 comentarios
Adam Danz
el 20 de Jun. de 2020
Editada: Adam Danz
el 20 de Jun. de 2020
* Just FYI, I edited Star Strider's answer to update the links to the two functions. They were from r2014a documentation which no longer exists.
+1
Más respuestas (4)
Guillaume
el 22 de Oct. de 2014
I don't think you'll find a faster way to do it in matlab, short of performing the search in a mex file.
In my limited understanding of this domain , a spatially indexed R-tree would be the way to go. Implementing this in matlab is bound to be difficult with the limited data structures available and probably not that efficient in the end.
0 comentarios
Matt J
el 22 de Oct. de 2014
Editada: Matt J
el 22 de Oct. de 2014
You should partition your field into an NxN chequerboard of 2D bins, say with N=10. Use sort or histc to bin your Rect and XY coordinate data into each square of the chequerboard . Then you don't have to compare all XY coordinates with all Rectangles. You can loop over the chequerboard squares and just compare XY data lying in a given square with rectangle data lying in that square.
Leonardo Souto Ferreira
el 8 de Feb. de 2018
U can accelerate your search using a quadtree for example.
0 comentarios
Hary
el 15 de Jul. de 2024
Using index would much faster than row to row comparison if you have less rectangle in comparison to the points you are checking in. Although loop is still needed. For example
For ii.....
index=the whole matrix >=xmin(ii) &...
end
0 comentarios
Ver también
Categorías
Más información sobre 2-D and 3-D Plots en Help Center y File Exchange.
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!