标签: intersection

在Python中,如何找到两个圆共同的所有整数点？

例如,假设两(大小相等的)圆的维恩图状交叉点,与中心点(x1,y1)和(x2,y2)和半径r1=r2.另外,我们已经知道圆圈的两个交点是(xi1,yi1)和(xi2,yi2).

如何(x,y)以有效的方式生成两个圆圈中包含的所有点的列表？也就是说,绘制一个包含交叉点的框并迭代它是很简单的,检查给定点是否在两个圆内,但是有更好的方法吗？

这样做最简单的方法是什么？我在数学上失败了,我在互联网上找到了非常复杂的公式...我希望如果有一些更简单的吗？

我只需要知道一个球体是否与一个立方体重叠,我不在乎它做了哪个点等.

我也希望它能利用这两个形状都是对称的事实.

编辑:立方体在x,y,z轴上直线对齐

我想在Python(2.7)中交叉两个列表.我需要结果可迭代:

list1 = [1,2,3,4]
list2 = [3,4,5,6]
result = (3,4) # any kind of iterable

在交叉点之后首先提供完整的迭代,以下哪个更有效？

使用发电机:

result = (x for x in list1 if x in list2)

使用filter():

result = filter(lambda x: x in list2, list1)

其他建议？

感谢
Amnon

尝试编写一个带有两个字符串的for函数,并返回按它们在第一个字符串中出现的顺序相交的字符.

这是我试过的:

def strIntersection(str1, str2):
    for i in str1:
        str3 = ''
        str3 = str3.join(i for i in str1 if i in str2 not in str3)
    return str3

str1 = 'asdfasdfasfd'
str2 = 'qazwsxedc'

strIntersection(str1,str2)

=> 'asdasdasd'

但是我只希望交叉字符出现一次并按照第一个字符串的顺序即出现.'ASD'

有人可以帮忙吗？

我在其他论坛上发现了一些类似的问题,但解决方案似乎都涉及列表,而我希望我的输出是一个字符串

下面的函数需要两个BitSets,复制第一个(它不能被覆盖),将副本与第二个(按位AND)相交并返回结果的基数.

public int getIntersectionSize(BitSet bits1, BitSet bits2) {
    BitSet copy = (BitSet) bits1.clone();
    copy.and(bits2);
    return copy.cardinality();
}

我对这段代码加速感兴趣吗？这个功能被称为十亿次,所以即使是微秒加速也是有道理的,而且我对最快的代码感到好奇.

我给出了两个不同的numpy数组.第一个是二维数组,看起来像(前十点):

[[  0.           0.        ]
 [ 12.54901961  18.03921569]
 [ 13.7254902   17.64705882]
 [ 14.11764706  17.25490196]
 [ 14.90196078  17.25490196]
 [ 14.50980392  17.64705882]
 [ 14.11764706  17.64705882]
 [ 14.50980392  17.25490196]
 [ 17.64705882  18.03921569]
 [ 21.17647059  34.11764706]]

第二个数组只是一维的,看起来像(前十点):

[ 18.03921569  17.64705882  17.25490196  17.25490196  17.64705882
  17.64705882  17.25490196  17.64705882  21.17647059  22.35294118]

第二个(一维)数组中的值可能出现在第一列中的第一个(二维)数组中.Fe 17.64705882

我想从二维数组中获取一个数组,其中第一列的值与第二个(一维)数组中的值匹配.怎么做？

我在3d空间中有成千上万个OOBB(面向对象的边界框),它包含简单的细长3d网格.他们紧紧地挤在一起.

我想拍摄光线并找出哪些OOBB被击中.由于我需要执行的光线交叉测试的数量(数百万),对所有OOBB的暴力方法是不够的.

最初我认为使用某种空间分区系统来快速缩小潜在结果会很容易,但像BVH或KDTrees这样的系统依赖于AABB(轴对齐边界框)来加速查询,在我的情况下,那些效率非常低(因为我所包含的网格的对角线性质使得我的紧密堆积的OOBB具有大致相同的AABB).

我在RAPID库中读到了OBBTrees,但看起来它们是从上到下构建的(从多边形汤开始并细分为逐渐变小的OOBB组以形成树),而不是自下而上(从大量OOBB开始)并从他们建立一个树).

有没有其他数据结构可以用来加速交叉口测试？

这是我的OOBB图片.正如你所看到的,它们是紧密的,如果你可以想象它们的AABB会是什么样子,你会发现它们重叠到基于AABB的树不会真正提高性能的程度(因为几乎所有这些都是会被群体中心的射线击中.

值得注意的是,我需要查询所有被光线击中的OOBB,而不仅仅是第一个/最近的一个.

对于光线跟踪器项目,我一直在研究处理找到光线和三角形之间交叉的算法(由三个顶点定义).到目前为止我发现的是Möller-Trumbore(MT)算法被普遍使用.

所以我的问题是1)是否有MT的替代方案或算法被认为是计算交叉点的最快方法？2)如果是,MT被证明是最优的还是有人可以想象发明更快的算法？

编辑:我现在看到我的问题与Ray-triangle交叉非常相似

我刚开始使用面向有限元分析的3D网格。我想在类似立方体的矩阵中建模材料（任何形状，但主要对球体和椭球体感兴趣）的夹杂物。这些内含物不应彼此重合。

因此，我在考虑为python使用某种程序包，该程序包可以绘制原始对象，查找它们的交集（如果存在）并导出几何体（或对其进行网格划分并导出）。对于球体，我正在编写自己的解决方案，但我认为将其扩展为除球体以外的其他形状将非常困难。

在寻找合适的库/模块几天后，我无法决定应该使用哪个库/模块。

我想使用python作为主要语言，因为它很简单，开放源代码，我已经知道了一点。因此检查了此链接： python中好的几何库？

但：

• SymPy。似乎仅适用于2D对象。
• 吡尤利德。在其Google代码页中看起来已停产。
• CGAL。似乎是最先进的，但我找不到它是否相交。
• 几何简单。也已停产，我相信它不能处理3D对象。
• pythonocc。缺少文档是这里的重要问题。
• 打开网格。看来是个不错的选择，但我看不出它是否有交叉点。

我可能会缺少某些功能或库。对不起

如果确实有必要且有用，我可以尝试使用C ++，它似乎有更多的几何库，如此处，此处和此处所述。另外，我想我应该提到我主要在Windows 10上工作，而我对Linux的经验很少，但是我可以挑战自己。

总结一下我的问题：python中是否有任何好的库（如果可能）可以找到3D对象之间的交集？我是否缺少我应该知道的功能或库？我会很高兴向正确的方向提出任何建议。

提前非常感谢！

在矩阵中，例如M1，行是国家，列是年。这些国家在同一年没有观测值。我想找到多年来为我提供最多国家/地区的“最佳”交集。最小年份和最小国家/地区的数量将被预先定义。结果中包括哪些国家并不重要，年份不必连续。

> M1
      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15]
 [1,]   NA   NA   NA 2004   NA 2006   NA 2008 2009    NA  2011  2012    NA    NA    NA
 [2,]   NA 2002   NA 2004   NA   NA 2007   NA   NA  2010  2011    NA  2013  2014    NA
 [3,]   NA   NA   NA 2004 2005 2006 2007 2008 2009    NA    NA  2012  2013    NA  2015
 [4,]   NA 2002   NA 2004 2005 2006 2007 2008   NA  2010  2011 …