问题标签 [computational-geometry]

我正在尝试自动检测 3d 点云上的旋转轴。

换句话说，如果我取一个小的 3d 点云，选择一个单一的旋转轴，并以不同的旋转角度制作多个点的副本，那么我会得到一个更大的点云。

我的算法的输入是较大的点云，所需的输出是单对称轴。最终我将计算相互旋转的点之间的对应关系。

较大点云的大小约为 100K 点，旋转副本的数量未知。

在我的例子中，旋转角度有恒定的增量，但不一定跨越 360 度。例如，我可能有 0、20、40、60。或者我可能有 0、90、180、270。但我不会有 0、13、78、212（或者如果我有，我不在乎来检测它）。

这似乎是一个计算机视觉问题，但我无法弄清楚如何精确找到轴。输入通常非常干净，接近浮点精度。

我没有旋转/复制以制作更大点云的原始较小点云。我知道数据是合成的，噪音很小（通常是另一个程序的输出）。

我们不能轻易地计算较小云中可能的点数，因为不幸的是，这些点不会沿着轴重复。如果我们知道哪些点在轴上，那么我们可以想出可能的因素，但是我们已经解决了这个问题。

--

谢谢大家的建议。看起来我的最终算法将尝试使用 k-nn 度量提出匹配点的派系。每个派系都会给出一个轴。然后，我可以使用 RANSAC 将轴拟合到所有派系的结果。

在工业中，通常存在一个问题，您需要计算材料的最有效使用，无论是织物、木材、金属等。所以起点是给定尺寸的 X 数量的形状，由多边形和/或弯曲制成线，目标是给定尺寸的另一个多边形。

我假设许多当前的 CAM 套件都实现了这一点，但是没有使用它们或其内部的经验，使用什么样的计算算法来找到最有效的空间使用？有人可以指点我讨论这个话题的书或其他参考资料吗？

希望这里有一些计算几何学的人可以帮助我解决以下问题 -

请想象我在 3 空间中取一个自由移动的球，并通过定义一组不可通过的坐标 Sc（即 3 空间中不允许扩散球的任何部分重叠的点）在它周围创建一个“笼子”。这些点位于某个较大球体的体积 V(cage) 内，其中 V(cage) >> V(ball)。

假设一组不可通过的坐标 Sc，是否有一种计算上有效和/或很好的方法来确定球是否可以逃脱笼子？

请参阅我之前在 MathOverflow 上的帖子 - https://mathoverflow.net/questions/21911/when-can-a-freely-moving-sphere-escape-from-a-cage-defined-by-a-set-of-无言以对

我有具有线段、射线等的图像。我使用Bresenham 算法表示这些线段（意味着我使用此算法在两点之间获得的任何坐标）。现在我想做一些操作，比如找到两条线段之间的交点，找到一个向量到另一个向量的投影等等......问题是我不在连续空间中工作。使用 Bresenham 算法对线段进行近似。

所以我想要关于什么是最好和最有效的方法的建议？到 C++ 库或实现的链接也足够了。请推荐一些处理此类问题的书籍。

我的应用程序是表示地球表面上的形状（使用球体就足够了）。这些可以是点、线和多边形。坐标应该使用度数或弧度来定义（就像地理坐标一样）。

球面上两点之间的线段应位于其大圆上。多边形应该由这些线条的集合组成。此外，我想对提到的形状执行集合 - 基本操作，如交集、联合、差异、补码。这些操作只需要输出点的集合。

我尝试使用 CGAL 的3D Spherical Geometry Kernel和2D Boolean Operations on Nef Polygons Embedded on Sphere 来解决这个问题。实际上，我在球体上划线时已经遇到了问题。此外，CGAL 在欧几里得空间中工作，这仍然给我留下了必要的几何运算，以处理放置在球体上的大圆圈。

我的问题是，您是否可以帮助我实现 CGAL 中提到的功能，或者您是否可以推荐另一个用于 C/C++ 的库来做到这一点。非常感谢！

我有一个小竞赛问题，其中给出了一组二维点，形成一个三角形。这个三角形可以进行任意旋转，可以进行任意平移（都在 2D 平面中）并且可以在镜子上进行反射，但其尺寸保持不变。然后，他们给了我平面上的一组点，我必须在一个或多个几何运算后找到构成我的三角形的 3 个点。

例子：

我打赌它应该应用一些已知的算法，但我不知道是哪个。最常见的有：凸包、扫描平面、三角剖分等。

有人可以给小费吗？我不需要代码，只需要一个推送，拜托！

我正在寻找如下算法：

给定一组可能重叠的矩形（所有这些矩形都“不旋转”，可以统一表示为（左、上、右、下）连音等...），它返回一组最小的（非旋转）占据相同区域的非重叠矩形。

乍一看似乎很简单，但事实证明很棘手（至少要有效地完成）。

这个/想法/指针有一些已知的方法吗？

不一定是最小但启发式小集的方法也很有趣，产生任何有效输出集的方法也很有趣。

假设我有两个点，Point1 和 Point2。在任何给定时间，这些点可能位于不同的位置——它们不一定是静态的。

Point1 在时间 t 位于某个位置，其位置由连续函数 x1(t) 和 y1(t) 定义，给出时间 t 的 x 和 y 坐标。这些函数不可微分，它们是从线段分段构造的。

Point2 是相同的，具有 x2(t) 和 y2(t)，每个函数具有相同的属性。

可能妨碍可见性的障碍是简单的（和固定的）多边形。

如何找到可见性的边界点？

即有两种边界：点变得可见和不可见。

(x1(a), y1(a))对于变得可见的边界 i，存在一些 ϵ>0，因此对于任何实数 a，a ∈ (i-ϵ, i) ，Point1 和 Point2 不可见（即连接到的线段(x2(a), y2(x))穿过一些障碍物）。

对于 b ∈ (i, i+ϵ) 它们是可见的。

而对于变得不可见，情况正好相反。

但是我能找到一个精确的这样的边界吗？如果有，怎么找到？

我有 x1,y1 和 x2,y2 形成一条线段。我怎样才能得到另一条线 x3,y3 - x4,y4 与图片中的第一条线平行。我可以简单地将 n 添加到 x1 和 x2 以获得平行线，但这不是我想要的。我希望线条在图片中平行。

MI Shamos 在他 1978 年的论文中首先提出了在平面上找到“N”个圆盘/圆的交点/并集的问题：

Shamos，密歇根州“计算几何”博士 论文，耶鲁大学，纽黑文，CT 1978。

从那时起，在 1985 年，Micha Sharir 提出了一种 O(n log2n) 时间和 O(n) 空间确定性算法来解决圆盘交集/并集问题（基于修改后的 Voronoi 图）：Sharir, M. Intersection and nearest-pair questions for一组平面圆盘。暹罗.J计算机。14 (1985)，第 448-468 页。

1988 年，Franz Aurenhammer 提出了一种更有效的 O(n log n) 时间和 O(n) 空间算法，用于使用幂图（Voronoi 图的推广）进行圆相交/并集：Aurenhammer, F. 使用幂的改进的圆盘和球算法图表。算法杂志 9 (1985)，第 151-161 页。

早在 1983 年，Paul G. Spirakis 还提出了一个 O(n^2) 时间确定性算法和一个 O(n) 概率算法：Spirakis, PG Very Fast Algorithms for the Union of Many Circles。Rep. 98，计算部。科学，Courant 研究所，纽约大学，1983 年。

我一直在寻找上述算法的任何实现，专注于计算几何包，但我还没有找到任何东西。由于两者似乎都不重要，如果有人能指出我正确的方向，那就太好了！

也许建设性立体几何 (CSG) 包将具有用于重叠圆形基元的表面积特征？