逆Bresenham算法：如何将像素数组转换为对应线段坐标？

核心结论 #

存在这类算法，本质是通过像素点集的线段拟合+Bresenham覆盖验证，生成一组线段，其Bresenham绘制结果与原像素点集完全一致，可用于优化手绘像素艺术的存储效率。

算法核心思路与步骤 #

1. 预处理点集 #

• 将原像素数组转换为哈希集合（例如用(x, y)元组作为键），实现O(1)时间复杂度的像素存在性校验。
• 若有用户绘制的时序数据，优先按绘制顺序排序像素；无时序则按x→y坐标排序，确保拟合逻辑贴合实际绘制路径。

2. 贪心式线段扩展（高效实现方案） #

这是最常用的工程化实现方式，步骤如下：

• 从剩余未覆盖的像素中选取起点S。
• 尝试向所有可能的方向（优先8邻域方向，或按斜率区间划分）逐步扩展终点E，每次扩展后计算S到E的Bresenham线段覆盖的所有像素。
• 验证这些像素是否全部属于原像素集合，且不存在原集合内的像素被遗漏；直到无法再扩展（继续延长会包含外点或遗漏内点），确定当前最长有效线段。
• 将该线段[S, E]加入结果数组，并从原集合中移除该线段覆盖的所有像素。
• 重复上述流程，直到所有像素都被覆盖。

3. 针对性优化 #

• 规则线段快速识别：对于连续的水平/垂直像素（如示例中[18,25]到[18,13]的竖直线），可直接判定为单一线段，跳过逐点验证。
• 线段合并：若两条相邻线段的Bresenham合并结果完全匹配原像素子集，且无额外像素，可合并为更长线段，减少结果数组长度。
• 时序优先拟合：如果有手绘时序数据，按绘制顺序扩展线段，结果更贴合用户的手绘意图。

示例验证 #

针对你提供的像素片段：
原像素：[ [27,31],[26,31],[25,30],[24,30],[23,29],[22,29],[21,28],[20,27],[19,26],[18,25],[18,24],...,[18,13] ]

• 从[27,31]扩展至[22,29]：Bresenham绘制的像素恰好是前6个点，全部匹配原集合，生成第一条线段。
• 从[22,29]（或剩余的[21,28]）扩展至[18,25]：对应Bresenham像素正好覆盖[21,28]到[18,25]的所有点，生成第二条线段。
• 从[18,25]扩展至[18,13]：竖直线的Bresenham结果完全覆盖后续连续竖排像素，生成第三条线段。

关键注意事项 #

• 严格校验完整性：必须确保每条线段的Bresenham像素与原集合的对应子集完全一致，不能多画或少画像素。
• 多解性与效率权衡：同一个像素点集可能对应多组线段组合，贪心算法得到的是局部最优（线段数量较少）；若追求全局最优，可采用动态规划或回溯，但会牺牲运行效率。
• 噪点处理：若原像素存在孤立噪点，算法会将其作为单像素线段处理，建议提前做去噪预处理。

内容的提问来源于stack exchange，提问作者Kirkman14