简化的凹壳
问题：
给定：与 3d k 边非凸多边形强相关的 n 个点，其中 n >>> k
查找：与点的原始几何形状相匹配的最佳拟合凹包
尝试的解决方案：
警告：伪代码
segments = []
for each point in image:
#segment points into planes via comparing approximate normals
#actual implementation is more complicated
findSegment(image,point)
for each segment in image:
#transform coordinate system to be a
#2D-plane perpendicular to the normal of segment
transform(segment, segment.normal)
edges = findEdges(segment)
polygonHull = reconstructPolygon(edges)
#transform back to original coordinate system
transform(segment, segment.normal)
示例：< /strong>
___
| | |
| \__ ==> | ___
| | |__/ /_____
|_______| / / \_
/ /_____/
/
输入只是一个高密度点云，它是多边形平面内近似均匀分布的随机点，带有一点噪声。
输出将是 3d 点中多边形的顶点。
我的问题是，有没有更好的方法来解决这个问题？上述解决方案的问题是点可能有噪音。此外，将点光栅化为二维，然后执行边缘查找的成本相当高。
任何指点都会很棒。提前致谢
Problem:
Given: n points that are strongly correlated to a 3d k-sided non-convex polygon, where n >> k
Find: the best fit concave-hull that matches the original geometry of the points
Attempted solutions:
Warning: pseudocode
segments = []
for each point in image:
#segment points into planes via comparing approximate normals
#actual implementation is more complicated
findSegment(image,point)
for each segment in image:
#transform coordinate system to be a
#2D-plane perpendicular to the normal of segment
transform(segment, segment.normal)
edges = findEdges(segment)
polygonHull = reconstructPolygon(edges)
#transform back to original coordinate system
transform(segment, segment.normal)
Example:
___
| | |
| \__ ==> | ___
| | |__/ /_____
|_______| / / \_
/ /_____/
/
Input would be simply a high density point cloud that is approximately uniformly distributed random points within the polygon plane, with a bit of noise.
Output would be the vertices of the polygon in 3d points.
My question is, is there a better way to approach this problem? The problem with the above solution is that the points can be noisy. Also, rasterization of the points into 2d and then preforming a edge find is pretty costly.
Any pointers would be great. Thanks in advance
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
首先，您要为网格选择一种表示形式。在 2D 中，我使用以下表示实现了 Python 凹壳算法： half -边数据结构。
然后，2D 中的算法（您应该适应 3D）可以接近 阿尔法形状算法，作者：Edelbrunner。
First of all you are to choose a representation for your mesh. In 2D, I implemented a Python concave hull algo using this representation: half-edge data structure.
Then, algorithm in 2D (you should adapt to 3D) can be close to alpha shape algorithm, by Edelbrunner.
如果你的凹角不是太尖锐，我可能会尝试在点集上进行 3d Delaunay 三角剖分。边界上点的 Voronoi 区域往往是无限的或比内部点的沃罗诺伊区域长得多。类似地，与多面体的单个面相关联的边界上的单元将倾向于在几乎垂直于它们所关联的面的方向上对齐，因为它们都将是又长又薄，并且它们的长轴将是几乎平行并指向多边形之外。在某种程度上准伪代码
编辑现在我看到你只想要一个多边形。上述方法有效，但最好分两步进行。首先找到多边形所在的平面，对一小部分点样本进行最小二乘拟合可能就足够了。将点投影到平面上（这几乎就是您一直在做的事情），然后计算 2d Delaunay 三角剖分以找到边缘点并继续如上所述。
If your concave corners are not too sharp, I might try doing a 3d Delaunay triangulation on the point set. The Voronoi regions of the points on the boundary will tend to be either infinite or much longer than the ones on the interior. Similary, cells on the boundary that are associated with a single face of the polyhedron will tend to be aligned in a direction nearly normal to the face that they are associated with, in that they will all be long and thin and their long axes will be nearly parallel and pointing out of the polygon. In kinda sorta quasi-pseudocode
Edit Now I see that you just want a polygon. The above approach works, but it is probably best to do it in two steps. First find the plane in which the polygon lies, doing a least squares fit of a small sample of the points is probably good enough. Project the points onto a plane (This is pretty much what you have been doing) then compute the 2d Delaunay triangulation to find the edge points and continue as above.
听起来您想计算 3 空间中投影到平面上的点集合的凹壳。 此处详细讨论了 2D 情况< /a>.
It sounds like you want to compute the concave hull of a collection of points in 3-space projected onto a plane. The 2D case is discussed in some detail here.