问题标签 [line-intersection]

编辑：示例文件的 Git Repo https://github.com/tpubben/lineIntersect

我正在尝试根据一组相交线计算 x,y 坐标中的线交点，这些相交线穿过由多个线段组成的一条连续线。

实线由元组列表表示，如下所示，其中每个段以前一段端点的 x/y 坐标开始：

交叉线以相同的方式表示，但是每条线都是离散的线（没有共享点）：

我正在尝试遍历连续线（lineA）并检查哪些交叉线与 lineA 的哪些段相交。

线交叉点的示例图像如下：

到目前为止，我已经尝试了以下方法：

我已经使用了这里发布的代码。这是代码：

它实现了 Cramer 规则（适用于线条；如果为两条给定线条构建的线性方程的行列式为 0，则线条不相交）。然而，我遇到的问题是它还检测到由于手头两条线的延续而导致的交叉点。这是我使用的一个图matplotlib，它演示了这个问题：

我还有一个Triangle包含 3 个Line对象的类，它进一步说明了这个问题，因为该类也有自己的intersect(...)函数，它接受另一个三角形并检查两个三角形的哪些边相交以及在哪里：

我想使用链接中的算法检测线段相交。上述线段没有交点。我怎么做？

我有两个类 -Point和Line- 用于以更易读的方式处理这些几何元素。我维护了上面的脚本并将其包裹起来（请参阅 参考资料Line.intersect(...)）：

我也在寻找一个最佳的（尽可能少的非成本操作和尽可能少的内存占用）解决方案。

一种可能的解决方案是通过使用欧几里德距离来确定这些点是否位于两个线段上，从而过滤掉结果的交点（不属于两个线段的交叉点）。如果不是，则相交是一条或两条线连续的结果，应视为无效。然而，这是一项代价高昂的操作，并且还涉及考虑所有交点（无论该点是否是两个段的一部分）。

更新：我以为我已经解决了这个问题，但是唉！下面有问题。在仔细查看评论后，我看到了@JerryCoffin 发表的评论，他指出这篇文章可能存在重复：

结果：

这看起来不错，正是我想要的。但是我添加了一条线（坐标或多或​​少是随机的，但我很容易在图上检查）即Line(Point(-4, 12), Point(12, -4)). 想象一下当我再次得到一个误报时我的惊讶：

如您所见，在我的线段开头的左上角检测到一个交叉点。它确实与垂直线的延续相交，但与实际线段不相交。似乎两条线段相同而一条线段是垂直的这一事实构成了一个问题。所以我仍然不知道如何解决这个问题。x

我正在尝试从任一侧（应该相交）获得由两个线性 polyfit 制成的组合拟合线，这是拟合线的图片：

我试图使两条拟合（蓝色）线相交并产生一条组合拟合线，如下图所示：

请注意，波峰可以发生在任何地方，所以我不能假设在中心。

这是创建第一个图的代码：

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

这是我的代码：

有人可以帮我降低这个程序的时间复杂度吗？

给定N行（水平或垂直），我需要找到这些线段的总交点以及每条线的交点。我的代码如下：

对于以下输入：

输出 ：

现在我不知道如何做以下事情：

1.两条线段端点相交时不应有交点。一个端点可以位于另一条线段上，尽管(3,0) 是不正确的。根据我的条件，有效的交点是：

2.我想计算每条线的交叉点数，即期望的输出应该是：

IE

有人可以帮我纠正这两个代码错误吗？

我正在编写一个简单的 2D 游戏引擎，因为我想复习我的学校数学知识。我知道也许很多人已经回答了类似的问题（我阅读了很多关于这个主题的问题和答案），但我无法管理为什么我的方法不起作用。在这个例子中，我们可以看到一个“房间”，里面有一个摄像头和两条根据摄像头方向改变方向的光线。这些光线应该代表相机视野的左右边界，并且应该与相机前面的墙壁相交。问题是当相机移动和旋转时（使用“UP”、“DOWN”、“LEFT”、“RIGHT”），有时光线会消失，即相交功能失败。有人可以帮我找到解决方案吗？这里有代码的相关部分：

编辑：我试图删除代码的不相关部分。综合不是我的素质之一，我希望现在更具可读性。

首先，我编写了一个简单的代码，根据 x 和 y 坐标给出的 4 个点检查 2 条线是否发生碰撞。它检查两条线的角度（我的代码中的变量 k ）是否相同，在这种情况下它们是平行的，否则它们会发生碰撞。角度 (k) 是根据数学方程计算得出的，单击此处[k = (y2-y1)/(x2-x1)]。现在我不知道如何理解他们的冲突点。如果你能帮助我，我将不胜感激。先感谢您。

我的代码：（我调用计算角度的方法）

Duzina 类中的代码：

我必须找到一种算法，可以找到两组数组之间的交集总量，而其中一个数组是排序的。

举个例子，我们有这两个数组，我们画直线指向对应的数字。

这两个数组总共给了我们7 个交集。

它存在什么样的算法来帮助我解决这个问题？

我使用了搜索按钮，但没有找到任何可以为我解决这个问题的东西。

谢谢

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

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

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

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

还有更多的例子。我应该看看另一种方法来检测交叉点。感谢所有输入和想法，谢谢。

我在 3D 空间的某处有一条线和一个三角形。换句话说，三角形有 3 个点（每个 [x,y,z]），直线有两个点（也有 [x,y,z]）。

我需要找出一种方法，希望使用 C++ 来确定这条线是否穿过三角形。一条平行于三角形的线，并且有多个共同点，应该算作“不相交”。

我已经编写了一些代码，但它不起作用，即使视觉表示清楚地显示了交叉点，我也总是会出错。

这是 inside() 的定义