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

问题描述

亲爱的 Stackoverflow 社区，

我有不规则多边形的轮廓作为无序数据点(就像这里的图:

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

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

解决方案

看这里 在二维点集中寻找洞关于如何解决这个问题的一些想法

1. 我会创建点密度图(类似于上面链接的答案)
2. 创建所有行的列表
   • 因此添加所有可能的线组合(在接近点之间)
   • 不与地图中的空白区域相交
3. 删除所有相交线
4. 对线路应用闭环/连通性分析
5. 然后处理剩余的未使用点
   • 通过它们分割最近的线...
   • 根据您的地图网格大小和点密度，您可能需要混合/平滑地图以覆盖间隙
   • 如果网格尺寸太大，那么您可能会错过点 A、C 之间图像上的细节
   • 如果它太小，那么在低密度区域附近可能会出现明显的间隙

但如前所述，这有不止一个解决方案，因此您需要稍微调整一下，以使想要的输出可能是一些用户输入，用于稍微摇晃解决方案，直到找到想要的解决方案...

[注释]

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

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

Dear Stackoverflow community,

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).

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.

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

解决方案

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

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
3. remove all intersecting lines
4. apply closed loop / connectivity analysis on the lines
5. then handle the rest of unused points
   • by splitting nearest line by them ...
   • depending on you map grid size and point density you may need to blend/smooth the map to cover gaps
   • if grid size is too big then you can miss details like on the image between points A,C
   • if it is too small then significant gaps may occur near low density areas

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 ...

• add line only if winding rule met
• stop when no more lines found
• start again with unused points
• and in the end try to connect found non closed polygons ...

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