计算到画布中“像素斑点”之间的最小距离

Question

我想计算两组像素之间的距离–出于说明目的，一组蓝色像素和一组红色像素。我想计算x方向，y方向和任意方向上的最接近距离（请参见图中的三个箭头）。通常，一种颜色的像素可能是未连接的色块（如示例中的红色），但是大多数时候它们将被连接，尽管它们可能有孔（如示例中的蓝色）。

是否有任何库或算法已经以明智的方式解决了这个问题？提出解决方案并不是特别困难– x和y距离是O（n）问题，但是对于任意距离，幼稚的蛮力算法是O（n²）。我预感有更好的方法。

Answer 1

如果您的集合没有特殊形状（例如线段），您将找不到比O（n²）更好的解决方案。

但是您可以添加预处理步骤以减少n。删除集合的所有内部点。这（取决于集合）可能会大大减少n。在您的示例中，我估计这会将n的大小减小一半。

如果您的示例是集合的典型示例，则可以将这些集合转换为一组线段，然后计算它们之间的距离。