标签: computational-geometry

如何计算三角形(指定为三(X,Y)对)和圆(X,Y,R)之间的交叉区域？我做了一些搜索无济于事.这是为了工作,而不是学校.:)

它在C#中看起来像这样:

struct { PointF vert[3]; } Triangle;
struct { PointF center; float radius; } Circle;

// returns the area of intersection, e.g.:
// if the circle contains the triangle, return area of triangle
// if the triangle contains the circle, return area of circle
// if partial intersection, figure that out
// if no intersection, return 0
double AreaOfIntersection(Triangle t, Circle c)
{
 ...
}

给定一个完全由四边形组成的网格,其中每个顶点都具有效价n(n> = 3),并且不在同一平面上,我需要从一组封闭的种子顶点中找到网格中每个顶点的距离.也就是说,给定一个或多个网格顶点(种子集),我需要构建一个距离图,该距离图存储每个网格顶点距种子集的距离(距离自身的距离为0).

在花了一些时间寻找可能的解决方案之后,我得到了以下图片:

1)这不是微不足道的,并且在过去20年左右的时间里已经开发了不同的方法

2)考虑3d域的每个算法都限于三角域

说,这是我得到的图片:

Dijkstra算法可以用作在网格边缘之后找到2个顶点之间的最短路径的方法,但是它非常不准确并且将导致错误的测地线.Lanthier(洛杉矶)提出了改进,但错误仍然很高.

Kimmel和Sethian(KS)提出了一种快速行进方法-FMM-来解决Eikonal方程,解决计算从种子点开始的波传播并记录波穿过每个顶点的时间的问题.不幸的是,这个算法虽然简单易于实现,但仍然会带来非常不准确的结果,必须注意避免使用钝角三角形,或者以非常特殊的方式处理它们.Novotni(NV)解决了单个种子场景中(KS)精度的问题,但我不清楚是否:

a)它仍然受到钝角问题的困扰

b)当在多种子点场景中使用时,必须为每个种子实施单个FMM,以便从每个种子中找到每个网格顶点的最小距离(即,在10个种子点场景中,FMM将具有每个网格顶点运行10次)

另一方面,Mitchell等人提出了导致0错误的精确算法-MMP-.(MI)在87年,AFAIK从未真正被扼杀(可能是由于所需的计算能力).同样的方法,Surazhsky&al.(SU)提供了基于MMP的替代精确算法,其在速度方面应该优于后者,仍然导致正确的结果.不幸的是,计算所需的计算能力,即使比原始MMP小得多,仍然足够高,因此此时实时交互式实现是不可行的.(SU)也提出了他们的精确算法的近似,他们称之为平精确.它应该花费相同的FMM计算时间,同时只带来1/5的错误,但是:

c)我不清楚它是否可用于多种子方案.

Chen&Han(CH)和Kapoor(KP)已经提出了其他精确的最短路径算法,但是第一种算法绝对慢,第二种算法太复杂而无法在实践中实施.

所以..底线是:我需要一组距离,而不是两点之间的最短路径.

如果我做对了,

要么我使用FMM来获取单个通道中每个顶点的距离,

-要么-

使用另一种算法来计算从每个网格顶点到每个种子点的测地线,并找到最短的一个(如果我把它弄好,这意味着在每个网格顶点的每个种子点上调用该算法,即在10,000个顶点网格上和一个50分的种子集,我将不得不计算500,000测地线,以获得10,000最短的一个)

我错过了什么吗？FMM是一次通过多种种子距离的唯一方法吗？有人知道平面精确算法是否可用于多种子点场景？

日Thnx

笔记:

(洛杉矶):Lanthier等."在多面体表面上逼近加权最短路径"

(KS):Kimmel,Sethian"在流形上计算测地线路径"

(NV):Novotni"计算三角网格上的测地距离"

(MI):米切尔等人."离散测地线问题"

(SU):Surazhsky,Kirsanov等."网格上的快速精确和近似测地线"

(CH):Chen,Han,"多面体的最短路径"

(KP):Kapoor"高效计算geodeisc最短路径"

覆盖所有n点所需的半径为r的最小圆数是多少？r和n将作为输入给出,接着是n对整数,表示n个点的xy坐标.r是实数且大于0.n <20.

如果该点位于圆内,则圆圈覆盖一个点.如果点与圆心之间的距离小于或等于r,则点位于圆内.

给定一组积分S (x, y, z).如何找到convex hull那些点？

我尝试从这里理解算法,但是得不到多少.

它说:

首先将所有点投影到xy平面上,并通过选择具有最高y坐标的点然后执行礼品包装的一次迭代以确定边缘的另一个端点来找到肯定在船体上的边缘.这是不完整船体的第一部分.然后我们迭代地构建船体.考虑这第一个优势; 现在找到另一个点,以形成船体的第一个三角形面.我们通过选择点来使得所有其他点位于该三角形的右侧,当适当地观察时(就像在礼品包装算法中一样,我们选择边缘使得所有其他点位于右侧)那边缘).现在船体有三条边; 继续,我们任意选择其中一个,并再次扫描所有点以找到另一个点来构建具有此边缘的新三角形,并重复此直到没有剩余边缘.(当我们创建一个新的三角形面时,我们向池中添加两条边;但是,我们必须首先检查它们是否已经添加到船体中,在这种情况下我们忽略它们.)有O(n)个面,每次迭代需要O(n)时间,因为我们必须扫描所有剩余的点,给出O(n2).

任何人都可以用更清晰的方式解释它或建议一种更简单的替代方法.

我有一个3D实体,表示为一组多面体凸壳的联合.(或者单个凸起,如果这样可以使事情变得更容易.)我想将该实体近似为一组球体的并集,以最小化集合中球体的数量和近似中的误差.(后一个目标是刻意模糊的:任何合理的误差度量都可以.同样,目标组合的方式在空中;要么球体的数量或误差度量可能受到限制,要么两者的某些功能可以最小化.我不想把自己指定到一个角落.)

近似值不需要完全包含原始集合或完全包含在原始集合中.每个球体可以具有任意半径.

这感觉就像NP完全的问题,并且在任何情况下都不太可能使用精确方法,所以我假设解决方案在于随机优化领域.感觉k-means的某些变体可能适合(将未覆盖的位置分配给它们最近的球体,并精炼球体以覆盖其中的一些),但我不确定如何处理多重覆盖的位置,或者如何找到局部的,不一定是覆盖 - 即使对于单个球体也是最佳的.此外,对于迭代方法,效率很重要,并且执行3D布尔操作不会有效.

我想解决在线编程竞赛中的几何问题.但每当我读到它们时,我发现它太难了.请提供一些我可以研究计算几何的书籍和资源.

我一直在研究基于Qhull(R中的几何包)的R和MatLab中的一些函数,将圆形图中的局部笛卡尔X,Y,Z点投影到球面(theta,phi,R),以0为中心, 0,0.由于所有的Z值在原始坐标中都是正的(X和Y的中心位于0),这给了我所需的半球投影(点颜色按Z值缩放),用radial.plot绘制( )R plotrix的功能,使用phi(方位角)和theta(极角):

对于球面变换,在以0,0,0为中心之后,而不是使用Bourke(1996)的计算,我使用维基百科上列出的ISO规范(而不是物理惯例).

r     <- sqrt(x^2 + y^2 + z^2)
theta <- acos(z/r)
phi   <- atan2(y,x)

我想知道在这个半球投影中包含给定类点的Voronoi单元区域,保留透视失真.虽然计算二维笛卡尔X,Y点的二维Voronoi图很简单,但将这个Voronoi图转换为二维球形可能无法产生预期的结果,是吗？也许最好直接从半球投影点计算Voronoi图,然后返回每个细胞的面积.

更新:我已经解决了.我的解决方案将在新的R包中共享,我将在此处发布.

我正在寻找一种算法,我可以检查凸多边形(形状1)是否适合另一个多边形(形状2).

我的第一项研究将我带到了"包装不规则形状".这在我看来有点矫枉过正.我只有一个容器和一个对象.

形状1通常是凸多边形.形状2可以是凸的或凹的.

我的应用:我有三维激光扫描仪测量原木,这给我形状2.我也有不同的切割轮廓,我认为凸形船体,形状1.

现在我想检查切割轮廓是否适合我的激光轮廓.

给出飞机上的n个点.No 3是共线的.

给定数k.

找到k个点的子集,使得k个点的凸包具有k个点的子集的任何凸包的最小周长.

我可以想到一个天真的方法在O(n ^ kk log k)中运行.(找到大小为k的每个子集的凸包并输出最小值).

我认为这是一个NP问题,但我找不到任何适合减少的东西.

有人对这个问题有什么想法？

一个例子,

the set of n=4 points {(0,0), (0,1), (1,0), (2,2)} and k=3

结果:

{(0,0),(0,1),(1,0)}

由于该组包含3个点,因此结果的凸包和周长小于任何其他3个点的周长.

Bentley-Ottoman算法查找一组线段中的所有交叉点.对于一个众所周知且重要的算法,Bentley-Ottmann算法的C++实现似乎很奇怪 - 可以处理所有退化情况的实现(即,对扫描线和交叉点的数量没有特殊假设,等等on) - 根本没有.我能找到的唯一代码就在这里,但它似乎没有处理广义的情况.

Bentley-Ottmann算法是否已经在任何经过​​良好测试的库中实现,例如Boost或LEDA？如果是的话,我可以参考吗？