ios - 查找给定形状的外线

Question

我有各种实体形状，需要为其找到外线。

我从 API 获取形状，作为形状中每个像素的 x、y 坐标列表。我想删除“填充点”，所以我只有一个“外线”列表，即这张图片中的红色像素:

如何做到这一点？

Answer 1

如果您打开该图像并将其放大，您可以很容易地看出红色像素与蓝色像素的区别:红色像素至少有一个白色像素，位于正上方、下方、左侧或右侧它的右边，而蓝色像素为零。对角线不算在内。

因此，在给定像素坐标列表的情况下，您可以使用以下算法找到形状的外线(红色像素):

• 将所有像素坐标转换为整数(如果尚未转换)。
• 遍历列表中的所有点并找到最小和最大 x 和 y 坐标。
• 创建一个大小为 [(max y - min y) + 1][(max x - min x) + 1] 的数组并将所有元素设置为 0
• 遍历列表中的所有点并将数组[point y - min y][point x - min x]设置为1
• 为您的外线坐标创建一个空列表
• 遍历数组，对于每个元素 array[y][x]:
  • 如果 array[y][x] 等于 1 AND (array[y-1][x] 等于 0 OR array[y+1][x] 等于 0 OR array[y][x-1] 等于 0或者 array[y][x+1] 等于 0)，那么:
    • 将 (x + min x, y + min y) 添加到外线点列表。

请注意 (max y - min y) 和 (max x - min x) 不要太大，否则在尝试分配数组时可能会出现内存不足错误。此外，为了避免在检查数组时出现索引越界错误，只需在数组的边缘添加任何像素(x 或 y = 0，x 或 y = x 或 y 数组大小 - 1)，其中 array[y][x ] 等于列表中的 1 并避免其他检查。