我有一组“块”（用红色和绿色线表示），放置在一个“容器”内（用蓝色线表示）。
所有块的交点（绿点和红点）以及容器的所有相关信息（角度、梯度、起始点、结束点等）都已知。
我想提取放置块后结果图形的“最上层”轮廓（由绿线和点表示）。
我尝试使用凸包方法（如下图中紫色线所示），但它并没有给出精确的线条。
我的问题是，有没有人能够指导我一个解决这种问题的方法或算法？
寻找一组点的特定轮廓
4
- John Tan
7
我也考虑了凸包，你能解释一下它为什么不起作用吗？ - shole
@shole 凸包将生成紫色轮廓，如第二张图片所示，而我想要的输出是绿色轮廓。我猜这是因为凸包会直接连接边界点。 - John Tan
@MBo 不是的。这就是我想要找出的。换句话说，我知道所有点的位置（红色和绿色），但我不知道它们的颜色。 - John Tan
这对我来说似乎是计算点集的天际线。您可以使用分治或平面扫描（在2D中均为n log n）。 - sud03r
是的，它类似于天际线问题。 - John Tan
显示剩余2条评论
2个回答
1
将所有点填充到列表（数组）中。（在T节点中重复点，如您图片中的第二个绿色点）
按Y坐标对此列表进行排序。
像扫描线算法一样从顶部点开始扫描列表。
在每个阶段，您将获得具有相同Y坐标的一组点（一对或更多）。
从左侧和右侧同时删除被区间覆盖的点（请参见下文）。
通过这些点的X坐标制作区间（通过X坐标）。
将这些区间添加到区间（段）树中。
连接相邻的区间。
重复以上步骤，直到单个区间覆盖整个顶部部分。
- MBo
3
嗨，我不太明白您所说的从左右两侧删除被区间覆盖的点的意思。您能详细说明一下吗？ - John Tan
你没有考虑红点（它们上面有绿色的线段）。 - MBo
所以这个想法是，当我进行扫描线时，如果有点在绿色线段下方，那么我将删除所有这些点？ - John Tan
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接