从一个点到一个区域的最小距离

这是我的代码,它是一个使用离散坐标的离散版本:

提示:我用来计算面积周长的方法很简单,就像你如何从陆地上知道海滩一样?答案:海滩从一侧被海覆盖,所以在我的图表矩阵中,NULL参考是海,点是陆地!

分类点:

class Point
{
    public int x;
    public int y;

    public Point (int X, int Y)
    {
        this.x = X;
        this.y = Y;
    }
}

班级面积:

class Area
{
    public ArrayList<Point> points;

    public Area ()
    {
        p = new ArrayList<Point>();
    }
}

离散距离实用程序类别:

class DiscreteDistance
{

    public static int distance (Point a, Point b)
    {
        return Math.sqrt(Math.pow(b.x - a.x,2), Math.pow(b.y - a.y,2))
    }

    public static int distance (Point a, Area area)
    {
        ArrayList<Point> cir = circumference(area);
        int d = null;

        for (Point b : cir)
        {
            if (d == null || distance(a,b) < d)
            {
                d = distance(a,b);
            }
        }

        return d;
    }

    ArrayList<Point> circumference (Area area)
    {
        int minX = 0;
        int minY = 0;
        int maxX = 0;
        int maxY = 0;

        for (Point p : area.points)
        {
            if (p.x < minX) minX = p.x;
            if (p.x > maxX) maxX = p.x;
            if (p.y < minY) minY = p.y;
            if (p.y > maxY) maxY = p.y;
        }

        int w = maxX - minX +1;
        int h = maxY - minY +1;

        Point[][] graph = new Point[w][h];

        for (Point p : area.points)
        {
            graph[p.x - minX][p.y - minY] = p;
        }

        ArrayList<Point> cir = new ArrayList<Point>();

        for (int i=0; i<w; i++)
        {
            for (int j=0; j<h; j++)
            {
                if ((i > 0 && graph[i-1][j] == null)
                  || (i < (w-1) && graph[i+1][j] == null)
                  || (j > 0 && graph[i][j-1] == null)
                  || (i < (h-1) && graph[i][j+1] == null))
                {
                    cir.add(graph[i][j]);
                }
            }
        }

        return cir;
    }    
}

我们必须假设您知道或可以很容易地在该区域内找到至少一个像素地址(x0,y0)。最快的解决方案肯定是从这个像素开始直线搜索,比如在正x方向上搜索。或者,由于你有一个边界框,所以朝着最近的边界选择指南针点,然后朝那个方向搜索。

当您找到区域的边缘时,首先沿着边界搜索深度。 对于具有自相交和/或孔的一般多边形,这必须是一个完整且仔细实施的DFS,以维护一组已经访问过的顶点。 只有当多边形很简单时,只记住最后一个访问的像素就足够了,以避免重复已经搜索过的像素。

在DFS期间,计算每个边界像素的距离与p1的平方,并跟踪最小值。

注意,如果你真的很想获得性能,这个距离平方可以增量更新,用加法代替乘法。也就是说,如果你知道 d2=(x2-x1)^2+(y2-y1)^2 然后递增 x2 乘以1,绕边界迈出下一步,新的平方距离为

((x2+1) - x1)^2 + (y2-y1)^2 = d2 + 2(x2 - x1) + 1

所以你可以更新 d2 具有 d2 += 2(x2 - x1) + 1 。乘以2当然只是左移,所以这是非常便宜的。每个方向的步骤都有类似的非常便宜的更新。

一种方法可能是通过首先抵消该区域的三角测量来设置近似解;之后,只需要检查三角形的角。这种方法可能是有益的,尤其是在您计划的许多评估中,外部点发生了变化,但形状本身没有变化。

你可以找到区域矩形的中心,在两点之间使用一个三角形来找到角度,然后使用函数f(x)=mx+b进行像素行走,直到你找到区域的一个像素来计算距离,然后旋转角度,直到你发现最短路径。