对于我正在开发的游戏,我需要一种可以计算交叉点的算法.我已经解决了这个问题,但我这样做的方式真的很讨厌,我希望这里有人能有更优雅的解决方案.

一对点表示它们之间绘制的线的端点.给定两对点,绘制的线是否相交,如果是,在什么时候？

所以例如调用线(Ax,Ay) - (Bx,By)和(Cx,Cy) - (Dx,Dy)

谁能想到解决方案？任何语言的解决方案都可以.

编辑:我应该更清楚的一点,如果交叉点超出线段的长度,算法必须返回false.

对于个人项目,我需要找出两条立方Bézier曲线是否相交.我不需要知道在哪里:我只需要知道他们是否这样做.但是,我需要快速完成.

我一直在清理这个地方,我找到了几个资源.大多数情况下,这里的问题有一个很有希望的答案.

所以在我想出什么是西尔维斯特矩阵之后,什么是决定因素,什么是结果以及为什么它有用,我想我认为解决方案是如何工作的.然而,现实不同,它不能很好地工作.

到处乱混

我用我的图形计算器绘制了两个相交的Bézier样条(我们称之为B ₀和B ₁).它们的坐标如下(P ₀,P ₁,P ₂,P ₃):

(1, 1) (2, 4) (3, 4) (4, 3)
(3, 5) (3, 6) (0, 1) (3, 1)

结果如下,B ₀是"水平"曲线而B ₁是另一个:

根据上述问题的最高投票答案的指示,我将B ₀减去B ₁.根据我的计算器,它给我留下了两个方程式(X轴和Y轴):

x = 9t^3 - 9t^2 - 3t + 2
y = 9t^3 - 9t^2 - 6t + 4

西尔维斯特矩阵

从那以后我构建了以下的西尔维斯特矩阵:

9  -9  -3   2   0   0
0 …

这似乎并不重要(它在各种论坛上得到了很多讨论),但我绝对需要将它作为更复杂算法的构建块.

输入:2D中的2个多边形(A和B),以[(x0, y0, x1, y2), ...]每个边的列表形式给出.这些点由doubles 对表示.我不知道它们是顺时针,逆时针还是任何方向.我不知道他们不一定是凸的.

输出:表示A,B和交叉多边形AB的3个多边形.其中任何一个都可以是空(？)多边形,例如null.

优化提示:这些多边形代表房间和楼层边界.所以房间边界通常与地面边界完全相交,除非它属于同一平面上的另一层(argh!).

我有点希望有人已经在c#中完成了这个并且让我使用他们的策略/代码,因为到目前为止我在这个问题上发现的是相当艰巨的.

编辑:所以看起来我并不完全是鸡,因为这样做的前景微弱.我想在这里重述所需的输出,因为这是一个特例,可能会使计算更简单:

输出:第一个多边形减去所有相交的位,交叉多边形(复数是正常的).我对第二个多边形并不感兴趣,只是它与第一个多边形的交集.

EDIT2:我目前正在使用GPC(General Polygon Clipper)库,这非常容易!

我有一个可变数量的ArrayList,我需要找到它的交集.字符串数量的实际上限可能在35左右,但可能更多.我不想要任何代码,只需要有效的想法.我有一个实现,我即将开始编码,但想听听其他一些想法.

目前,只是考虑我的解决方案,看起来我应该有Θ(n ²)的渐近运行时间.

谢谢你的帮助!

tshred

编辑:为了澄清,我真的只是想知道是否有更快的方法来做到这一点.比Θ(n ²)快.

如果给定一条线(由线上的矢量或两个点表示),我如何找到线与平面相交的点？我已经找到了大量的资源,但我无法理解那里的方程(它们似乎不是标准的代数).我想要一个标准编程语言(我使用Java)可以解释的等式(无论多长时间).

假设我有两个列表,L和M.现在我想知道它们是否共享一个元素.如果他们共享一个元素,这将是最快的询问方式(在python中)？我不关心他们分享哪些元素,或者多少,只要他们分享或不分享.

例如,在这种情况下

L = [1,2,3,4,5,6]
M = [8,9,10]

我应该得到假,在这里:

L = [1,2,3,4,5,6]
M = [5,6,7]

我应该成真.

我希望问题清楚.谢谢!

曼努埃尔

我有两个对象文字,如下:

var firstObject =
{
    x: 0,
    y: 1,
    z: 2,

    a: 10,
    b: 20,
    e: 30
}

var secondObject =
{
    x: 0,
    y: 1,
    z: 2,

    a: 10,
    c: 20,
    d: 30
}

我想获得这两个对象文字的键的交集:

var intersectionKeys  = ['x', 'y', 'z', 'a']

我显然可以做一个循环,看看另一个对象中是否存在具有相同名称的键,但我想知道这对于某些函数式编程和map/filter/reduce用法是否是一个好例子？我自己还没有完成那么多函数式编程,但我有一种感觉,对于这个问题可能存在一个干净而聪明的解决方案.

我已经尝试搜索一个javascript函数,它将检测两条线是否相互交叉.

该函数将获取每一行的两个起始端点的x,y值(我们称之为A行和B行).

如果相交则返回true,否则返回false.

功能示例.如果答案使用矢量对象,我很高兴.

Function isIntersect (lineAp1x, lineAp1y, lineAp2x, lineAp2y, lineBp1x, lineBp1y, lineBp2x, lineBp2y) 
{

    // JavaScript line intersecting test here. 

}

一些背景信息:这段代码是我想在html5画布中制作的游戏,也是我碰撞检测的一部分.

我有一组随机分布的2d点.我需要在这些点的一小部分上执行时间密集型操作,但我需要首先弄清楚我需要执行这个时间密集型操作的点.为了确定我需要什么点,他们必须通过一系列几何标准.

最基本的标准是它们在特定点的特定距离内.第二个最基本的标准是它们是否包含在从该特定点延伸出的圆形扇区(2-D锥形)内.(编辑:此操作定期调用,每次使用不同的特定点,但是相同的2d点集.)

我最初的想法是创建一个包含2d点的网格,然后沿着它相交的锥形抓取网格方块进行迭代.根据网格的大小,它将过滤掉绝大多数不需要的2d点.不幸的是,我正在运行的嵌入式系统受到严重的内存限制,所以一个大的(根据我们的标准而不是任何人),2d阵列会占用大量内存.

我一直在尝试使用KD树来研究加速计算,但我还没能找到一个关于圆扇区和kd树的算法.

是否有一种有效的算法来查找圆圈扇区中的2d点？

只是注意我们的特定系统在浮点数学和三角学方面都很慢,所以一个涉及较少的解决方案是一个需要大量的解决方案.

从包含相当大数量(约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"交叉点可能的情况.如果我管理的话,我会在未来几天尝试解决这个问题并发布一个更通用的解决方案!