Divide a path into N sections using Java or PostgreSQL/PostGIS

Question

Imagine a GPS tracking system that is following the position of several objects. The points are stored in a database (PostgreSQL + PostGIS).

Each path is composed by a different number of points. That is the reason why, in order to compare a pair of paths (compare the whole path), I want to divide every path in a set of 100 points. This is the problem. Do you know any PostGIS function that already implement this algorithm? I've not been able to find it.

If not, I'd like to solve it using Java. In this case I'd like to know an efficient and easy to implement algorithm to divide a path into N points.

The most simple example could be to divide this four-points-path into eight points:

position 1 : x=1, y=2
position 2 : x=2, y=4
position 3 : x=3, y=6
position 4 : x=4, y=8

And the result should be:

position 1 : x=1, y=2 (starting point)
position 2 : x=1.5, y=3
position 2 : x=2, y=4
position 2 : x=2.5, y=5
position 2 : x=3, y=6
position 2 : x=3.5, y=7
position 2 : x=4, y=8 (ending point)

Edit: By 'compare a pair of paths' I mean to calculate the distance between two complete paths. I plan to divide each path in 100 points, and sum the euclidean distance between each one of these points as the distance between the two paths.

Answer 1

I am confused about the purpose of dividing the path into 100 parts. The obvious solution to get the distance to the end of the path would be the distance formula:

distance = Math.sqrt(Math.pow(2, (x1-x2)) + Math.pow(2, (y1-y2));

If you are wanted to find the distance along a certain route between the two points (say to follow streets and dodge buildings), then you could do so with such a collection of 'destinations', and an entirely different problem, but your example shows the points as a straight line between the points anyways. (I assume you meant the input 'position 2' to be x=9, y=3).

EDIT: If you meant that you are given a collection of points and need to find the distance along the path, you would use the same formula as follows:

double distance = 0;
for(int i=1; i<numberOfLocations; i++)
{
    Location oldLoc = collection.get(i-1);
    Location nextLoc = collection.get(i);
    int x = nextLoc.getX() - oldLoc.getX();
    int y = nextLoc.getY() - oldLoc.getY();
    distance = distance + Math.sqrt(Math.pow(2, x) + Math.pow(2, y);
}

...distance would be the sum of the distances between each point.

If the problem is in dividing the path into 'N' parts, you can use the following:

//numberOfPoints must be greater than 1.
public ArrayList<Location> divideIntoPoints(Location pointA, Location pointB, int numberOfPoints)
{
    ArrayList<Location> locationList = new ArrayList<Location>();

    xStart = pointA.getX();
    xInterval = (pointB.getX() - pointA.getX()) / (numberOfPoints - 1);

    yStart = pointA.getY();
    yInterval = (pointB.getY() - pointA.getY()) / (numberOfPoints - 1);

    for(int i=0; i<numberOfPoints; i++)
    {
        locationList.add( new Location( (xStart + (i*xInterval)), (yStart + (i*yInterval))) );
    }

    return locationList;
}

Which will return an ArrayList of a given number of Locations equally spaced along the path from pointA to pointB.

Answer 2

I'm not certain I understand exactly what you want. Nonetheless, this PostGIS query will take a single line and spit out one hundred points equally spaced along that line:

SELECT ST_AsText(
  ST_Line_Interpolate_Point(
    ST_GeomFromText('LINESTRING(0 0, 1 2, 10 2)'),
    generate_series(0, 100):: double precision / 100
  )
);

Obviously you would use real geometry rather than ST_GeomFromText(..), and would not include the ST_AsText(...) call. The result, as text, is:

                  st_astext                  
---------------------------------------------
 POINT(0 0)
 POINT(0.0502492235949962 0.100498447189992)
 POINT(0.100498447189992 0.200996894379985)
 POINT(0.150747670784989 0.301495341569977)
 POINT(0.200996894379985 0.40199378875997)
 POINT(0.251246117974981 0.502492235949962)
 POINT(0.301495341569977 0.602990683139955)
 POINT(0.351744565164974 0.703489130329947)
 POINT(0.40199378875997 0.803987577519939)
 POINT(0.452243012354966 0.904486024709932)
 POINT(0.502492235949962 1.00498447189992)
 POINT(0.552741459544958 1.10548291908992)
 POINT(0.602990683139955 1.20598136627991)
 POINT(0.653239906734951 1.3064798134699)
 POINT(0.703489130329947 1.40697826065989)
 POINT(0.753738353924943 1.50747670784989)
 POINT(0.803987577519939 1.60797515503988)
 POINT(0.854236801114936 1.70847360222987)
 POINT(0.904486024709932 1.80897204941986)
 POINT(0.954735248304928 1.90947049660986)
 POINT(1.01114561800017 2)
 POINT(1.12350629777517 2)
 POINT(1.23586697755016 2)
 POINT(1.34822765732516 2)
 POINT(1.46058833710016 2)
 POINT(1.57294901687516 2)
 POINT(1.68530969665016 2)
 POINT(1.79767037642515 2)
 POINT(1.91003105620015 2)
 POINT(2.02239173597515 2)
 POINT(2.13475241575015 2)
 POINT(2.24711309552515 2)
 POINT(2.35947377530014 2)
 POINT(2.47183445507514 2)
 POINT(2.58419513485014 2)
 POINT(2.69655581462514 2)
 POINT(2.80891649440013 2)
 POINT(2.92127717417513 2)
 POINT(3.03363785395013 2)
 POINT(3.14599853372513 2)
 POINT(3.25835921350013 2)
 POINT(3.37071989327512 2)
 POINT(3.48308057305012 2)
 POINT(3.59544125282512 2)
 POINT(3.70780193260012 2)
 POINT(3.82016261237512 2)
 POINT(3.93252329215011 2)
 POINT(4.04488397192511 2)
 POINT(4.15724465170011 2)
 POINT(4.26960533147511 2)
 POINT(4.38196601125011 2)
 POINT(4.4943266910251 2)
 POINT(4.6066873708001 2)
 POINT(4.7190480505751 2)
 POINT(4.8314087303501 2)
 POINT(4.9437694101251 2)
 POINT(5.05613008990009 2)
 POINT(5.16849076967509 2)
 POINT(5.28085144945009 2)
 POINT(5.39321212922509 2)
 POINT(5.50557280900008 2)
 POINT(5.61793348877508 2)
 POINT(5.73029416855008 2)
 POINT(5.84265484832508 2)
 POINT(5.95501552810008 2)
 POINT(6.06737620787507 2)
 POINT(6.17973688765007 2)
 POINT(6.29209756742507 2)
 POINT(6.40445824720007 2)
 POINT(6.51681892697506 2)
 POINT(6.62917960675006 2)
 POINT(6.74154028652506 2)
 POINT(6.85390096630006 2)
 POINT(6.96626164607506 2)
 POINT(7.07862232585005 2)
 POINT(7.19098300562505 2)
POINT(7.30334368540005 2)
 POINT(7.41570436517505 2)
 POINT(7.52806504495005 2)
 POINT(7.64042572472504 2)
 POINT(7.75278640450004 2)
 POINT(7.86514708427504 2)
 POINT(7.97750776405004 2)
 POINT(8.08986844382504 2)
 POINT(8.20222912360003 2)
 POINT(8.31458980337503 2)
 POINT(8.42695048315003 2)
 POINT(8.53931116292503 2)
 POINT(8.65167184270003 2)
 POINT(8.76403252247502 2)
 POINT(8.87639320225002 2)
 POINT(8.98875388202502 2)
 POINT(9.10111456180002 2)
 POINT(9.21347524157501 2)
 POINT(9.32583592135001 2)
 POINT(9.43819660112501 2)
 POINT(9.55055728090001 2)
 POINT(9.66291796067501 2)
 POINT(9.77527864045 2)
 POINT(9.887639320225 2)
 POINT(10 2)