问题标签 [line-intersection]

我正在向屏幕添加一个新图层。所有可见的图层都会根据用户输入移动到随机位置。如何找出子层是否与任何其他层相交/重叠？

我想知道如何让 java 检测椭圆是链接到直线还是矩形，并且程序还应该检测它链接到的形状。

绘制了椭圆，还绘制了一条线和一个矩形。Java必须检测是否有东西链接到椭圆，如果有，然后通过线找出链接到它的东西。

这是我绘制形状的代码。

有人可以帮我吗？

如何有效地测试一个轴对齐的矩形 R 是否与一个漂亮的四边形 Q 相交？

• Nice 的意思是：Q 是凸的（不是 V 形）且非自相交的（不是领结，不是退化的）。
• 只是二维。
• 只是是/否。我不需要实际的交叉区域。
• 编辑： Q 和 R 可以打开或关闭，无论方便。

显然，对于 Q 的每个边，可以测试它是否与 R 相交。这将问题减少到 如何测试线段是否与二维中的轴对齐矩形相交？.

但是，就像 Liang-Barsky 利用 R 的轴对齐比 Cohen-Sutherland 更快一样，Q 的属性可能被利用来获得比多次运行 Liang-Barsky 更快的东西。

因此，多边形-矩形相交算法 Sutherland-Hodgman、Vatti 和 Greiner-Hormann，所有这些算法都让 Q 为非凸的，不太可能是最优的。

矩形-矩形相交的区域看起来很有希望，即使它没有利用 R 的轴对齐性。

我正在编写一个 Matlab 程序，它必须执行以下我坚持的事情。

我有一个文件，其中包含每行上两个点的名称（这些点在空间中有各自的坐标）。假设段是航空公司，点是机场。

我已经绘制了所有的航路，显然其中一些在某个点相交。我想在这些交叉点画一个十字“X”。我怎样才能做到这一点？是否有任何已经实现的 Matlab 函数可以让我找到线段的交点？

与此相关的另一个问题是，提供文件（大约有 100 行，其中每行中一个段由两个点定义）我是否应该执行一个循环来检查第一段与其他 99 个段的所有相交点，并且那么第二段与其他 98 段呢？还是有更有效的方法来做到这一点？谢谢！！！

我尝试使用 boost 几何来计算 3D 中两条线段的交点。

这是一段代码：

很明显，上述情况没有交集，但它仍然返回结果：( 1, 0, 6.94593e-310 )

它只适用于二维吗？

我需要确定两条线是否相交，但这些线只有起点。（这就是为什么这与关于线交叉点的类似问题不同的原因）。这些线被定义为 y = dx + a，其中 d 是梯度。两条线都从不同的起点 (x,y) 开始。

我创建了一个函数来计算两条线段的交点。

不幸的是，如果其中一个段是垂直的，则下面的代码将不起作用

当我有一条垂直线段时的问题，这个公式

等于 0 并且该方法返回 null。

我该如何处理这个异常。

谢谢

我已经实现了 Bentley-Ottmann 算法，还处理了这里提到的边缘情况：http ://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm#Special_position_and_numerical_precision_issues 。

但是，它仍然不适用于所有线段，例如这个，仅找到左侧交点，但没有找到第二个（当提取第一个交点时，左侧的前 2 行在扫描线字典中反转作为来自事件优先级队列的事件）：

或者在有点复杂的情况下，仍然只能识别左侧的第一个交叉点：

我应该在算法中添加什么或更改它以考虑这种情况（当然要保持其 O(n log n) 复杂度）？

编辑：另一个“肮脏”的例子，这次没有找到交叉点：

编辑 2：从第 28 页开始，请参见此处的算法伪代码和模拟： http ://www-ma2.upc.es/vera/wp-content/uploads/2012/10/intersection-of-segments.pdf

我正在学习算法和数学，我想出了“两条线段的交点”。我搜索了一个很好的代码和解释，但没有运气，我不明白它是如何一步一步地工作的。我读了这个页面，@Gareth 很好地解释了这是链接。我很困扰。我有一个像这样的例子p=(11,11), r=(-12,-12), q=(0,0), s=(0,10)。我的问题是我将如何将其应用于@gareth 的扩展。:-(，我数学不是很好，所以现在我需要帮助。

任何帮助将不胜感激。感谢你们。希望有人能帮助我理解这一点。

Im trying to write a game in 2D with Sfml. For that game i need a Lightengine and some code that can give me the area of the world that is visible to the player. AS both problems fit very well together (are pratically the same) i would like to solve both problems at once. My world will be loaded from files in which the hitboxes of objects will be represented as Polygons. I now wrote some code that takes a list of Polygons and the Direction of a Ray that follows the mouse and finds the closest intersection with any of these polygons. The next step now would be to cast rays from the players or lights Position towards the edges of the polygons, aswell rays offset by +-0.000001 radians to determine the visible area and give it back as a polygon.

The Problem though is that my algorithm (it calculates the inersection between two lines with vector mathematics) is too slow. In my very good PC i get 100fps with 300 egdes and one Ray.

I now read many articles online but couldnt find one best solution. But as far as i read it should be much faster to calculate intersections with triangles.

My question now: would it be meaningly faster to triangulate the polygons once while loading the map and then use ray-triangle intersection or is there any better way that you know of to solve my problem? I also heard of bounding Volumen hierachies but i dont know howmuch impact that would have.

Im a bit surprised of how much power my algorithm consumes, as it only has to calculate some 2 dimensional intersections...