问题标签 [line-intersection]

我有一个 3d 世界，我有几个 2d 圆圈躺在地面上，面向天空。

我如何检查一条线是否会从上到下与其中一个圆圈相交？

我试图搜索，但我得到的只是这种交叉测试： http: //mathworld.wolfram.com/Circle-LineIntersection.html

但这不是我需要的，这是我的意思：http: //imageshack.us/m/192/8343/linecircleintersect.png

我一直在查看有关确定一个点是否位于多边形内的帖子，而答案对我来说太模糊、抽象或复杂。因此，我将尝试针对我需要做什么提出我的问题。

我有一组描述非直线（有时是闭合多边形）的点。我有一个矩形“视图”区域。我需要尽可能有效地确定是否有任何线段（或多边形边界）通过视图区域。

我不能简单地测试每个点以查看它是否位于视图区域内。一个线段可以通过该区域而实际上没有任何点位于该区域内（即，该线被绘制穿过该区域）。

这是我要确定的示例（红色表示该函数应该为点集返回 true，蓝色表示它应该返回 false，示例使用直线和矩形，因为我不是艺术家）。

我希望能够解释的另一个条件（尽管方法/函数可能是单独的），不仅要确定多边形的边界是否穿过矩形区域，还要确定该区域是否完全被多边形包围。这里的细微差别是，在上面首先描述的情况下，如果我只关心绘制边框，该方法应该返回 false。但在此处描述的情况下，如果我需要填充多边形区域，那么我需要该函数返回 true。我目前不需要担心测试“甜甜圈”形状的多边形（感谢上帝！）。

这是一个说明细微差别的示例（红色矩形没有单个顶点或边框段穿过屏幕区域，但仍应将其视为在屏幕上）：

对于“是否有任何线段或多边形边框穿过或位于屏幕上？” 问题 我知道我可以想出一个解决方案（尽管可能不是一个有效的解决方案）。尽管它更冗长，但条件对我来说是清楚的。但第二个“是屏幕上的多边形区域吗？” 问题有点难。我希望有人可能对这样做有一个很好的建议。如果一个解决方案很容易在另一个之上实施，那么，booya。

与往常一样，提前感谢您的任何帮助或建议。

PS我有一个确定线交点的功能，但是使用它来比较每个段与屏幕区域的每一侧似乎有点过头了，因为屏幕区域总是一个普通的 [0, 0, width, height]长方形。不是有什么捷径吗？

如果我知道平面总是在同一个 z 轴上（所以它不能旋转），并且它的宽度/高度是无限的，那么有什么方法可以快速检查我的线在平面中的相交位置？另外，我的“线”实际上不是一条线，而是一个 3d 矢量，所以“线”可以无限远。

这是依赖于两点的代码：（p1 和 p2 是直线的起点和终点。plane_z = 平面所在的位置）

另一个使用向量的解决方案（我也像第一个示例一样使用两个点，“p2.x-p1.x”等是向量计算）：

Edit3：添加了 Orbling 的解决方案，它稍微快一点，并且不一定依赖两点。

我们有一种情况，用户将在屏幕上绘制多条线，我们需要找出交叉线并获取交叉点。

有没有办法在 iPhone 中使用 cocoa-touch 实现这一点？请指出一个方向，如果可能的话，代码示例对我来说是 gr8，因为我自过去 2 天以来一直为此受困。

请帮忙。

我选择了一个基于堆栈的遍历算法（递归射线遍历算法），但我在理解它时遇到了一些麻烦。

这是我的理解。

我需要找到光线进入体素的点（然后计算光线原点和那个点的距离），它在哪里退出（然后计算光线原点和那个点之间的距离），光线原点和平面之间的距离（在一些论文中我看到公式：

我的光线方向是(0, 0, -1)，然后在某些情况下，我将除以零（因为x = 0和y = 0）。怎么会这样？

并且在算法的初始化中，光线原点在主体素中，我如何获得光线进入体素的距离？

我理解正确吗？有人可以解释吗？

请看图（抱歉，新用户不能直接在帖子中插入图片）。线条是半透明的颜色（alpha = 0.5）。当红线与自身相交时，不会出现双重叠加半透明颜色。同时，将叠加在红色上的绿色线分开。可以得出结论，画布上绘制的线条不是线性的，以及整个区域。我认为这是不正确的行为。

现场演示：jsfiddle.net/dom1n1k/xb2AY/

我不会问如何解决它:) 问题是意识形态的：你如何看待这种行为？

1. 这是合乎逻辑的，应该是；
2. 这不合逻辑，但如果它发生了——我们假设该特征；
3. 出于技术原因，Canvas 以这种方式工作 - 实现更简单。
4. 这是一个明显的错误，浏览器的作者应该修复它。

PS对不起我的英语不好。

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

Bentley-Ottmann 算法用于寻找一组直线的交点。但我有很多折线：

有没有办法找到一组折线的交点？

我正在弄清楚，但与此同时，如果有人可以提供一些指示或想法，那将很有帮助。谢谢阅读。顺便说一句，我使用的是 WPF/C#，所有的折线都是 PathGeometry。

图片来源：http ://www.sitepen.com/blog/wp-content/uploads/2007/07/gfx-curve-1.png

如何编写具有 3 个输入（由系数 [abc] 和 x 值向量组成的 2 个向量）的函数，该函数具有两个形式为 ax+by=c 的线方程，输出一个向量，给出交点的 x 和 y 值。

示例：solveSystem([1 -1 -1],[3 1 9],-5:5 ) 应该产生 [2 3]

至今：

我尝试搜索一个 javascript 函数，该函数将检测两条线是否相互交叉。

该函数将获取每条线的起点和终点的 x,y 值（我们将它们称为线 A 和线 B）。

如果它们相交则返回true，否则返回false。

函数示例。如果答案使用矢量对象，我很高兴。

一些背景信息：此代码适用于我尝试在 html5 画布中制作的游戏，并且是我的碰撞检测的一部分。