问题标签 [computational-geometry]

List1包含大量 (~7^10) 的 N 维点 (N <=10)，List2包含相同或更少数量的 N 维点 (N <=10)。

我的任务是：对于 List1 中的每个点，我想检查 List2 中的哪个点最接近（欧几里德距离） List1 中的一个点，然后对其执行一些操作。我一直在做简单的嵌套循环方式，当我在 List1 中没有超过 50 个点时，但是有 7^10 个点，这显然会占用很多时间。

最快的方法是什么？计算几何中的任何概念可能会有所帮助？

编辑：我有以下内容，我已经从List2构建了一个 kd-tree ，然后现在我正在对List1中的每个点进行最近邻搜索。现在正如我最初指出的那样，List1有 7^10 个点，因此尽管我节省了每对的蛮力欧几里得距离方法，但List1中的大量点导致了大量的时间消耗。有什么办法可以改善吗？

如何测试intersession ray和triangle，如果存在如何获得从射线原点到交点的距离？如果在我的程序中我必须检查 1 条射线到 ~10000 个三角形，我可以使用什么优化？

我正在尝试编写一些代码来搜索地图上的给定点，但在给定的罗盘方位弧中。

例如 45 度（东北），两边各 20 度。

到目前为止，我有一个 SQL 命令，它会给我一个给定半径的结果，需要一些帮助来了解如何将它过滤到一个方向。

我是否能够在 SQL 中执行此操作（如果可能），还是需要一些 PHP 应用到它？

非常感谢任何和所有帮助！

我有类似于以下的多边形链...

...给定图像中的链，我将如何计算定义相同形状但没有交叉路径的链？

具体来说，对于图像的输入链，我想要的结果如下所示：

A1 ,
A2 , A2和A3
之间的 相交 , A3和A4之间的相交, A4 , A5 , A3和A4 之间的相交, A3 , A3和A2 之间的相交, A6

我正在寻找一种算法来为任何链完成此任务，但我不确定我正在尝试做的事情是否被调用，这使得寻找解决方案变得很棘手。

如果我正在尝试做的事情有一个名字，那么了解它会很有帮助。

感谢您的任何帮助！

我有两组k维向量，其中k在500左右，向量的个数通常更小。我想计算两组之间的（任意定义的）最小距离。一个天真的方法是这样的：

但是，这需要 O(n² * distance) 计算。有没有更快的方法来做到这一点？

我有一组简单的（没有孔，没有自相交）多边形，我需要检查它们是否相互交叉（一个可以完全包含在另一个中；没关系）。我可以通过简单地检查一个多边形与其他多边形的每个顶点内部来检查这一点。

我还需要确定包含树，它是一组关系，表明哪个多边形包含任何给定的多边形。由于没有多边形可以与任何其他多边形相交，因此任何包含的多边形都有一个唯一的容器；“下一个更大”的。换句话说，如果 A 包含 B 包含 C，则 A 是 B 的父级，B 是 C 的父级，我们不认为 A 是 C 的父级。

问题：如何有效地确定包含关系并检查不相交标准？我将此作为一个问题提出，因为也许组合算法比单独解决每个问题更有效。该算法应该将多边形列表作为输入，由它们的顶点列表给出。它应该生成一个布尔值 B，指示是否没有多边形与任何其他多边形相交，并且如果 B = true，则生成对 (P, C) 对的列表，其中多边形 P 是子 C 的父级。

这不是家庭作业。这是我正在从事的一个爱好项目。

我有一组点来描述应该大致为球形的形状的表面，我需要一种方法来确定是否有任何其他给定点位于该形状内。我之前一直将形状​​近似为一个精确的球体，但事实证明这太不准确了，我需要一种更准确的方法。简单性和速度优于完全准确度，一个好的近似值就足够了。

我遇到了将点云转换为 3d 网格的技术，但我发现的大多数东西都非常复杂，我正在寻找尽可能简单的东西。

有任何想法吗？

我必须能够为飞行模拟的航路点设置随机位置。数学挑战很简单：

“在四边形中找到一个随机位置，该点位于任何位置的机会均等。”

视觉上是这样的：

ABCD四边形的一个例子是：A:[21417.78 37105.97] B:[38197.32 24009.74] C:[1364.19 2455.54] D:[1227.77 37378.81]

提前感谢您提供的任何帮助。:-)

编辑感谢大家的回复。我会在周末看看这个，然后奖励接受的答案。顺便说一句，我应该提到四边形可以是凸的或凹的。Sry 'bout dat。

可能重复：
除了蛮力搜索之外，如何在凸包中找到最大的三角形

我有一组随机点，我想从中找到按面积计算的最大三角形，每个顶点都在其中一个点上。

到目前为止，我已经发现最大三角形的顶点只会位于点云（或凸包）的外部点上，所以我编写了一个函数来做到这一点（在 nlogn 时间内使用 Graham 扫描）。

然而，这就是我卡住的地方。我可以弄清楚如何从这些点中找到最大三角形的唯一方法是在 n^3 时间使用蛮力，这在平均情况下仍然是可以接受的，因为凸包算法通常会剔除绝大多数点。然而，在点在一个圆上的最坏情况下，这种方法将失败。

有人知道更有效地做到这一点的算法吗？

注意：我知道 CGAL 有这个算法，但他们没有详细说明它是如何完成的。我不想使用库，我想学习这个并自己编程（并且还允许我将它调整到我想要它的操作方式，就像其他实现拾取共线点的格雷厄姆扫描一样我不想）。

I need to compute the area of the region of overlap between two triangles in the 2D plane. Oddly, I have written up code for the triangle-circle problem, and that works quite well and robustly, but I have trouble with the triangle-triangle problem.

I already first check to see if one entirely contains the other, or if the other contains the first, as well as obtain all the edge-wise intersection points. These intersection points (up to 6, as in the star of David), combined with the triangle vertices that are contained within the other triangle, are the vertices of the intersection region. These points must form a convex polygon.

The solution I seek is the answer to either of these questions:

1. Given a set of points known to all lie on the convex hull of the point set, compute the area of the convex hull. Note that they are in random order.
2. Given a set of half-planes, determine the intersecting area. This is equivalent to describing both triangles as the intersection of three half-planes, and computing the solution as the direct intersection of this description.

I have considered for question 1 simply adding up all areas of all possible triangles, and then dividing by the multiplicity in counting, but that seems dumb, and I'm not sure if it is correct. I feel like there is some kind of sweep-line algorithm that would do the trick. However, the solution must also be relatively numerically robust.

I simply have no idea how to solve question 2, but a general answer would be very useful, and providing code would make my day. This would allow for direct computation of intersection areas of convex polygons instead of having to perform a triangle decomposition on them.

Edit: I am aware of this article which describes the general case for finding the intersection polygon of two convex polygons. It seems rather involved for just triangles, and furthermore, I don't really need the resulting polygon itself. So maybe this question is just asked in laziness at this point.