标签: computational-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的答案 - 显然这个解决方案已经是最优的)
• 多边形中的最小内角是最大的

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

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

我想计算两条折线之间的距离d:

显然,我可以检查所有线段对的距离并选择最小距离,但这样算法运算符的运行时间为O(n ²).有没有更好的方法？

我有一个凸多边形P1的N点.该多边形可以是任何形状或比例(只要它仍然是凸的).

我需要P2使用原始多边形几何计算另一个多边形,但是"扩展"给定数量的单位.算法可以用于扩展凸多边形？

这个问题在这里已经有了答案:
Point in Polygon aka hit test
C#Point in polygon

给定在笛卡尔坐标系中用N线方程组成的随机多边形,是否有任何标准公式用于检查点(x,y)的隶属度？

简单的解决办法是让所有的线公式和检查点X这条线之下,高于线和其他线路,等权但这可能会是乏味的.

我应该注意,多边形可以是任何形状,具有任意数量的边,并且可以是凹的或凸的.

为方便起见,我已经添加了这些实用功能:

float slope(CGPoint p1, CGPoint p2)
{
    return (p2.y - p1.y) / (p2.x - p1.x);
}

CGPoint pointOnLineWithY(CGPoint p, float m, float y)
{
    float x = (y - p.y)/m + p.x;
    return CGPointMake(x,y);
}

CGPoint pointOnLineWithX(CGPoint p, float m, float x)
{
    float y = m*(x - p.x) + p.y;
    return CGPointMake(x, y);
}

我正在尝试使用给定的makefile 制作/编译wykobi库(计算几何),但我不断收到错误:

错误:显式实例化不应使用'inline'说明符[-fpermissive]

我怎么解决这个问题？

我有一组表示多边形顶点(x,y)的点.

points= [(421640.3639270504, 4596366.353552659), (421635.79361391126, 4596369.054192241), (421632.6774913164, 4596371.131607305), (421629.14588570886, 4596374.870954419), (421625.6142801013, 4596377.779335507), (421624.99105558236, 4596382.14190714), (421630.1845932406, 4596388.062540068), (421633.3007158355, 4596388.270281575), (421637.87102897465, 4596391.8018871825), (421642.4413421138, 4596394.918009778), (421646.5961722403, 4596399.903805929), (421649.71229483513, 4596403.850894549), (421653.8940752105, 4596409.600842565), (421654.69809098693, 4596410.706364258), (421657.60647207545, 4596411.329588776), (421660.514853164, 4596409.875398233), (421661.3458191893, 4596406.136051118), (421661.5535606956, 4596403.22767003), (421658.85292111343, 4596400.94251346), (421656.5677645438, 4596399.696064423), (421655.52905701223, 4596396.164458815), (421652.82841743, 4596394.502526765), (421648.46584579715, 4596391.8018871825), (421646.38843073393, 4596388.270281575), (421645.55746470863, 4596386.400608018), (421647.21939675923, 4596384.115451449), (421649.5045533288, 4596382.661260904), (421650.7510023668, 4596378.714172284), (421647.8426212782, 4596375.8057911955), (421644.9342401897, 4596372.897410107), (421643.6877911517, 4596370.404512031), (421640.3639270504, 4596366.353552659)]

我需要找到最小的封闭圆(区域,中心的x和y,以及半径)

我正在使用从此页面派生的python代码:Nayuki的最小封闭圈

当我运行代码时,结果每次都会改变,例如:

>>> make_circle(points)
(421643.0645666326, 4596393.82736687, 23.70763190712525)
>>> make_circle(points)
(421647.8426212782, 4596375.8057911955, 0.0) …

我想知道一个返回true或false的算法,告诉我是否可以围绕一组点A绘制一个圆,这样点B组中的任何点都不在其中,或者反过来(可能)围绕一组点B绘制圆圈,使得来自点集A的任何点不在其内部).

基本上,你有两组点作为输入,你需要确定是否可以围绕任何一个绘制一个圆,这样另一个点的任何一个点都不在其中.

我已经看过Megiddo的线性时间算法来解决最小的圆周问题,但问题是它只绘制了最小的圆,这意味着它在你需要一个大圆的情况下不起作用.

这是我的意思的图片:

在这张图片中,可以围绕红点集绘制一个非常大的圆圈,这样任何一个绿点都不在其中,因此Megiddo的算法将无法工作.