标签: line-intersection

Bentley-Ottmann算法用于计算线段的交集.

但是,我想找到两组线之间的交叉点,而不是找到它们之间所有线的交叉点.这就是说,对于线组中的每一行A,我想知道这些线与组中的线之间的交叉点B.

无论如何我可以为此扩展Bentley-Ottmann算法吗？我已经实现了现有的Bentley-Ottmann算法(在CGAL库中),我并不热衷于修改它.但是,我很想找到重用它并扩展它的方法.

编辑:欢迎任何其他算法(不一定基于Bentley-Ottmann).如果这些算法已经在现有库中实现,那会更好.

我在空间中有两个点,L1和L2在一条线上定义了两个点.

我在太空中有三个点,P1,P2和P3在一架飞机上有3个点.

那么根据这些输入,线在什么点与平面相交？

FX.平面方程A*x + B*y + C*z + D = 0是:

A = p1.Y * (p2.Z - p3.Z) + p2.Y * (p3.Z - p1.Z) + p3.Y * (p1.Z - p2.Z)
B = p1.Z * (p2.X - p3.X) + p2.Z * (p3.X - p1.X) + p3.Z * (p1.X - p2.X)
C = p1.X * (p2.Y - p3.Y) + p2.X * (p3.Y - p1.Y) + p3.X * (p1.Y - p2.Y)
D = -(p1.X * (p2.Y * p3.Z - p3.Y * p2.Z) …

我有 QPainterPath。我需要通过 x 找到 QPainterPath 的 y 坐标。

我在 QPainterPath 中找到了 intersected() 方法。因此，我创建了新的 QPainterPath，它是具有 x 坐标的从路径边界矩形的左边缘到右边缘的线，以查找作为交集结果的点。

intersects() 方法返回 true。但 intersected() 返回空路径。

如果我使用高度 = 1 的矩形而不是直线，一切正常。

也许您有更好的想法如何找到 QPainterPath 与线的交点？

我想找到代数重建方法的权重矩阵.为此,我必须找到与网格的线交点.我可以找到直线与线的交点,但我必须存储相交的线段网格数.所以假设如果在网格第一个方格中不与网格相交,则将零置于权重矩阵的第一个元素上.这里为线路交叉尝试的代码:

ak = 3:6
aka = 3:6
x = zeros(size(aka))
y = zeros(size(ak))
for k = 1:length(ak)
  line([ak(1) ak(end)], [aka(k) aka(k)],'color','r')
end

% Vertical grid
for k = 1:length(aka)
  line([ak(k) ak(k)], [aka(1) aka(end)],'color','r')
end
hold on;
 X =[0 15.5]
 Y = [2.5 8.5] 
 m = (Y(2)-Y(1))/(X(2)-X(1)) ;
 c = 2.5 ; 
 plot(X,Y)
axis([0 10 0 10])
axis square
% plotting y intercept
for i = 1:4
    y(i) = m * ak(i) + c
    if y(i)<2 || y(i)>6
        y(i) = 0 …

有N条线段，它们要么是水平的，要么是垂直的。现在我需要找出每条线段的交点总数和交点总数。N可以达到100000。我试着检查每一对线。答案是正确的，但我需要减少它所花费的时间。

这是我的代码：

using namespace std;

typedef struct Point
{
     long long int x;
     long long int y;
} ;


bool fun(Point p0, Point p1, Point p2, Point p3)
{
    double s1_x, s1_y, s2_x, s2_y;
    s1_x = p1.x - p0.x;     s1_y = p1.y - p0.y;
    s2_x = p3.x - p2.x;     s2_y = p3.y - p2.y;

    double s, t;
    s = (-s1_y * (p0.x - p2.x) + s1_x * (p0.y - p2.y)) / (-s2_x * s1_y …

我有一个骨架图像（如下所示）。

我想得到线条的交点。我在下面尝试了以下方法，skeleton是一个 openCV 图像，算法返回一个坐标列表：

def getSkeletonIntersection(skeleton):
    image = skeleton.copy();
    image = image/255;
    intersections = list();
    for y in range(1,len(image)-1):
        for x in range(1,len(image[y])-1):
            if image[y][x] == 1:
                neighbourCount = 0;
                neighbours = neighbourCoords(x,y);
                for n in neighbours:
                    if (image[n[1]][n[0]] == 1):
                        neighbourCount += 1;
                if(neighbourCount > 2):
                    print(neighbourCount,x,y);
                    intersections.append((x,y));
    return intersections;

它找到有两个以上相邻像素的白色像素的坐标。我认为这只会返回角落，但事实并非如此 - 它会返回更多点。

这是其检测到的点标记在图像上的输出。这是因为它检测到下面显示的一些不是相交的示例。

0 0 0    1 1 0    0 1 1
1 1 1    0 1 0    1 1 0
0 0 1    0 0 …

我有一些问题让我的游戏算法工作,希望这里有人可以帮助我.谷歌似乎并不是一个很好的帮助,因为大多数解决方案只适用于完整的瓷砖.

在游戏中,单位可以占据拼图内部的不同位置,即它们可以位于拼图的左上角,中间,右下角,...位置(2/3),即(2.2/3.1),(2.5/3.5) ),(2.8/3.9).

如果他们从位置(2.2/3.1)移动到(5.7/4.1),我需要检查路径中是否有障碍物.

我目前的算法是:

1. 从(2.2/3.1)开始
2. 计算运动角度(即70度)
3. 朝这个方向移动0.1步
4. 检查我在哪个瓷砖(地板(pX)/地板(pY))
5. 重复2

这个算法有效,但对我来说它看起来不是很有效,因为障碍物只能是一个完整的瓦片,而不是瓦片的一部分(单元不会碰撞).如果我增加步长,我开始错过仅略微交叉的瓷砖(即,您只穿过最左边的角).即使步长为0.1,仍然可能错过障碍物.

我试图找到一个解决方案,采取分图(与弯道所有瓷砖(地板(start.X)/楼(start.Y))和(小区(start.X)/小区(start.Y)),移动通过每个瓷砖并以数学方式检查它是否越过.可悲的是,我似乎缺乏这项检查所需的数学知识.

我的最后一个想法是将一个瓷砖的所有4个边框作为一条线并进行直线交叉,但这似乎比我原来的方法慢.

任何提示？

谢谢.

我有两个立方贝塞尔曲线,

曲线1: - 第一个锚点(a1x,a1y),第一个控制点(c1x,c1y),第二个控制点(c2x,c2y),第二个锚点(a2x,a2y)

曲线2: - 第一个锚点(a3x,a3y),第一个控制点(c2x,c3y),第二个控制点(c4x,c4y),第二个锚点(a4x,a4y)

现在我想找到这两条贝塞尔曲线之间的交点;

怎么做？任何带算法的参考文件都会对我有帮助;

我有 4 条线段，A、B、C 和 D。每条线都表示为两个点。例如。线A由点A1和点A2表示。

我想要的是

1. 点 X，即线 A 射线与线 B 相交的点
2. X与A1（原点）之间的距离

测试相交时，线 A 射线不应

1. 与线段 D 相交
2. 与线段C相交

我该怎么做呢？

我在stackoverflow上看过很多帖子,正在讨论这个话题.我从stackoverflow中找到了一个解决方案,但我找不到帖子.这就是说:如果两条线相交,那么交叉产品会为左侧和右侧产生两种不同的结果.一个积极和一个消极.否则两者都有相同的标志.到目前为止还可以.使用的公式是,其中AB是一行而CD是另一行.

dotproductleft =(Bx-Ax)(Cy-By) - (By-Ay)(Cx-Bx)

dotproductright =(Bx-Ax)(Dy-By) - (By-Ay)(Dx-Bx)

如果我为以下给定的GPS坐标计算得到这个,我得到一个交叉点,在没有交叉点的情况下.

答:x:15.4433917 y:47.0697272

B:x:15.4433661 y:47.0697722

C:x:15.4434363 y:47.0696776

D:x:15.442966 y:47.0700098

如果我在谷歌地图引擎上绘制它,我可以看到这些线之间肯定没有交集.

dotproductleft的结果:-7.372399999828474E-10和dotproductright:1.1921940000328E-8

它非常适合其他例子,但在这里我看到它不能正常工作.但我无法发现公式中的任何错误.