问题标签 [line-segment]

给定n个100个样本，我们如何使用matlab在下面的线段中生成这些随机样本

线段：

x 介于 -1 和 1 之间，y=2

我正在寻找一种算法来找到给定 n 个线段的所有交点。以下是来自http://jeffe.cs.illinois.edu/teaching/373/notes/x06-sweepline.pdf的伪代码

输入 S[1 .. n] 是一个线段数组。label[i] 是第 i 个最左边端点的标签。

将算法应用于下面设置的线，只检查一个交点。我应该怎么做才能知道其他 2 个交叉点的存在？

1. 行 [1] 进入
2. line[2] 进入，line[1] 和 line[2] 的交点被检查。
3. line[3] 进入，line[2] 和 line[3] 的交点被检查。
4. line[4] 进入，line[4] 和 line[1] 的交点被检查。找到交叉点 A。
5. line[4] 离开，没有检查任何内容。
6. line[1] 离开，没有检查任何内容。
7. line[2] 离开，没有任何检查。
8. line[3] 离开，没有任何检查。

这是一个有点棘手的问题。它不像线交叉点那么简单（我不认为）。

首先，我得到了一堆地图坐标来定义公交路线，然后我用 MKPolyline 将它绘制到我的地图（MapKit，iOS）上。它允许同时显示几条不同的公交路线。问题是有几个点公交路线共享同一条道路，因此遵循非常相似的路径，尽管 GPS 坐标不准确。

我的问题是我怎样才能最好地检测到由路线组成的线段的子序列何时遵循相同的路径，以便它们不会相互重叠？它们具有用户需要区分的不同颜色，但由于它们都非常相似，因此彩色线段被绘制在彼此之上。

如果检测到提到的线段，是否还有一种方法可以获得它们制作的线（直线或曲线）的平均运行？这样我就可以重新制作坐标，使它们彼此相邻运行，因此没有重叠。

对此的任何帮助表示赞赏，我可能只需要使用已经存在的某种算法朝着正确的方向推进，因为我确信这种类型的问题可能很难。

如何检查给定点是否在线段中？

我一开始用这个：

但它并没有真正起作用，因为 LineSegment 不是 Object..

到目前为止，这是我的代码：

编辑：据我所知，这里有一些问题可能与我的相同......我需要的答案不存在。

我正在学习计算机图形学，遇到了 Cohen-Sutherland 线裁剪算法。我们有一个由点定义的线段P1，P2并且我们试图找出它是否被裁剪在裁剪矩形内（通常由屏幕的宽度和高度定义，左上角是 [0, 0]）

该算法很简单，我们只需检查每个点以查看该点的 x 和 y 是否超出范围：

如果两者p1_code和p2_code都不等于零，我们拒绝该线，如果它们都为零，我们接受它，否则我们继续测试以找到与裁剪矩形相交边缘的裁剪交点：

我从一本书中读到这个。我理解我们如何推导出 x 截距的方程，我只是不明白为什么我们要添加 0.5f 来舍入到下一个整数。为什么我们需要四舍五入？

谢谢！

我有一个大小为 10x10 的二维单元格数组，以及许多是浮点值对的点，例如：(1.6, 1.54), (4.53, 3.23)。对 (x,y) 使得 x<10 和 y<10

每个单元格获取坐标与单元格坐标具有相同整数部分的点。所以 arr[3][7] 将采用 x={3...3.99(9)} 和 y={7...7.99(9)} 的点，例如 (3.5, 7.1) 或 (3.2, 7.6 ）。同样 (1.6, 1.54) 在 arr[1][1] 中，(4.53, 3.23) 在 arr[4][3] 中，等等。

每个点在数组中都有一个很容易找到的指定位置，因为我只需要将 x 和 y 转换为 int 即可去除小数点。

但我想找出数组中的哪些单元格与两点 A(x,y) 和 B(x,y) 之间的线段相交。

例如：A(1.5, 2.5) 和 B(4.3, 3.2) 交叉数组中索引为 [1][2]、[2][2]、[3,3] 和 [3,4] 的单元格

有什么算法吗？

这是一个类似的问题： 网格中的单元格被一条线交叉（PHP）

我正在尝试修改代码，但得到标题中列出的错误。请帮助。

错误：BruteCollinearPoints 类型中的方法 segments() 不适用于参数 (Point, Point)

我有两组 n 个节点。现在我想将一组中的每个节点与另一组中的另一个节点连接起来。结果图应该没有交集。

我知道几种扫描线算法（Bentley-Ottmann-Algorithm来检查交叉点发生的位置，但我找不到解决这些交叉点的​​算法，除了蛮力方法。

一组中的每个节点都可以连接到另一组中的任何其他节点。

任何指向解决此问题的（有效）算法的指针？无需实施。

编辑1：

这是解决问题的一种方法n=7：

黑点是一组节点，红点是一组。每个黑色节点都必须连接到一个红色节点，这样连接它们的线就不会交叉。

编辑2：

进一步澄清：所有节点的位置都是固定的，结果图将有 n 条边。我也没有任何证据证明存在解决方案，但我无法创建没有解决方案的示例。我敢肯定，某处有证据表明始终可以创建这样的平面图。此外，只需要一种解决方案，而不是所有可能的解决方案。

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

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

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

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

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

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

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

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

结果：

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

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

我有一个LineSegment带有名为bool LineSegment::intersect(LineSegment &otherLineSegment, Point &intersectionPoint, bool continuous=false). 我添加了continuous参数，因为我懒得从我LineSegment的类继承来创建一个Line类（反之亦然）。这个论点所做的基本上是可以检查两条线段之间的交叉点，既可以作为线段，也可以将它们作为线段（即它们在两个方向上无限地跨越）。如果返回intersectionPoint，则保存两个对象之间的交点。intersect(...)true

• 第一种情况涵盖了我们需要知道两条线段是否真的相交的情况。
• 第二种情况涵盖了即使两条线段不相交的情况，我们仍然需要知道 - 如果我们将这两条线段视为两条线的一部分 - 在某处发生相交。

为了进行此检查，我使用此处提供的算法（用于线段相交）和此处（用于线段相交）。

我遇到的问题是当我有两个并列的线段时，这意味着两者之间有无数个交叉点。例如，让我们以线段l1(Point(0, 1), Point(1, 1))和l2(Point(-1, 1), Point(2, 1)). 如果我们将两者都可视化，我们会得到

连续检查（即如果线相交）返回true（相交点Point(2, 1)甚至不是相交点的一部分，l2并且直接与相交点的属性相矛盾，该属性可以使用任何一条线/线段的方程来计算) 在这种情况下，当线段交点返回时false。

我该如何处理这种情况？我当然可以检查两者，如果我得到这样的不匹配，我可以说“好吧，你有重合的线条”。然而，这对我没有进一步帮助，因为：

• 双重检查很昂贵，必须对我想要的每一对线段进行
• 重叠意味着有无限的交点（当然，在使用机器浮点数时情况并非如此，因为（由于存储和准确性）我们在该区间内有一组有限（但仍然足够大）的数字）。这显然是不可能处理的，所以必须例外

另一方面，我也不能任其发展，并在我的代码中创建未定义或不正确的行为。一种可能的解决方案是检查两个向量之间的角度（相应线/线段的每个部分），如果角度为 0 或非常非常接近它（以处理舍入误差），则线重合。这仍然不能帮助我确定如何处理这些信息？