标签: intersection

从包含相当大数量(约20000)可能部分重叠的多边形的shapefile开始,我需要提取所有通过交叉它们的不同"边界"而产生的子多边形.

在实践中,从一些模拟数据开始:

library(tibble)
library(dplyr)
library(sf)

ncircles <- 9
rmax     <- 120
x_limits <- c(-70,70)
y_limits <- c(-30,30)
set.seed(100) 
xy <- data.frame(
  id = paste0("id_", 1:ncircles), 
  x = runif(ncircles, min(x_limits), max(x_limits)),
  y = runif(ncircles, min(y_limits), max(y_limits))) %>% 
  as_tibble()

polys <- st_as_sf(xy, coords = c(2,3)) %>% 
  st_buffer(runif(ncircles, min = 1, max = 20)) 

plot(polys[1])  

我需要派生一个包含ALL的多边形sf或sp多边形,并且只需要交叉点生成的多边形,例如:

(请注意,颜色仅用于举例说明预期结果,其中每个"不同颜色"区域是一个单独的多边形,不覆盖任何其他多边形)

我知道我可以通过一次分析一个多边形,识别并保存所有交叉点然后"擦除"那些区域形成完整的多边形并继续循环来解决问题,但这很慢.

我觉得应该有一个更有效的解决方案,但我无法弄清楚,所以任何帮助将不胜感激!(这两个sf和sp基础的解决方案,欢迎)

更新:

最后,我发现即使是"一次一个多边形",任务也远非简单!我真的在努力解决这个显而易见的"简单"问题!任何提示？即使是一个缓慢的解决方案或提示在正确的道路上开始将不胜感激!

更新2:

也许这会澄清一些事情:所需的功能类似于这里描述的功能:

https://it.mathworks.com/matlabcentral/fileexchange/18173-polygon-intersection?requestedDomain=www.mathworks.com

更新3:

我将赏金奖给了@ shuiping-chen(谢谢!),他的回答正确地解决了所提供的示例数据集上的问题.然而,"方法"一般被推广到"四倍"或"n-uple"交叉点可能的情况.如果我管理的话,我会在未来几天尝试解决这个问题并发布一个更通用的解决方案!

我正在寻找一种快速的方法来确定矩形和圆形之间的交叉区域(我需要进行数百万次这些计算).

一个特定的属性是,在所有情况下,圆和矩形总是有2个交点.

我需要一个快速算法来检查两条非无限线是否正在交叉.必须快速,因为它会在手机上运行很多.

该算法只需要返回yes或no,它不必确切地找出线交叉的位置!

我看过这里:你如何检测两个线段相交的位置？ 但是这个线程是一个丛林,人们一直在说"这就是答案"但是其他两个人说这是错误的,因为这个和那个错误.

请帮我找到一个好的和有效的算法.

为了清楚起见:我需要一个你给出的函数
lineApointAx
lineApointAy
lineApointBx
lineApointBy
lineBpointAx
lineBpointAy
lineBpointBx
lineBpointBy
......并且返回true或false,具体取决于两条线是否交叉.

如果你回答(伪)代码,而不是公式,我将不胜感激.

好的,这一切都发生在一个漂亮而简单的2D世界...... :)

假设我在位置Apos处有一个静态物体A,在Bpos处有一个带有bVelocity的线性移动物体B,以及一个带有速度Avelocity的弹药轮......

考虑到B的线速度和A弹药的速度,我如何找出A必须射击的角度,击中B？

现在目标是在物体的当前位置,这意味着当我的射弹到达那里时,该单位已经转移到更安全的位置:)

我有两个2D矩形,定义为原点(x,y)的大小(高度,宽度)和旋转角度(0-360°).我可以保证两个矩形的大小相同.

我需要计算这两个矩形的近似交叉区域.

计算不需要精确,尽管可以.我将把结果与其他交叉区域进行比较,以确定一组矩形中最大的交叉区域,因此它只需要相对于同一算法的其他计算准确.

我想过使用相交区域的边界框区域,但由于所有不同的可能情况,我无法获取相交区域的顶点:

我正在Cocoa框架中的Objective-C中编写这个程序,这是值得的,所以如果有人知道任何快捷方式使用NSBezierPath或者你也欢迎提出建议.

我试图在打字稿中获得关于并集和交集类型的直觉，但我无法弄清楚这种情况：Playground Link

interface A {
    a: number;
}

interface B{
    b: boolean;
}



type UnionCombinedType = A | B;
type IntersectionType = A & B;

const obj: UnionCombinedType = {
    a: 6,
    b: true,
}

const obj2: IntersectionType = {
    a: 6,
    b: true,
}

为什么我允许将两个值都放入交集类型中？两个界面之间的交集是空的。如果我读到&asAND那么我很清楚为什么它允许我添加两个 props，但是我应该读到关键字|asOR并且我希望它允许我只分配a或b而不是两者都分配。

有人能给我一些关于这些类型的直觉吗？

也就是说,如果我有两个或更多集合,并且我想返回一个包含以下任一集合的新集合:

1. 每个集合的所有元素都有共同点(AND).
2. 每组(OR)的所有元素总数.
3. 每组的所有元素都是独一无二的.(XOR).

是否有一种简单的,预先存在的方法可以做到这一点？

编辑: 这是错误的术语,不是吗？

我想确定光线和盒子之间的交点.该框由其最小3D坐标和最大3D坐标定义,并且光线由其原点和它指向的方向定义.

目前,我正在为盒子的每个面形成一个平面,我正在将光线与平面相交.如果光线与平面相交,那么我检查交叉点是否实际位于框的表面上.如果是这样,我检查它是否是此光线的最近交点,并返回最近的交点.

我检查平面交叉点是否在盒子表面上的方式是通过一个函数

bool PointOnBoxFace(R3Point point, R3Point corner1, R3Point corner2)
{
  double min_x = min(corner1.X(), corner2.X());
  double max_x = max(corner1.X(), corner2.X());
  double min_y = min(corner1.Y(), corner2.Y());
  double max_y = max(corner1.Y(), corner2.Y());
  double min_z = min(corner1.Z(), corner2.Z());
  double max_z = max(corner1.Z(), corner2.Z());
  if(point.X() >= min_x && point.X() <= max_x && 
     point.Y() >= min_y && point.Y() <= max_y &&
     point.Z() >= min_z && point.Z() <= max_z)
     return true;

  return false;
}

哪个corner1是该框面的矩形的一角,corner2是对面的角.我的实现大部分时间都在工作,但有时它给了我错误的交集.请看图片:

图像显示来自相机眼睛并撞击盒子表面的光线.其他光线是盒子表面的法线.可以看出,特别是一条光线(它实际上是看到的法线)从盒子的"背面"出来,而法线应该从盒子的顶部出来.这似乎很奇怪,因为有多个其他光线正确地击中了盒子的顶部.

我想知道我正在检查交叉点是否在盒子上的方式是正确的还是我应该使用其他算法.

谢谢.

我在2D平面上有两条光线延伸到无限远,但两者都有一个起点.它们都由起点和矢量在射线方向上描述,该射线延伸到无穷远.我想知道两条光线是否相交,但我不需要知道它们相交的位置(它是碰撞检测算法的一部分).

到目前为止,我所看到的一切都描述了找到两条线或线段的交点.是否有快速算法来解决这个问题？

我有这个功能

vector<string> instersection(const vector<string> &v1, const vector<string> &v2);

我有两个字符串向量,我想找到两者中存在的字符串,然后用常见的元素填充第三个向量.

如果我的载体是...

v1 = <"a","b","c">
v2 = <"b","c">