多边形轮廓到多边形的无序浊点 [英] Unordered cloud point of polygon contour to polygon

问题描述

尊敬的Stackoverflow社区，

Dear Stackoverflow community,

我将不规则多边形的轮廓作为无序数据点(如此处的图所示: https://s16.postimg.org/pum4m0pn9/figure_4.png )，而我正在尝试对它们进行排序(即创建多边形).

I have contours of irregular polygons as unordered datapoints (like on the figure here: https://s16.postimg.org/pum4m0pn9/figure_4.png), and I am trying to order them (ie. to create a polygon).

由于多边形的非凸形状，我无法使用凸包外壳.我不能提出最小距离准则，因为轮廓的其他部分的某些点更近一些(例如:点A必须与B相连，但更近于C).由于轮廓的形状不规则，因此无法使用顺时针排序.

I cannot use the convex hull envelope because of the non convex shape of the polygon. I cannot ase a minimum distance criterion because some points of other parts of the contour lie closer (example: point A has to be joined with B, but is closer to C). I cannot use a clockwise ordering because of the irregular shape of the contour.

有没有人知道一种实现(最好在Python中)从起点重新排序数据点的算法的方法?

Do anyone knos a way to implement (preferentially in Python) an algorithm that would reorder the datapoints from a starting point?

推荐答案

在这里在2D点集中找到孔有关如何解决此问题的一些想法

look here finding holes in 2D point set for some ideas on how to solve this

1. 我将创建点密度图(类似于以上链接的答案)
2. 创建所有行的列表
   • 因此添加所有可能的线组合(在闭合点之间)
   • 不与地图上的空白区域相交

1. I would create point density map (similar to above linked answer)
2. create list of all lines
   • so add to it all possible combination of lines (between close points)
   • not intersecting empty area in map

• 通过他们分割最近的线...
• 取决于您的地图网格大小和点密度，您可能需要混合/平滑地图以覆盖空白
• 如果网格尺寸太大，那么您可能会错过点A，C之间的图像之类的细节
• 如果它太小，则在低密度区域附近可能会出现明显的间隙

但是正如所说的，它有一个以上的解决方案，因此您需要稍微调整一下，以使所需的输出可能是一些用户输入，以便稍微摇动该解决方案，直到找到所需的解决方案为止...

But as said this has more then one solution so you need to tweak this a bit to make the wanted output perhaps some User input for shaking the solution a bit until wanted solution found...

[notes]

您可以将其作为更多的凸多边形来处理...

you can handle this as more covex polygons ...

• 仅在符合缠绕规则的情况下添加行
• 找不到更多行时停止
• 从未使用的点重新开始
• 最后尝试连接找到的非闭合多边形...

这篇关于多边形轮廓到多边形的无序浊点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！