Whether a point lies within a rectangle (Fast solution)

Question

vivek 2014-10-22

2
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/159671-whether-a-point-lies-within-a-rectangle-fast-solution

回答： Hary 2024-7-15

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 个评论
显示无隐藏无

Guillaume 2014-10-22

Do the rectangles overlap?

Are the coordinates integer or floating point?

vivek 2014-10-22

The rectangles can overlap and the coordinates are floating point.

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Star Strider 2014-10-22

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/159671-whether-a-point-lies-within-a-rectangle-fast-solution#answer_156191

编辑：Adam Danz 2020-6-20

The inpolygon (and possibly rectint depending on what you want to do) functions will likely make your task easier, although they would not eliminate the loops over the rectangles.

3 个评论
显示 1更早的评论隐藏 1更早的评论

Adam Danz 2020-6-20

编辑：Adam Danz 2020-6-20

* 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

Star Strider 2020-6-20

Adam — Thank you!

请先登录，再进行评论。

Answer 2

Guillaume 2014-10-22

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/159671-whether-a-point-lies-within-a-rectangle-fast-solution#answer_156207

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 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

Answer 3

Matt J 2014-10-22

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/159671-whether-a-point-lies-within-a-rectangle-fast-solution#answer_156211

编辑：Matt J 2014-10-22

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.

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

vivek 2014-10-22

A simple example code would be very helpful for the idea mentioned.

请先登录，再进行评论。

Answer 4

Leonardo Souto Ferreira 2018-2-8

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/159671-whether-a-point-lies-within-a-rectangle-fast-solution#answer_304022

U can accelerate your search using a quadtree for example.

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

Answer 5

Hary 2024-7-15

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/159671-whether-a-point-lies-within-a-rectangle-fast-solution#answer_1485278

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