基于到达特定点所需的最小线段数量评估像素的算法，同时仅穿过有效区域？

Question

给定一个二维像素数组，其中任何像素可以是 0 或 1，什么算法将输出一个新的二维像素数组，其中每个值为 1 的像素将根据所需的最小线段数量获得一个新值到达特定的“光源”像素，同时仅穿过输入值为 1 的像素？输入值 0 不会改变。

输入数组示例，洋红色十字代表“光源”像素:

https://cdn3.imggmi.com/uploads/2019/1/8/2a5f6dd0ebdc9c72115f9ce93af3337a-full.png

具有输出值 1 和 2 的输出数组(经过 Photoshop 处理，不是像素完美的图像):

https://cdn3.imggmi.com/uploads/2019/1/8/0025709aaa826c26ee0a8e17476419cb-full.png

• 红色区域 = 距源 1 条线段
• 黄色区域 = 距离源 2 条线段
• 白色区域 = 距离源 3 个或更多线段

(算法不会在 3 处停止，它会一直持续到每个像素都被评估为止。)

编辑:我不确定 StackOverflow 是否是发布此内容的正确 Stack Exchange 站点，如果不是，请告诉我!

Answer 1

使您的原点成为极坐标系的原点。将 block 角转换为极坐标。

现在，将您的点光源视为探照灯，从 0 扫描到 2*PI。光束一直持续到它碰到框架边缘或黑框为止。这定义了一个用洋红色填充的多边形(1 条线段，直接照明)。

这是简单的部分。现在，您可以对位于多边形洋红色-白色 (1-0) 边界上的每个像素重复此操作。这定义了一组有限的次要多边形；用黄色填充(代码 2)。

用黄白色 (2-0) 边界重复此过程以识别 3 像素；迭代直到用完像素。

在其他范例中，我已将区间代数应用于 block 段(例如，一个 block 部分遮挡另一个 block )，但我认为极地多边形攻击将使您在更少的编码时间内找到解决方案。