问题标签 [line-segment]

我有一条射线，我需要找到它击中的最近的线段。如果我首先对线段进行排序，我认为可以在 O(log n) 时间内完成此操作，但我不记得如何对它们进行排序......我认为某种树会工作得最好，但我该如何排序他们的起点和终点？如果可能的话，我还想快速插入这个数据结构。

一条射线与一条线段有很多代​​码，但我需要一条射线与许多线段的代码……我不知道谷歌的术语是什么。

适当文章的链接很好，C++ 代码更好。谢谢！:)

PS：线段实际上是非自相交多边形的边缘，按逆时针顺序排序......但我认为以不同的方式对它们进行排序可能会有一些优势？

这都是二维的。

再三考虑，我不完全确定这是可能的。某种空间分区可能会有所帮助，但除此之外，我想不出任何方法来对线条进行排序，以便将它们与任意光线进行比较。

我需要一个基本函数来找到点和线段之间的最短距离。随意用您想要的任何语言编写解决方案；我可以把它翻译成我正在使用的（Javascript）。

编辑：我的线段由两个端点定义。所以我的线段AB是由两个点A (x1,y1)和定义的B (x2,y2)。我试图找到这条线段和一个点之间的距离C (x3,y3)。我的几何技能生疏了，所以我看到的例子令人困惑，我很抱歉承认。

在上述 ASCII 艺术中，有四个多边形（P1、P2、P3、P4）具有完全重叠的线段。例如，多边形 P2（由节点 n3、10、9、12、15、14、13、8、7、6 和 2 之间的线段形成）和 P1（n1、2、5 和 6）在n2 和 n6 之间的线段。

找到完全重叠的线段的最快方法是什么？

我的程序使用 PyOpenGL（所以它是 Python）和 psyco。

我需要在渲染的每一帧中渲染大约 21,000 个线段（除非用户放大，在这种情况下线段被剔除并且根本不发送到卡）。目前每帧大约需要 1.5 秒才能完成。这还不够好，所以我正在寻找减少不同线段数量的方法。

我想会有多条线段可以合并成一条大线的情况，但老实说，我什至不知道从哪里开始。我确实存储了每条线的起点和终点，所以这可能会有所帮助。请注意，我可以在启动时花费我需要的时间，并且内存使用并不是什么大问题。

任何想法将不胜感激。

这只是一个关于光线（和/或线段或边缘等）及其在软件渲染的 3d 引擎中的位置的大问题，该引擎正在/不执行光线跟踪操作。我正在学习基础知识，我是第一个承认我对这些东西不太了解的人，所以请善待。:)

我想知道为什么不使用参数化线而不是射线（或者它们是？？）。我查看了互联网上的一些 cpp 文件，发现有几个资源定义了一个 Ray.cpp 对象，一个带有顶点和一个向量，另一个使用了一个点和一个向量。我很确定您可以定义一条只有法线或向量的无限线，然后沿着该线定义相交点以创建一条线段作为该无限线的子集。当前是否有任何引擎以这种方式实现线路，或者是否有更好的方法来解决这个问题？

为了增加进一步的复杂性（或简单性？）维基百科说，在向量空间中，线段的端点通常是向量，特别是 u -> u + v，如果在空间中用向量而不是用向量定义线，这很有意义与已经定义的无限线相交，但我也找不到任何实现，这让我怀疑在 3d 引擎中应用它时我的想法的有效性，甚至在查看 Flash 3D 引擎 Papervision 时会产生更复杂的情况，我查看了 Ray 类，它采用 6 个单独的数值作为参数，然后将它们作为 2 个不同的 Number3D（Papervision 等效于 Vector）、数据类型返回？！？

我很想看到一个实际使用正确方法来实现这些低级部分的实现，这些低级部分按照它们的真实定义。

当使用常用公式计算两个 2D 线段之间的交集时，即此处，如果将结果四舍五入为整数，则会得到非对称结果。

也就是说，有时，由于舍入错误，我得到了intersection(A,B)!=intersection(B,A).

最好的解决方案是继续使用浮点数，并将结果比较到一定的精度。但是，我必须在计算交点后将结果舍入为整数，我不能继续使用浮点数。

到目前为止，我最好的解决方案是在飞机的各个部分上使用一些完整的顺序，并且必须intersection始终将较小的部分与较大的部分进行比较。

有没有更好的方法？我错过了什么吗？

经过一番研究，我决定在我的 2D 游戏中使用Liang-Barsky线裁剪算法。Google 没有提供该算法的任何 VB.NET 实现，但提供了大量 C/++ 实现。因此，由于我有 C++ 知识，决定将Skytopia上的一个移植到 VB.Net。不幸的是，它不适用于：

我正在使用类/方法，例如：

但是，CollideRay方法在其第 3 次边迭代 (edge = 3) 时失败，r < t0，因此该函数返回 false。

我想知道是否有人可以发现我的CollideRay函数存在导致这种行为的一些问题，因为我真的很难过。

提前致谢。

我有一条由一系列 x、y 坐标点定义的非直线。我可以毫无问题地在这些点之间直接在屏幕上画一条直线。不幸的是，我必须画出等长的线段。

这是一个示例，说明我需要如何将具有 3 个点的非直线分解为几个等距点的数组。（忽略最后的红点，它是一条线不均分的结果，也是终点）

请注意“关节”处的红线。考虑到我有一条线 A->B->C，其中向量 AB 和 BC 形成某个角度。基本上，线在 B 点弯曲。

分割点 A 和 B 之间的线直到一点都没有问题。但是当 AB 没有除以段长度时，我需要做一些特别的事情。我需要取剩余的长度并将其视为三角形的一侧。恒定线段长度是与 BC 线段相连的三角形的另一边（上面的红线）。我需要知道从 B 点到这个交叉点的长度。有了这些信息，我可以继续计算 BC 上的线段。

这是我要解决的三角形（此后我将引用这张图片上出现的变量）到目前为止，我已将问题分解为使用余弦定律。c ² = a ² + b ² - 2ab * Cos( y )

问题是我已经知道c，它是段长度。我需要求解 a（我可以计算 y）。

我已经写了一个多项式方程，但现在我卡住了：a ² + b ² - 2ab * Cos( y ) - c ² = 0

或 Ax ² + Bx + C (A = 1, B = -2b * Cos( y ), C = b ² - c ² , x = a)

这甚至是正确的方法吗？接下来我该怎么做？我需要在 Actionscript 中实现这一点。

编辑：Duh，我将不得不使用二次公式。所以我现在得到：

a = b * Cos( y ) +/- SqrRoot(c ² - b ² * Sin( y ) ² )

现在如何将其放入代码中...

目前我已经检测到图像中的边缘，并且我计划使用霍夫变换从边缘中提取线段。一旦我有了这些部分，我就计划找到两个部分交叉的角落。有没有一种算法可以从角落检测矩形？假设我检测到了四个角，是否可以在知道矩形有 4 个直角的情况下获得四个角组成的矩形边的相对长度？

我想这样做的原因是我可以提取矩形绑定的纹理并将其绘制为屏幕上的平面矩形。

编辑：感谢到目前为止的答案，我认为我应该更清楚地解释我的问题，因为我认为我被误解了。我实际上是在尝试将扭曲的矩形转换为扁平矩形。我阅读了一些 aforge 文章并看到了这个功能：链接。我想知道是否可以仅从 4 个角确定矩形边之间的比率？

C# 或 Java 中是否有任何现有的 Bentley-Ottmann 算法实现/库？