Search code examples
arraysalgorithmoptimizationpathgrid

Simplifying a path on a two dimensional grid

Im generating a path from point A to point B on a two dimensional grid, which returns an array of points for my unit to travel through, each element in the array has an X and Y coordinate.

red dot is the path start and the blue one the end, brown points are points contained in the array (the array also includes the start and end points), green line is the path.

enter image description here

how can I simplify this path to something like this? enter image description here

Solution

  • If we consider 3 points on your input path (p0,p1,p2) we want to remove the middle point p1 when the following condition is true:

    (p1.x - p0.x)    (p2.x - p1.x)
------------- == -------------
(p1.y - p0.y)    (p2.y - p1.y)

    Or equivalently, and avoiding the risk of division by zero:

    (p1.x - p0.x) * (p2.y - p1.y) == (p1.y - p0.y) * (p2.x - p1.x)

    Here's some Java code to illustrate:

    static List<Point> simplify(List<Point> poly)
{
    if(poly.size() < 3) return new ArrayList<>(poly);
    
    List<Point> spoly = new ArrayList<>();
    
    spoly.add(poly.get(0));
    for(int i = 0, dx = 0, dy = 0; i < poly.size()-1; i++)
    {
        Point p0 = poly.get(i);
        Point p1 = poly.get(i+1);
        
        int x = p1.x - p0.x;
        int y = p1.y - p0.y;
        
        if(i > 0 && (dx * y != dy * x)) 
            spoly.add(poly.get(i));
        
        dx = x;
        dy = y;
    }
    spoly.add(poly.get(poly.size()-1));
    
    return spoly;
}

    Test:

    List<Point> poly = 
   Arrays.asList(p(0, 0), p(1, 1), p(2, 2), p(3, 3), p(4, 3), p(5, 3), p(6, 3));

System.out.println(simplify(poly));

    Output:

    [(0, 0), (3, 3), (6, 3)]