问题标签 [intersection]

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

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

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

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

这都是二维的。

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

如何查找一条线是否在多边形中截取

如何查看 2 个对象数组之间的常见项目。我的相交没有返回任何东西。该对象是从 Linq to SQL 类创建的。

我知道如何测试点和三角形之间的交点。

...但是我不明白，如何使用鼠标坐标将点的起始位置精确地移动到屏幕平面上，因此点角度应该根据鼠标光标在屏幕上的位置而改变，这也应该有效完全不管我在我的 OpenGL 应用程序中使用哪个透视角度，所以点角度在不同的透视角度上会有所不同...... gluPerspective() 是我正在谈论的函数。

我正在使用 VB.Net，并且有两个一维数组。是否有一个内置函数来查找它们共同的元素？还是我必须为自己写一个？

我需要解决一个相对简单的问题——我有 n 个顶点凸 2D 多边形和一条带有一些“y”坐标的水平（！）线。我只需要一件事：检查多边形是否与这条线相交（即有2个交叉点）。

我能想到的最快的方法是在多边形内找到最小/最大 y 坐标（循环重复 n 次，两次比较和两次存储），然后比较最小 y <= y < max y。

不知何故，我觉得这可以更“数学”地解决，但我总是以较慢的代码结束（例如矢量方式——我需要计算 n[i] 和 n[i+1] 的差异，然后将它们相乘、相加等 - - 比 2 cmps+stores 慢得多）。

我正在交叉一些数字集，并通过存储每次在地图中看到数字时的计数来做到这一点。

我发现性能非常缓慢。

详细信息：-其中一组包含 150,000 个数字-该组和另一组的交集第一次大约需要 300 毫秒，第二次大约需要 5000 毫秒-我还没有进行任何分析，但每次我打破在 malloc.c 中进行交集时的调试器！

那么，我该如何提高这种性能呢？切换到不同的数据结构？一些如何提高map的内存分配性能？

更新：

1. 有没有办法让 std::map 或 boost::unordered_map 预先分配一些空间？
2. 或者，是否有任何有效使用这些的技巧？

更新2：

请参阅像 C# HashSet<T> 和 Dictionary<K,V> 这样的快速 C++ 容器？

更新3：

我对 set_intersection 进行了基准测试并得到了可怕的结果：

代码：

我在 STL 中使用 set_intersection 将一组 100,000 个数字和一组 1,000 个数字相交，它需要 21 秒，而在 C# 中需要 11 毫秒。

C++ 代码：

C#代码：

在我的机器（四核，8gb 内存）上，运行 Vista x64 Business 和 Visual Studio 2008 SP1，我试图非常快速地交叉两组数字。

我在 C++ 中实现了两种方法，在 C# 中实现了一种。到目前为止，C# 方法更快，我想改进 C++ 方法，使其比 C# 更快，我希望 C++ 可以做到这一点。

这是 C# 输出：（发布版本）

这是初始 C++ 输出，用于两种不同的方法（发布 x64 构建）：

这是最新的 C++ 输出，用于三种方法（发布 x64 构建）：

最新基准：

因此，set_intersection 方法现在比 C# 慢约 2 倍，但比最初的 C++ 方法快 2 倍。

最新的 C++ 代码：

C#代码：

C++ 代码：

好的，这是最新的，有一些变化：

• C++ 集现在已正确设置，因此它们有 50% 的交集（如 C#）
• Set1 被打乱所以它没有排序， set2 已经没有排序
• set_intersection 实现现在使用向量，并首先对它们进行排序

C++（发布，x64）结果：

所以它比 C# 慢 2 倍。@Jalf：你得到了一些非常快的数字，我在这里做错了吗？

C++ 代码：

对于一些需要从一堆松散字母中找到字谜的游戏，我最终实施了一种置换算法来找到所有可能的字谜，并在需要时过滤已知字母位置的字谜（-match顺便说一句，这很棒）。但是对于较长的单词，这被证明非常容易出错，因为浏览大量乱码并不能真正揭示隐藏在其中的正确单词。

所以我想，如果我有一个大的英语单词列表（应该可以在某个地方获得），我可以将我的排列列表与正确的单词列表相交，并（希望）从排列列表中获取所有真实的单词。

由于 PS 中的许多运算符对集合的工作方式不同，我想我可以做类似的事情

并让路口回来。不幸的是，这并不容易。我想到的其他选项是遍历一个列表并-contains为每个项目执行一个：

我认为这可能会起作用，但也很慢（尤其是当$wordlista 的结果时gc wordlist.txt）。或者我可以构建一个巨大的正则表达式：

但这也可能不会很快。我也许也可以使用findstr上述巨大的正则表达式，但这感觉是错误的。

有没有我可以使用的内置解决方案，并且比我迄今为止的尝试更好？否则，我可能会将单词列表放入哈希表并使用迭代-contains方法，这种方法应该足够快。