如果测试点在某些矩形 [英] Test if point is in some rectangle

问题描述

我有一个大集合的矩形的，所有的大小相同。我生成随机点不应该落在这些矩形，所以我希望做的是测试如果产生的点在矩形之​​一，如果是的话，生成一个新的起点。

I have a large collection of rectangles, all of the same size. I am generating random points that should not fall in these rectangles, so what I wish to do is test if the generated point lies in one of the rectangles, and if it does, generate a new point.

使用R-树似乎工作，但他们是真正的意思的矩形，而不是点。我可以使用R树算法，该算法与点也正常运行修改后的版本，但我宁愿不推倒重来，如果已经有一些更好的解决方案。我不是很熟悉数据结构，所以也许已经存在一些结构，它适用于我的问题？

Using R-trees seem to work, but they are really meant for rectangles and not points. I could use a modified version of a R-tree algorithm which works with points too, but I'd rather not reinvent the wheel, if there is already some better solution. I'm not very familiar with data-structures, so maybe there already exists some structure that works for my problem?

总之，基本上是我问的是，如果任何人都知道一个好的算法，在Python的工作，可以用来检查一个点是否位于矩形的任何一个给定的矩形的。

In summary, basically what I'm asking is if anyone knows of a good algorithm, that works in Python, that can be used to check if a point lies in any rectangle in a given set of rectangles.

编辑：这是在二维和矩形不旋转

edit: This is in 2D and the rectangles are not rotated.

推荐答案

这reddit的线程解决你的问题：

This Reddit thread addresses your problem:

<一个href="http://www.reddit.com/r/programming/comments/80dlc/i_have_a_set_of_rectangles_and_need_to_determine/"相对=nofollow>我有一组矩形，并且需要确定一个点是否包含在其中任何一个。有什么好的数据结构，要做到这一点，以快速查找是重要的？

如果你的宇宙是整数，或者如果precision水平是众所周知的，不太高，你可以使用的 abelsson 的从线程的建议，使用O（1）查找使用着色：

If your universe is integer, or if the level of precision is well known and is not too high, you can use abelsson's suggestion from the thread, using O(1) lookup using coloring:

和往常一样，你可以换空间   时间..这里是一个O（1）查找具有非常   低常数。初始化：创建位图   大到足以包围所有的矩形   有足够的precision，初始化   它为黑色。颜色的所有像素   包含任何长方形白色。 O（1）   查找：是点（x，y）的白色？如果   所以，一个矩形被击中。

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 的回答这是最接受之一。我在这里贴吧：

I recommend you go to that post and fully read ModernRonin's answer which is the most accepted one. I pasted it here:

首先，将微问题。您有一个   任意旋转的矩形，和一个   点。里面的点   矩形？

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

有很多方法可以做到这一点。但   最好的，我想，是使用2D   向量积。首先，确保   矩形的点存储   按顺时针方向排列。然后做矢量   用1叉积）的矢量   由两个点的一侧形成的   和2）从第一点的矢量   侧到测试点的。检查   结果的标志 - 正面是   内（到右侧）的一侧，   负在外面。如果是内   所有四个侧面，它的内   矩形。或者等价地，如果它是   以外的两侧，它的外   的矩形。 这里更多的解释。

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.

此方法将每3减去   矢量*次每边2载体，   每边加一跨产品，   为三乘法和两个补充道。 11   每边触发器，每44触发器   矩形。

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.

如果你不喜欢的叉积，   那么你可以这样做：   找出刻和   外接圆为每   矩形，检查点内   落款之一。如果是这样，它在   长方形为好。如果没有，请检查   它的外接外   矩形。如果是这样，它的外   长方形为好。如果它落在之间   两界，你˚F**** D和你   要检查硬盘的方式。

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.

查找点是否一个圆内   在2D需要两个减法和两个   squarings（=乘），然后你   比较距离平方，以避免   不必做平方根。这是4   触发器，次两圆是8触发器 -   但有时候你还是会不知道。   另外这个假定您不支付   任何CPU时间来计算   外切或内切圆，   其可以是或可以不是真正的视   多少pre-计算你   愿意做你的矩形集合。

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.

这给我们带来的宏观问题。   如何避免对测试点   在设定的每一个矩形？在   2D，这可能是一个四叉树   问题。在3D中，什么generic_handle   说 - 八叉树。关闭顶我   头，我可能会实现它作为   一个 B +树。人们很容易用D = 5，   使得每个节点都可以有多达4个   儿童，因为映射这么好听   到四叉树的抽象。但是如果   该组矩形太大了，   装入主存储器（未非常可能   这些天），然后有节点的   尺寸相同的磁盘块可能是   要走的路。

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.

当心讨厌的堕落   情况下，这样的具有十个某些数据集   千几乎相同的矩形   与中心在相同的确切点。   ：P

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

为什么这个问题重要吗？其   在计算机图形学有用的，检查   如果射线相交多边形。即   这样做，狙击步枪开枪打你刚   做打你拍戏的人   在？它也可用于实时地图   软件，好比说GPS设备。全球定位系统   告诉你，你的坐标，   但地图软件必须找到在哪里   这一点是在数量巨大的地图   数据，并做每几次   第二。

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 ...

这篇关于如果测试点在某些矩形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！