我有很多多边形。理想情况下,所有的多边形不能相互重叠,但它们可以彼此相邻。
但实际上,我必须允许轻微的多边形重叠(由一定的公差定义),因为所有这些多边形都是从用户手绘输入获得的,这并不像我想要的那样精确。
我的问题是,是否有任何软件库组件:
- 允许输入多边形范围
- 检查多边形重叠是否超过预先指定的公差
- 如果是,则停止,否则继续
- 通过将共同的顶点和边缘分组在一起,为多边形创建坐标和元素的网格?
- 更重要的是,链接回网格边缘到原始多边形的边缘?
或者之前有人解决过这个问题吗?
这个问题是GIS应用程序的日常"面包"-这就是这里所做的。我们也在地理信息系统课程中学到了这一点。看看GIS系统是如何解决这个问题的。例如,ArcGIS定义了所谓的拓扑规则,并有一些功能来检查编辑的特征是否拓扑正确。见http://webhelp.esri.com/arcgisdesktop/9.2/index.cfm?TopicName=Topology_rules
这很长,只是因为问题太大了。我试着根据你的要点来整理我的评论。
组件绘制多边形
我的猜测是,如果没有提供更多的信息,你将有有限的成功-一个组件来绘制多边形将非常耦合到语言和UI范例你正在使用的项目的其余部分,即。web组件的代码看起来与本地组件非常不同。
也许另一种选择是将流程的这个元素从您正在尝试做的其他事情中分离出来。有一些非常棒的预先存在的编辑器,你可以使用它们来创建2d和3d多边形。
Inkscape是矢量图形编辑器的一个示例,它可以很容易地输入2d多边形,并且具有生成输出SVG的优势,这相当容易解析。
在三维Blender是一个开源的编辑器,可以用来产生任意的几何图形,可以导出为多种格式。
如果你可以使用google-maps API(可能在原生HTML渲染控件中),并且你对在地图叠加上添加空间点感兴趣,你可能会对stackoverflow上的相关点击绘制多边形问题感兴趣。从过去的经验来看,其他地图api如OpenLayers也支持类似的方法。
检查多边形是否重叠
Thomas T在他的回答中指出,有一系列相关的谓词可以用来解决这个问题和相关的查询。如果你只是在二维空间中寻找重叠和其他集合理论运算(并、交、集差)你可以使用General Polygon Clipper
你可能还需要考虑稍微更一般的问题,当两个多边形没有重叠或共享一个顶点时,他们应该。您可以使用闵可夫斯基和来扩展(放大)二维和三维多边形以避免此类问题。计算几何算法库有这些算法的鲁棒实现。
我认为这是更有可能,你真的在寻找一个软件,可以执行顶点焊接,克里斯特·埃里克森的书实时碰撞检测包括广泛的和非常可读的描述,在这个领域的基础知识,也对边缘断裂,裂纹检测,t型结等相关问题。然而,尽管书中包含了代码片段,但据我所知,没有现成的库可以解决这些问题,特别是,除了基本顶点焊接之外,没有给出任何完整的实现。
显然,所有的3D软件包(blender, maya, max, rhino)都包含内置的软件和工具来解决这个问题。
基于顶点对多边形进行分组
从过去的经验来看,这是开发软件来解决这个领域的问题最耗时的部分之一。它需要对图论和算法有合理的理解才能遍历边界。值得依靠一个立体的几何或图形库来为您完成繁重的工作。在过去,我用igraph取得了成功。
将更新后的多边形链接回原始多边形
再一次,从过去的经验来看,这只是一个仔细记账的例子,以及一些非常仔细的预先设计网格类。我想给出更多的建议,但即使在过去六个月的大部分时间里,我仍然在努力寻找一个"好的"方法来做到这一点。
其他评论
如果您正在与用户交互,我强烈建议尽可能使用"快照"编辑器来避免此问题,将所有用户输入的点四舍五入到网格中。这将有望大大减少您必须做的工作量。
是的,您可以使用OGR。它有python绑定。具体来说,Geometry类有一个Intersects方法。我不太明白你第4点和第5点想要什么。