寻找一组点的具体轮廓

Question

我有一组 "blocks"（用红线和绿线表示）放在 "container"（用蓝线表示）内。

方块的所有交点（绿点和红点）和容器的所有相关信息（角度、梯度、起点、终点等）都是已知的。

我想在放置块（用绿线和点表示）后提取结果图形的 "top-most" 轮廓。

我试过使用凸包等方法（下图中紫色线所示），但没有给出准确的线

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

Answer 1

用所有点填充列表（数组）。 （在 T 节点中重复点，例如图片中的第二个绿点）
按 Y 坐标
排序此列表 像扫描线算法一样扫描列表（从顶部开始）。
在每个阶段，您都会得到一组具有相同 Y 坐标（一对或更多）的点。
从左侧和右侧删除被间隔（见下文）覆盖的点。
从这些点对中创建间隔（按 X 坐标）。
在区间（段）树中添加这些区间。
加入邻居区间。
重复直到单个区间覆盖所有顶部。

Answer 2

凸包应该可以完成这项工作。 您可以查看：Fast and improved 2D Convex Hull algorithm and its implementation in O(n log h) 了解许多凸包算法。

一碰到红点，就得到前后。