Least distance from a point to an area

问题:

I am trying to find a point (P2) in a closed area that has the minimum distance to a point (P1). The area is built of homogenous pixels, it is not shaped perfectly and it is not necessarily convex. This is basically a problem of reaching an area from the shortest path.

The whole space is a stored in the form of a bitmap in the memory. What is the best method to find P2? Should I go with random search (optimization) methods? Optimization methods do not give the exact minimum but they are faster than brute forcing every pixel of the area. I need to perform thousands of these decisions in a few seconds.

The MinX,MinY,MaxX,MaxY of the area is available.

Thanks.

回答1:

Here is my code, it's a discrete version using discrete coordinates:

Hint: the method I used to find the circumference of the Area is simple, it's like how do you know the beach from the land ? answer: the beach is covered by Sea from one side, so in my graph matrix, NULL reference is Sea, Points are Land!

Class Point:

class Point
{
    public int x;
    public int y;

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

Class Area:

class Area
{
    public ArrayList<Point> points;

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

Discrete Distance Utility Class:

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;
    }    
}

回答2:

We have to assume you know or can easily find at least one pixel address (x0,y0) inside the area. The fastest solution will certainly be to search from this pixel in a straight line, say in the plus x direction Alternately, since you have a bounding box, pick the compass point toward the nearest boundary and go in that direction.

When you find the edge of the region, search depth first along the boundary. For general polygons with self-intersections and/or holes, this will have to be a complete and carefully implemented DFS maintaining a set of already-visited vertices. Only if the polygon is simple will it suffice to remember only the last-visited pixel to avoid doubling back over what's already searched.

During the DFS, compute the distance squared to p1 for each boundary pixel and track the minimum.

Note, if you are really pressed for performance this distance squared can be updated incrementally to replace multiplications with additions. I.e. if you know d2=(x2-x1)^2+(y2-y1)^2 and then increment x2 by 1 to take the next step around the boundary, the new squared distance is

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

So you can update d2 with d2 += 2(x2 - x1) + 1. The multiplication by 2 is of course just a left shift, so this is very cheap. There are similar very cheap updates for steps in each direction.

回答3:

One approach might be to set for an approximate solution by first canculating a triangulation of the area; afterwards, only the corners of the triangles have to be checked. This approach could be beneficial especially if in the many evaluations you plan for, the outside point changes but the shape itself does not change.

回答4:

You could find the center of the rect of the area, and use a triangle between the two points to find the angle, and then use a function f(x) = mx + b to do the pixel walk until you find a pixel of the area to calculate the distance, and then rotate the angle until you find the shortest path.