标签: computational-geometry

给出飞机上的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个点的周长.

我想找到两个多边形之间的最小距离.我必须找到第一个形状的每个顶点与另一个顶点的所有顶点之间的最小最短距离.类似于Hausdorff距离,但我需要最小值而不是最大值.

所以我有大约16,000个75维数据点,并且对于每个点我想找到它的k个最近邻居(使用欧氏距离,如果这使得它更容易,则当前k = 2)

我的第一个想法是为此使用kd树,但事实证明,随着维数的增长,它们变得相当低效.在我的示例实现中,它仅比详尽的搜索稍快.

我的下一个想法是使用PCA(主成分分析)来减少维数,但我想知道:是否有一些聪明的算法或数据结构可以在合理的时间内完全解决这个问题？

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

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

我需要在一组点中找到"附近"的邻居.

上图中有10个点.红线是Delaunay三角剖分的边缘,黑色星标记边缘的中线,蓝线是Voronoi镶嵌.点1具有三个"近"邻居,即4,6和7,但不是2和3,它们几乎与边缘1-7一致,但距离更远.

识别近邻(或"好"边缘)的好方法是什么？看看这个图,在我看来,要么选择中点落在与Voronoi线交叉点的边缘,要么考虑作为"近"邻居那些触摸Voronoi单元的边缘可能是一个很好的解决方案(3-5的分类)可以去任何一种方式).有没有一种有效的方法来实现Matlab中的任何一个解决方案(我很乐意得到一个好的通用算法,然后我可以转换为Matlab,顺便说一下)？

我最近被一家GIS公司雇用来重写旧的地理信息库.所以我目前正在寻找一个好的计算几何库.我见过CGAL,这太棒了,但我的老板想要一些免费的东西.

所以我现在正在检查Boost.Geometry.这个库看起来很棒,但它似乎也在快速变化.很多事情还没有实现,邮件列表上讨论了很多问题.

因此我的问题是:Boost.Geometry足够成熟,所以我可以在它上面构建一些东西吗？或者设计仍在发展？

谢谢

我在Actionscript中创建了一个绘图应用程序(虽然我的问题不是与Actionscript相关).基本思想是在按下鼠标时开始绘画并跟踪鼠标移动.我想要的是:

1. 减少鼠标"噪音"和
2. 创造更平滑的线条.

现在,(1)是有问题的,因为我在几秒钟内就能获得数千个鼠标移动.由于(1)线条看起来很锯齿.当前的想法:当用户完成绘制线时,我将所有移动存储在一个数组中并减少它们(中位数阈值),然后使用样条算法重新创建一条线.

有更好的方法吗？

这是一个面试问题,面试已经完成.

给定一副长方形卡片,将它们随机放在一张矩形桌子上,这张桌子的大小远大于卡片大小的总和.有些卡片可能会随机重叠.设计一种算法,可以计算所有卡覆盖的表面积,并分析算法的时间复杂度.所有卡的每个顶点的所有坐标都是已知的.卡可以任何模式重叠.

我的想法:

按垂直坐标降序对卡片进行排序.

到达卡片的边缘或顶点后,从上到下垂直扫描卡片,继续扫描另一条扫描线,直至到达另一条边缘,然后找到位于两条线条之间的区域.最后,对位于两条线之间的所有区域求和并得到结果.

但是,如果区域不规则,如何计算位于两条线之间的区域是一个问题.

任何帮助表示赞赏.谢谢 !

我有一套2d points.它们X,Y coordinates位于标准的笛卡尔网格系统上(在本例中为a UTM zone).我需要在该点集中找到孔,最好能够设置找到这些孔的算法的灵敏度.通常这些点集非常密集,但有些可能密度低得多.

它们是什么,如果它有帮助的话,那就是田地里的土壤被采样的点,农业人们显然发现它们有用.有时在这些点样品中有巨大的岩石或沼泽地或满是小湖泊和池塘.

从点集中,他们希望我找到粗略定义这些孔的凹多边形.

我已经编写了找到外部凹面边界多边形的算法,并允许它们设置由算法形成的多边形粗糙或平滑的灵敏度.在那之后,他们想找到洞并将那些洞作为凹多边形给予它们,我猜在某些情况下可能是凸的,但这将是边缘情况而不是常态.

问题是我听过的关于这个问题的唯一论文是那些希望在太空中找到大空虚的天文学家完成的论文,我从来没有能够找到他们的一篇论文,其中的实际算法显示为除了粗略的概念描述之外的任何东西

我已经尝试了谷歌和各种学术论文搜索等,但到目前为止我还没有找到很多有用的东西.这让我想知道是否有这个问题的名字,我不知道所以我在寻找错误的东西或什么？

所以经过那个冗长的解释之后,我的问题是:有没有人知道我应该寻找什么,最好用定义明确的算法找到这方面的论文,或者有人知道一个他们可以指出我的算法吗？

任何帮助我解决这个问题的东西都会非常有用并且非常感激,即使只是正确的搜索短语,也会发现潜在的算法或论文.

这将实现的语言将是C#,但是从Mathematica软件包到其他任何东西的例子MATLAB or ASM, C, C++, Python, Java or MathCAD都可以,只要示例中没有一些调用就像是FindTheHole等等.FindTheHole没有定义或者是对于实现软件而言是专有的,例如,MathCAD示例通常具有很多.

下面是两个实际点集的例子,一个是密集的,一个是稀疏的,我需要找到它们中的区域:

我正在处理地理信息,最近我需要绘制一个椭圆.为了与OGC约定兼容,我不能原样使用椭圆; 相反,我使用多边形近似椭圆,通过采用椭圆包含的多边形并使用任意多个点.

我用于为给定数量的点N生成椭圆的过程如下(使用C#和虚构的Polygon类):

Polygon CreateEllipsePolygon(Coordinate center, double radiusX, double radiusY, int numberOfPoints)
{
    Polygon result = new Polygon();
    for (int i=0;i<numberOfPoints;i++)
    {
        double percentDone = ((double)i)/((double)numberOfPoints);
        double currentEllipseAngle = percentDone * 2 * Math.PI;
        Point newPoint = CalculatePointOnEllipseForAngle(currentEllipseAngle, center, radiusX, radiusY);
        result.Add(newPoint);
    }
    return result;
}

到目前为止,这对我很有帮助,但我注意到它有一个问题:如果我的椭圆是'矮胖',也就是说,radiusX比radiusY大得多,那么椭圆顶部的点数就是与椭圆左侧的点数相同.

这是浪费点的使用!在椭圆的上半部分添加一个点几乎不会影响多边形近似的精度,但在椭圆的左边部分添加一个点会产生重大影响.

我真正喜欢的是用多边形逼近椭圆的更好算法.我需要这个算法:

• 它必须接受点数作为参数; 可以接受每个象限中的点数(我可以在"有问题"的位置迭代地添加点,但我需要很好地控制我使用的点数)
• 它必须以椭圆为界
• 它必须包含正上方,正下方,直线向左,直线到椭圆中心右侧的点
• 它的面积应该尽可能接近椭圆的面积,当然优先考虑给定的点数(参见Jaan的答案 - 显然这个解决方案已经是最优的)
• 多边形中的最小内角是最大的

我想到的是找到一个多边形,其中每两条线之间的角度总是相同的 - 但不仅我不知道如何产生这样的多边形,我甚至不确定是否存在,甚至如果我删除限制!

有没有人知道如何找到这样的多边形？