我有一组“块”(用红色和绿色线表示),放置在一个“容器”内(用蓝色线表示)。 所有块的交点(绿点和红点)以及容器的所有相关信息(角度、梯度、起始点、结束点等)都已知。 我想提取放置块后结果图形的“最上层”轮廓(由绿线和点表示)。 我尝试使用凸包方法(如下图中紫色线所示),但它并没有给出精确的线条。 我的问题是,有没有人能够指导我一个解决这种问题的方法或算法?
将所有点填充到列表(数组)中。(在T节点中重复点,如您图片中的第二个绿色点) 按Y坐标对此列表进行排序。 像扫描线算法一样从顶部点开始扫描列表。 在每个阶段,您将获得具有相同Y坐标的一组点(一对或更多)。 从左侧和右侧同时删除被区间覆盖的点(请参见下文)。 通过这些点的X坐标制作区间(通过X坐标)。 将这些区间添加到区间(段)树中。 连接相邻的区间。 重复以上步骤,直到单个区间覆盖整个顶部部分。