相关疑难解决方法(0)

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

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

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

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

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

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

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

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

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

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

我有一些地理数据(下面的图像显示了河流的路径为红点),我想用多段三次贝塞尔曲线近似.通过对计算器等问题,在这里和这里我发现由Philip J.施耐德从"图形宝石"的算法.我成功地实现了它并且可以报告即使有数千个点它也非常快.不幸的是,速度带来了一些缺点,即装配非常不合适.请考虑以下图形:

红点是我的原始数据,蓝线是由Schneider算法创建的多段贝塞尔曲线.如您所见,算法的输入是一个容差,至少与绿线表示的一样高.然而,该算法创建了具有太多急转弯的贝塞尔曲线.你也会在图像中看到这些不必要的急转弯.很容易想象,对于所示数据,具有较小急转弯的贝塞尔曲线,同时仍保持最大公差条件(仅将贝塞尔曲线稍微推向品红色箭头的方向).问题似乎是算法从我的原始数据中选取数据点作为各个贝塞尔曲线的终点(品红箭头指示一些嫌疑人).由于贝塞尔曲线的端点受到限制,很明显该算法有时会产生相当尖锐的曲率.

我正在寻找的是一种算法,它使用具有两个约束的多段贝塞尔曲线来近似我的数据:

• 多段贝塞尔曲线绝不能超过数据点一定距离(由Schneider算法提供)
• 多段贝塞尔曲线绝不能产生过于尖锐的曲率.检查此标准的一种方法是沿多段贝塞尔曲线滚动具有最小曲率半径的圆,并检查它是否沿其路径接触曲线的所有部分.虽然看起来有更好的方法涉及一阶和二阶导数的叉积

我发现可以创造更好拟合的解决方案或者仅适用于单个贝塞尔曲线(并且省略了如何在多段贝塞尔曲线中找到每个贝塞尔曲线的良好起点和终点的问题)或者不允许最小曲率约束.我认为最小曲率约束是这里的棘手条件.

这是另一个例子(这是手绘而不是100%精确):

让我们假设图1显示了两者,曲率约束(圆必须适合整个曲线)以及任何数据点与曲线的最大距离(恰好是绿色圆的半径).图2中红色路径的成功近似显示为蓝色.该近似值符合曲率条件(圆可以在整个曲线内滚动并在任何地方触摸它)以及距离条件(以绿色显示).图3显示了路径的不同近似值.虽然它符合距离条件但很明显圆圈不再适合曲率.图4显示了一条不可能用给定约束近似的路径,因为它太尖了.该示例应该说明为了正确地近似路径中的一些尖转弯,算法必须选择不属于路径的控制点.图3显示,如果选择沿路径的控制点,则不能再满足曲率约束.此示例还显示算法必须退出某些输入,因为无法使用给定的约束来近似它.

这个问题是否存在解决方案？解决方案不一定要快.如果需要一天时间来处理1000点,那就没问题了.解决方案也不必是最佳的,因为它必须导致最小二乘拟合.

最后,我将用C和Python实现它,但我也可以阅读大多数其他语言.

我们目前正在使用以下算法来检测地理点是否位于复杂多边形内。这工作正常，除非多边形穿过 180\xc2\xb0 经线。

例如，在多边形中未检测到点 (-170, 60) 160,65,0 160,15,0 -160,15,0 -160,65,0 160,65,0

看下图：\n[Img]http://tinypic.com/r/14x2xl1[/img]\n我想要红框中的所有内容。不是黄盒子！

    public static bool IsCoordinateInPolygon(IList<KMLCoordinate> polygon, KMLCoordinate testPoint)\n    {\n\n        bool result = false;\n        int j = polygon.Count - 1;\n        for (int i = 0; i < polygon.Count; i++)\n        {\n            if (polygon[i].Latitude < testPoint.Latitude && polygon[j].Latitude >= testPoint.Latitude || polygon[j].Latitude < testPoint.Latitude && polygon[i].Latitude >= testPoint.Latitude)\n            {\n                if (polygon[i].Longitude + (testPoint.Latitude - polygon[i].Latitude) / (polygon[j].Latitude - polygon[i].Latitude) * (polygon[j].Longitude - polygon[i].Longitude) < testPoint.Longitude)\n                {\n                    result = !result;\n …

我有很多像下面的图像(只有白色和黑色):

我最后的问题是找到匹配良好的椭圆.不幸的是,真正使用过的图像并不像这样.它们可能会变形一些,这使得椭圆匹配可能更难.

我的想法是找到"断点".我在下面的图片中标记它们:

也许这些点可以帮助匹配省略号.最终结果应该是这样的:

有人知道可以用什么算法来找到这些断点吗？或者甚至更好地进行良好的椭圆匹配？

非常感谢你