c# - 寻找一组点的具体轮廓

Question

我有一组“ block ”(用红线和绿线表示)放置在“容器”(用蓝线表示)内。

block 的所有交点(绿点和红点)和容器的所有相关信息(角度、梯度、起点、终点等)都是已知的。

我想在放置 block 后提取结果图形的“最顶部”轮廓(由绿线和点表示)。

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

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

Answer 1

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