测试点是否在某个矩形中

2021-06-19 13:14:32 发布

您现在位置:Python中文网/ 问答频道 /正文

3条回答
网友
1楼 ·

这个Reddit线程解决了您的问题:

I have a set of rectangles, and need to determine whether a point is contained within any of them. What are some good data structures to do this, with fast lookup being important?

如果您的宇宙是整数,或者如果精度级别是众所周知的,并且不是太高,则可以使用线程中的abelsson建议,使用O(1)使用着色查找:

As usual you can trade space for time.. here is a O(1) lookup with very low constant. init: Create a bitmap large enough to envelop all rectangles with sufficient precision, initialize it to black. Color all pixels containing any rectangle white. O(1) lookup: is the point (x,y) white? If so, a rectangle was hit.

我建议你去那篇文章,充分阅读ModernRonin的答案,这是最被接受的答案。我贴在这里:

First, the micro problem. You have an arbitrarily rotated rectangle, and a point. Is the point inside the rectangle?

There are many ways to do this. But the best, I think, is using the 2d vector cross product. First, make sure the points of the rectangle are stored in clockwise order. Then do the vector cross product with 1) the vector formed by the two points of the side and 2) a vector from the first point of the side to the test point. Check the sign of the result - positive is inside (to the right of) the side, negative is outside. If it's inside all four sides, it's inside the rectangle. Or equivalently, if it's outside any of the sides, it's outside the rectangle. More explanation here.

This method will take 3 subtracts per vector * times 2 vectors per side, plus one cross product per side which is three multiplies and two adds. 11 flops per side, 44 flops per rectangle.

If you don't like the cross product, then you could do something like: figure out the inscribed and circumscribed circles for each rectangle, check if the point inside the inscribed one. If so, it's in the rectangle as well. If not, check if it's outside the circumscribed rectangle. If so, it's outside the rectangle as well. If it falls between the two circles, you're f****d and you have to check it the hard way.

Finding if a point is inside a circle in 2d takes two subtractions and two squarings (= multiplies), and then you compare distance squared to avoid having to do a square root. That's 4 flops, times two circles is 8 flops - but sometimes you still won't know. Also this assumes that you don't pay any CPU time to compute the circumscribed or inscribed circles, which may or may not be true depending on how much pre-computation you're willing to do on your rectangle set.

In any event, it's probably not a great idea to test the point against every rectangle, especially if you have a hundred million of them.

Which brings us to the macro problem. How to avoid testing the point against every single rectangle in the set? In 2D, this is probably a quad-tree problem. In 3d, what generic_handle said - an octree. Off the top of my head, I would probably implement it as a B+ tree. It's tempting to use d = 5, so that each node can have up to 4 children, since that maps so nicely onto the quad-tree abstraction. But if the set of rectangles is too big to fit into main memory (not very likely these days), then having nodes the same size as disk blocks is probably the way to go.

Watch out for annoying degenerate cases, like some data set that has ten thousand nearly identical rectangles with centers at the same exact point. :P

Why is this problem important? It's useful in computer graphics, to check if a ray intersects a polygon. I.e., did that sniper rifle shot you just made hit the person you were shooting at? It's also used in real-time map software, like say GPS units. GPS tells you the coordinates you're at, but the map software has to find where that point is in a huge amount of map data, and do it several times per second.

再次,归功于ModernRonin。。。

网友
2楼 ·

我建议您查看BSP trees(以及可能的四叉树或八叉树,以及该页上的链接)。它们用于递归地分割整个空间,并允许您快速检查需要检查的矩形点。

至少你只有一个巨大的分区,需要检查所有的矩形,最大的分区变得如此之小,以至于它们可以缩小到单个矩形的大小。当然,分区粒度越细,为了找到要检查的矩形,沿着树向下走的时间就越长。

但是,您可以自由决定一个点适合检查多少个矩形,然后创建相应的结构。

但要注意重叠的矩形。由于BSP树无论如何都需要预先计算,因此您也可以在这段时间内删除重叠部分,以便获得清晰的分区。

网友
3楼 ·

对于与轴对齐的矩形,只需要两个点(四个数字)即可标识矩形-通常是左下角和右上角。要确定给定点(X测试,Y测试)是否与矩形(XBL,YBL,XTR,YTR)重叠,请同时测试:

  • X测试>;=XBL&X测试<;=XTR
  • Y测试>;=YBL&Y测试<;=YTR

显然,对于一个足够大的测试点集来说,这可能相当耗时。那么,问题是如何优化测试。

显然,一个优化是为包围所有矩形的框(边界框)建立最小和最大的X和Y值:对此进行的快速测试显示是否需要进一步查看。

  • X测试>;=X最小&X测试<;=X最大
  • Y测试>;=Y最小&Y测试<;=Y最大

根据总表面积中有多少被矩形覆盖,可以找到包含矩形的不重叠子区域,然后可以避免搜索那些不能包含与点重叠的矩形的子区域,再次在搜索过程中节省比较,代价是预先计算合适的数据结构。如果矩形集足够稀疏,则可能没有重叠,在这种情况下,这将退化为蛮力搜索。同样,如果矩形集非常密集,以致边界框中没有可以在不打断矩形的情况下拆分的子范围。

但是,也可以任意将边界区域分成四分之一(每个方向各一半)。然后,您将使用一个框列表,其中包含比原始集中更多的框(每个框有两个或四个框重叠任意边界之一)。这样做的好处是,您可以从搜索中删除四分之三的内容,从而减少总的搜索量,同时牺牲辅助存储空间。

所以,和以往一样,存在着时空取舍。以及预计算与搜索的权衡。如果不走运,则预计算将一事无成(例如,只有两个框,它们在两个轴上都不会重叠)。另一方面,它可以实现相当大的搜索时间效益。

相关问题