查找一组点的特定轮廓

Question

我有一组“块”（用红线和绿线表示）放置在“容器”（用蓝线表示）内。

所有块（绿色和红色的点）和容器的所有相关信息的交叉点的（角度，梯度，开始，结束点等）是已知的。

我想在块放置后（由绿线和点表示）提取结果图的“最顶部”轮廓。

我试图使用的方法，例如凸包，但它不给出确切的线（由紫线下图中示出。）

我的问题是任何人都可以指向我一个解决方案或某种算法，我可以用来解决这类问题？

Answer 1

用所有点填充列表（数组）。 （T形节点中的重复点，如图片中的第2个绿色点）
按Y坐标对此列表排序
扫描列表（从顶点开始）像扫描线算法。
在每一个阶段你都会得到一组具有相同Y坐标（一对或多对）的点。
从左侧和右侧移除包括间隔（见下文）的点。
根据这些点对的间隔（通过X坐标）。
在区间（分段）树中添加这些区间。
加入邻居间隔。
重复，直到单个间隔覆盖所有顶部。

Answer 2

凸包应该做的工作。 对于许多凸包算法，您可以检查：Fast and improved 2D Convex Hull algorithm and its implementation in O(n log h)。

只要它触及红点，你会得到前后。