标签: computational-geometry

我需要解决动态凸包算法问题,即保持2D点的凸包,我可以添加和删除点.

天真的做法很明显O(N); 无论何时N添加/删除其中一个点,我们都会从头开始重新计算凸包.但是,我无法承受线性时间,因此我正在寻找一种次线性算法.到目前为止,我已经找到了一堆纸,所有这些都描述了一些具有疯狂时间限制的复杂算法,这需要花费很长时间才能实现.即使是最古老的高效算法,由于Overmars和Leeuween,这O(log^2 N)似乎太复杂了.(像往常一样,这些论文中描述的大多数算法在结构/算法方面都有很多依赖性来自其他参考文献)

我正在寻找更简单,更不一定新颖的东西,在最坏的情况下(例如O(sqrt N))在线性方面表现优于线性.最后,我不介意时间是否摊销.有任何想法吗？

(简单来说,我主要是指不需要超过几百行代码的东西.)

我有2个三角形和顶点p0,p1,p2,p3.这两个三角形共享边缘.从这两个三角形我想制作一个由4个顶点给出的四面体.我使用的库要求"应该给出4个顶点,使得在从外面观察时,在图中定义四面体面的四个顶点三元组以逆时针顺序出现".假设两个三角形中的一个是p0,p1,p2,则将法线计算为(p1-p0)(交叉)(p2-p0).有人可以告诉我一种方法来确保满足这个条件吗？

四面体网格中的点位置是否有任何经过验证的数据结构,其中四面体都是不相交的,但彼此"接触"？即大多数面孔都是正好两个四面体的面孔.

按位置我的意思是我想找出给定点位于哪个四面体中,或者它是否位于任何四面体中.

到目前为止,我尝试过:

1. 一个简单的KD树.这对我的需求来说太慢了,因为平均树深非常高,我仍然有很多单独的四面体在每片叶子中进行测试.

2. 一个网格,包含每个单元格的所有交叉四面体.这似乎工作得更好,但仍然不够快.首先,网格包含许多空单元格,因为我的整体网格不是非常"四四方方".其次,大多数实际上含有四面体的细胞确实含有大量细胞(10+).我想这是因为很多四面体共享每个顶点,一旦顶点在一个单元格中,所有相邻的四面体也是如此.

关于输入数据的一些进一步信息:网格通常不是凸的并且可以具有孔或内含物.虽然最后两个有点不太可能,但我必须处理它们,如果没有(昂贵和复杂的？)预处理,这使得"行走"变得不可能.

好吧,近似一个带有多边形的圆圈和毕达哥拉斯的故事可能是众所周知的.但另一种方式呢？

我有一些多边形,实际上应该是圆圈.但是,由于测量误差,它们不是.所以,我正在寻找的是最能"近似"给定多边形的圆.

在下图中,我们可以看到两个不同的例子.

我的第一个Ansatz是找到点到中心的最大距离以及最小值.我们正在寻找的圈子可能介于两者之间.

这个问题有没有算法？

我有一组2D点,没有组织,我想找到这个集合的"轮廓"(不是凸包).我不能使用alpha形状,因为我有一个速度目标(在普通计算机上不到10毫秒).我的第一种方法是计算网格并找到轮廓正方形(正方形,其中空方块作为邻居).所以我认为我有效地缩减了我的点数(大致从22000到3000).但是我仍然需要改进这个新的集合.

我的问题是:如何在绿点中找到真实的轮廓点？

我在3D空间中有一组点(其中100万,可能更多,如10或1亿)形成一个球体(它们填充球体 - 它们不仅仅在表面上)我希望建立将每个球体连接到其第一个邻居的四面体...寻找四面体化,到目前为止,我发现的只有:

• 用于网格化的算法,但据我所知,它们填充空白空间,而我的点是固定的.
• 用于表面观察的算法,这是非常无关紧要的
• 用于3D图像观察的算法(在医学领域,大多数情况下):更接近但不完全诀窍.

我怎样才能做到这一点？

2014-08-09首先,感谢大家的建议!我是 - 现在仍然是 - 在假期,只是路过来检查是否有人回答......我并没有失望!!!! :-)我想我会首先尝试CGAL,并会从那里看到.我在O(n2)的同一组点上进行了其他数据计算,我预计它将持续大约1周,所以几个小时就不会那么糟糕.分钟将是梦想成真!

假设我在6维空间中给出了一个点云,我可以根据需要进行密集.这些点变成位于低维多面体的表面上(即点矢量(x1,x2,... x6)看起来是共面的).

我想找到这个未知多面体的顶点,我当前的尝试通过Python中的scipy接口使用qhull算法.在开始时,我只会得到错误消息,显然是由较低维度输入和/或许多退化点引起的.我尝试了几种蛮力方法来消除退化点,但不是很成功,所以最后,我想所有这些点都必须位于凸壳上.

这个问题非常有用,因为它建议通过主成分分析减少尺寸.如果我将点投影到4D超平面,则qhull算法运行时没有错误(对于任何更高的维度,它不会运行).

from scipy.spatial import ConvexHull
from sklearn.decomposition import PCA

model = PCA(n_components=4).fit(initial_points)
proj_points = model.transform(initial_points)
hull = ConvexHull(proj_points, qhull_options = "Qx")

上述问题的答案提到,在计算出投影点的凸包后,需要将单纯形变换回来.但是qhull输出只包含索引,为什么这些索引与初始点的索引不匹配？

现在我的问题是我不知道使用哪种精度来实际获得正确的顶点.无论我对点云的密集程度如何,所获得的顶点随着精度的不同而不同.例如,对于(10000,6)数组中的初始点,我得到(其中E0.03是其工作的最大值):

hull1 = ConvexHull(proj_points, qhull_options = "Qx, E0.03")
print len(hull1.vertices)
print hull1.vertices

5
[ 437 2116 3978 7519 9381]

并将其绘制在轴0,1,2(其中蓝点代表初始点云的选择)的某些(非信息丰富的)投影中:

但是为了获得更高的精度(当然),我会得到一个不同的集合:

hull2 = ConvexHull(proj_points, qhull_options = "Qx, E0.003")
print len(hull2.vertices)
print hull2.vertices

29
[  74   75  436  437  756 1117 2116 2366 2618 2937 3297 3615 3616 3978 3979
 4340 4561 4657 4659 4924 …

我正在制作一个图像处理项目,而且我已经陷入了项目的一个步骤.这是情况;

这是我的面具:

我想要检测可以适合这个蒙版的最大尺寸矩形.

我正在为我的项目使用MATLAB.你知道实现这个目标的任何快速方法吗？任何代码示例,方法或技术都会很棒.

编辑1:以下两种算法适用于大量案例.但是在一些困难的情况下,他们都给出了错误的结果.我在我的项目中使用了它们.

我有一堆2D点.你可以在左边的图片上看到它们.它们形成一些带有几个兔子耳朵的戒指.我的目标是找到大的内循环/椭圆,你可以在右侧看到.

什么样的算法对这种情况有用.

我尝试了RANSAC算法的一种变体(取5个随机点,形成一个椭圆,确定一个分数并重复).我以某种方式设计了评分函数,椭圆内部的点得到了很多负点,并且在外面指向,但非常接近得到很多积极点.但结果并不乐观.算法找到了环,但我得到了一些环的随机椭圆,而不是我想要的大内椭圆.

那里有什么好的策略吗？

我正在尝试从以下方法中找到一种更有效的方法来确定一个点属于哪个六角形：

1. 点数组-出于争论的考虑，为10000点。
2. 六边形的中心点数组，大约为1000个六边形。
3. 每个点将恰好属于一个六边形，一些（大多数）六边形将为空。
4. 六边形形成一个完美的网格，一个六边形的点从左上角开始（它将与整个区域的边缘重叠）。

我当前的解决方案有效，但是n * (m log m)我认为在哪里n=length(points)和都比较慢m=length(hexagons)。

我怀疑我可以做得比这好得多，想到的一种解决方案是根据点和六边形到任意点（也许是中间，也许是一个角）的距离对它们（仅一次）进行排序，然后遍历这些点在六边形的一个子集上，从第一个六边形开始，该第一个六边形的到该点的距离> =，到最后一个匹配的六边形。类似地，一旦（点->参照点）和（六边形中心->参照点）之间的距离差大于六边形的“半径”，我们可以停止查看六边形。从理论上讲，由于我们知道每个点都将属于一个六角形，所以我什至不必考虑这种可能性。

我的问题是：是否有很多做比这更好的办法？就复杂性而言，我认为最坏的情况会稍微好一些，n * m但平均情况应该很好，大概在的范围内n * 20（例如，我们只需要查看每个点20个六边形）。以下是我目前效率不高的解决方案，以供参考。

points.forEach((p) => {
  p.hex = _.sortBy(hexes, (hex) => {
    const xDist = Math.abs(hex.middle.x - p.x);
    const yDist = Math.abs(hex.middle.y - p.y);
    return Math.sqrt((xDist * xDist) + (yDist * yDist));
  })[0];
});