如何将点分为两组——轮廓线的上部和下部

Question

3

我有一些三维坐标点(x,y,z)的列表对于每个列表，我想将其分成两个列表，一个包含剖面上部的点，另一个包含下部的点，就像这样：

enter image description here

我的问题是：如何从具有它们的坐标(x,y,z)的点中确定哪些点应该属于上部，哪些点应该属于下部。

- Pawel Troka

很抱歉，它如果是什么呢？ - Pawel Troka

我在考虑一种快速而简单的方法（如果可以的话），就是找到最左边的点，并将其和接下来的 n/2 个点（按顺时针方向）标记为“顶部”。然而，这只适用于特定情况，你已经确认不是这种情况了。 - Geobits

1

如果这些点总是形成一个封闭曲线，你可以计算曲线的外法向量，并且任何在法向量中具有+y分量的点都将是“上部分”。 - Mark Ping

@MarkPing 我喜欢那个想法，但它是否也会捕捉到右上方的一些内容？例如，图像中最底部的形状在右侧会有一些y+法线。 - Geobits

@MarkPing 听起来很有趣，但我该如何计算呢？ - Pawel Troka

显示剩余4条评论

3个回答

1

首先，在每个相邻点之间创建“线”。假设这些点按顺序围绕着循环给出，这应该很容易。

然后，从0,0（左上角）到每个点投射一条线。如果它与另一条线相交以到达那里，它就不在上侧。如果没有，则是。

它的时间复杂度为O(n^2)，所以我确定有更好的解决方案，但对于小型点集来说，它应该可以胜任。请注意，它不能用于非常凹的形状，但对于所有显示的形状都有效。

- Geobits

好的，我现在明白了。我会尝试实现它的。 - Pawel Troka

1

优化这个算法可以使用扫描线算法，其中扫描线朝“上”方向（朝0,0？）。这将其降至O（n log n）。 - Mark Ping

1

将相邻的边连接起来形成线条，逆时针角度为正.. 在云的上部，连续的线条角度逐渐增加.. 而在下部，连续的线条角度逐渐减小..

一些试错应该会带你找到合适的启发式方法..

enter image description here

- Kshitij Banerjee

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ante · Accepted Answer

由于很多时候点可以以“一半”的方式分割，因此有更多的标准来分割它们是很好的。

在这种情况下，似乎您正在寻找一条曲线，可以将点云分割成与该点云相似形状的形状。适合覆盖您的形状的曲线类型可以帮助。二阶或三阶多项式可能适用于这些形状。

第二个想法是创建通过“几何中心”的东西。在2D情况下，您可以使用中轴线方法。可以通过Delaunay三角剖分计算点云。如果点接近某个平面，则可以将它们投影到该平面上并使用此方法。