标签: intersection

我在STL中使用set_intersection交叉一组100,000个数字和一组1,000个数字,并且花费21s,在C#中需要11ms.

C++代码:

int runIntersectionTestAlgo()
{   

    set<int> set1;
    set<int> set2;
    set<int> intersection;


    // Create 100,000 values for set1
    for ( int i = 0; i < 100000; i++ )
    {
        int value = 1000000000 + i;
        set1.insert(value);
    }

    // Create 1,000 values for set2
    for ( int i = 0; i < 1000; i++ )
    {
        int random = rand() % 200000 + 1;
        random *= 10;

        int value = 1000000000 + random;
        set2.insert(value);
    }

    set_intersection(set1.begin(),set1.end(), set2.begin(), set2.end(), inserter(intersection, intersection.end()));

    return …

我有两套,我正在尝试做一个联合(我在做交叉时得到同样的错误).这是错误:

error C3892: 'std::_Tree_const_iterator<_Mytree>::operator *' : you cannot assign to a variable that is const

代码片段(如果我用 - >注释掉行,那么代码编译并且我的工作方式可以正常工作):

    set<Line *>::iterator it;
    set<Line *> * newSet = new set<Line *>();
    leftLines = pLeft->getSet();
    rightLines = pRight->getSet();
 -->it = set_union(leftLines->begin(),leftLines->end(),rightLines->begin(), rightLines->end(), newSet->begin());
    for(it = leftLines->begin(); it != leftLines->end(); it++)
    {
        newSet->insert(*it);
    }
    for(it = rightLines->begin(); it != rightLines->end(); it++)
    {
        newSet->insert(*it);
    }
    it = newSet->begin();
    while(it != newSet->end())
    {
        result->insert(*it);
        it++;
    }

我确定这是愚蠢的但我有点迷茫.我认为代码片段应该足够了,但我可以提供其他所需的东西.谢谢.

我有两个数组,我知道最简单的方法是知道它们是否有共同的元素.所以实际上这个问题不得不提问.

string[] countries1 = new string[] { "USA", "Uruguay", "India", "UK"};  
string[] countries2 = new string[] { "Urguay", "Argentina", "Brasil", "Chile" };  
foreach (string country in countries1)
    if (countries2.Contains(country))  
        return true;  
return false;

1. 什么是最简单的linq查询,如果任何country1国家/地区也在country2阵列中,它会让我知道？
2. 什么是最简单的linq查询将返回每个重复国家的数组？

我正在研究一个小型游戏几何库,在一堆其他方法中,我希望能够找到圆形和矩形之间的交点中点.但是,我很难想到快速算法.有谁知道这样做的好算法？

如果这意味着算法会明显加快,我愿意牺牲完美的准确性.

我代表每个形状的基本方法是:

圈子:

• 浮点x,y(中心)
• 浮动r(半径)

矩形:

• 浮点x,y(中心)
• float w,h(宽度和高度值,它们代表从中心到相应边缘的x和y距离).

编辑:

由于似乎对"中点"的含义感到困惑,让我澄清一下:

假设圆和矩形相交,则存在由它们的重叠创建的区域.我想确定这个区域的地理中心(确切地说,或者确定一个近似的近似值).

示例:http://en.wikipedia.org/wiki/Centroid

编辑#2:

你们给了我一些想法,让我努力实现其中的一些,我会回复你.

闭幕思考:

我把Gareth的答案标记为已接受的答案,因为它给了我最终结果的想法,但我的最终实现与他的不同,所以我将在这里解释.

我想出了两种一般的方法:一种是完全准确的(但需要更复杂的编程和更多的数学运算),另一种是更简单/更快的方式,它始终相当接近.我最后选择了后者,但这里有两种方法:

方法1:形状碎片:

基本上,我们的想法是将重叠区域分解为可以轻松计算其中点和面积的离散区段,然后对整个结果进行加权平均.

此处显示的示例有三个子部分:占据区域大部分的中心矩形,以及用于圆的边缘的两个弯曲部分.

方法2:线插值

首先,您需要计算矩形中将作为基本位置的点.这应该是一个容易计算并且重叠的点.我在这一点上使用的是圆和矩形的所有边缘交点的平均值(如果不存在边缘交点,我默认为圆的位置,因为它意味着一个形状包含在另一个中).

计算圆心和该点之间的直线.然后,计算位于重叠区域内的段.该区域的中点被视为该线段的中点.

这种方法不准确,但总是在两个对象中产生一个点,并且结果点通常接近中间(因此它看起来对于随意的眼睛来说是好的).它也更简单,更快,所以我选择了它.

我重新实现了python中的set但是我遇到了多个交集的问题....我遵循了学习Python这本书,但我的代码有问题

class Set:
    def __init__(self,value=[]):
        self.data = []
        self.remDupli(value)

    def remDupli(self,val):
        for i in val:
            if i not in self.data:
                self.data.append(i)

    def intersect(self,other):
        val=[]
        for i in self.data:
            for k in other:
                if i == k:
                    val.append(i)
        return Set(val)

    def union(self,other):
        val=self.data
        for i in other:
            if i not in self.data:
                val.append(i)
        return Set(val)

    def __or__(self,a):       return self.union(a)
    def __and__(self,a):      return self.intersect(a)
    def __len__(self):        return len(self.data)
    def __getitem__(self,key):  return self.data[key]
    def __repr__(self):       return 'Set: ' +repr(self.data)

class Extend(Set):
    def intersect(self, …

我正在爆炸.爆炸应该击中它的矩形内的所有敌人(x,y,x + w,y + h).爆炸和敌人都继承自Sprite类,该类具有返回其矩形的getBounds()方法.当我在构造函数中创建爆炸项目时,我会通过敌人来检查矩形是否与rectangle.intersects(rectangle2)相交.但似乎当有多个目标被支持相交时,检查会忽略其中一些......

这是som代码:在Explosion类的构造函数中,继承类Sprite

    List<Zombie> zombies = mGamePlay.getZombieHandeler().getZombies();
    Rect r = getBounds();

    for(int i = 0; i < zombies.size(); i++)
    {
        Rect zR = zombies.get(i).getAnimation().getBounds();

        if(!zombies.get(i).isDead() && r.intersect(zR))
            zombies.get(i).doDamage(new int[]{damage, 0, 0});
    }

内部类Sprite:

public Rect getBounds()
{
    return new Rect(mPosX, mPosY, mPosX + mWidth, mPosY + mHeight);
}

我有两个向量.我需要找到这两者之间的交集,并做一个很好的情节.

所以,这是一个非常简单的数据框示例:

df <- data.frame( id <- c(1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2),
                 p <-c(5,7,9,11,13,15,17,19,21,23,20,18,16,14,12,10,8,6,4,2 ),
                 q <-c(3,5,7,13,19,31,37,53,61,67,6,18,20,24,40,46,66,70,76,78))
colnames(df) <- c("id","price","quantity")

supply <- df[df$id == 1,]
demand <- df[df$id == 2,]

plot( x = supply$quantity,  y = supply$price, type = "l", ylab = "price", xlab = "quantity")
lines(x = demand$quantity , y = demand$price, type = "l")
grid()

现在,我可以绘制它们并手动找到交点,但是你可以让R计算这两条线之间的交点吗？

数据可以进行大幅度的跳跃,线条可以从非常水平到近乎水平.

在golang中哪个更快找到两个数组的交集？

原始可以是一个非常大的列表,可以作为目标

original := []string{"test", "test2", "test3"} // n amount of items

target := map[string]bool{
    "test": true,
    "test2": true,
}

for _, val := range original {
    if target[val] {
        return true
    }
}

要么

original := []string{"test", "test2", "test3"} // n amount of items
target := []string{"test", "test2"}

for _, i := range original {
    for _, x := range target {
        if i == x {
            return true
        }
    }
}

我需要编写一个Java程序来查找任意数量的列表或整数数组(任意长度)的交集(公共元素).我想Java Lists可能有一个有用的方法来实现这一点,但我正在看看API并且找不到它.

任何提示？

我有轨迹数据,其中每个轨迹由一系列坐标(x,y点)组成,每个轨迹由唯一ID标识.

这些轨迹位于  x-y  平面,我想将整个平面划分为相等大小的网格(方形网格).该网格显然是不可见的,但用于将轨迹划分为子段.每当轨迹与网格线相交时,它就会在那里被分段并成为带有new_id的新子轨迹.

我已经包含了一个简单的手工图表,以明确我的期望.

可以看出轨迹如何在网格线的交叉点处被划分,并且这些段中的每一个都具有新的唯一id.

我正在研究Python,并寻找一些python实现链接,建议,算法,甚至是伪代码.

如果有任何不清楚的地方,请告诉我.

UPDATE

为了将平面划分为网格,单元索引的完成如下:

#finding cell id for each coordinate
#cellid = (coord / cellSize).astype(int)
cellid = (coord / 0.5).astype(int)
cellid
Out[] : array([[1, 1],
              [3, 1],
              [4, 2],
              [4, 4],
              [5, 5],
              [6, 5]])
#Getting x-cell id and y-cell id separately 
x_cellid = cellid[:,0]
y_cellid = cellid[:,1]

#finding total number of cells
xmax = df.xcoord.max()
xmin = df.xcoord.min()
ymax = df.ycoord.max()
ymin = df.ycoord.min()
no_of_xcells = math.floor((xmax-xmin)/ 0.5)
no_of_ycells …