paf*_*fcu 10 python algorithm point
我有一大堆矩形,大小都相同.我正在生成不应该落在这些矩形中的随机点,所以我想做的是测试生成的点是否位于其中一个矩形中,如果是,则生成一个新点.
使用R-tree似乎可行,但它们实际上是用于矩形而不是点.我可以使用R-tree算法的修改版本,它也适用于点,但如果已经有一些更好的解决方案,我宁愿不重新发明轮子.我对数据结构不是很熟悉,所以也许已经存在一些适用于我的问题的结构？
总之,基本上我要问的是,如果有人知道一个好的算法,在Python中工作,可以用来检查一个点是否位于给定矩形集中的任何矩形.
编辑:这是2D,矩形不旋转.
这个Reddit线程解决了你的问题:
我有一组矩形,需要确定一个点是否包含在任何一个中.有什么好的数据结构可以做到这一点,快速查找很重要？
如果您的Universe是整数,或者精度水平是众所周知的并且不是太高,您可以使用来自线程的abelsson建议,使用着色使用O(1)查找:
像往常一样,你可以换空间.这里是一个O(1)查找具有非常低的常数.init:创建一个足够大的位图,以足够的精度包围所有矩形,将其初始化为黑色.将包含任何矩形白色的所有像素着色 O(1)查找:点(x,y)是白色吗？如果是这样,就会出现一个矩形.
我建议你去那篇文章并完全阅读ModernRonin的答案,这是最受欢迎的答案.我把它贴在这里:
一,微观问题.你有一个任意旋转的矩形和一个点.矩形内的点是？
有很多方法可以做到这一点.但我认为最好的是使用2D矢量交叉产品.首先,确保矩形的点以顺时针顺序存储.然后做矢量交叉乘积,其中1)由侧面的两个点形成的矢量和2)从侧面的第一点到测试点的矢量.检查结果的符号 - 正面在(在右侧)侧面,负面在外面.如果它在所有四个边内,它在矩形内.或者等效地,如果它在任何一侧之外,它就在矩形之外.这里有更多解释.
该方法每个矢量需要3次减法*每侧2个矢量加上每侧加一个交叉乘积,即三次乘法和两次加法.每边11个人,每个矩形44个人.
如果您不喜欢十字架产品,那么您可以执行以下操作:找出每个矩形的内切圆和外接圆,检查内切圆中的点是否正确.如果是这样,它也在矩形中.如果没有,请检查它是否在外接矩形之外.如果是这样,它也在矩形之外.如果它落在两个圆圈之间,你就是f****d,你必须以艰难的方式检查它.
在2d中找到一个点是否在圆内,需要两个减法和两个平方(=乘法),然后比较距离平方以避免必须做平方根.这是4次失败,两次循环是8次失败 - 但有时你仍然不会知道.此外,假设您没有支付任何CPU时间来计算外接圆或内切圆,这可能会也可能不会,这取决于您愿意对矩形集进行多少预计算.
无论如何,对每个矩形测试点可能不是一个好主意,特别是如果你有一亿个矩形.
这给我们带来了宏观问题.如何避免针对集合中的每个矩形测试点？在2D中,这可能是四叉树 问题.在3d中,generic_handle说的是 - 八叉树.在我的头顶,我可能会把它实现为B +树.使用d = 5是很诱人的,因此每个节点最多可以有4个子节点,因为它可以很好地映射到四叉树抽象上.但是如果这组矩形太大而不适合主内存(这些天不太可能),那么拥有与磁盘块大小相同的节点可能就是要走的路.
注意恼人的退化情况,比如一些具有一万个几乎相同的矩形的数据集,其中心位于相同的精确点.:P
为什么这个问题很重要？它在计算机图形中很有用,可以检查光线是否与多边形相交.也就是说,狙击步枪射击你刚刚击中你射击的那个人？它也用于实时地图软件,比如GPS单位.GPS会告诉您所处的坐标,但地图软件必须找到该点在大量地图数据中的位置,并且每秒执行几次.
同样,归功于ModernRonin ......