Разделите путь на N участков, используя Java или PostgreSQL/PostGIS

Представьте себе систему GPS-слежения, которая отслеживает положение нескольких объектов. Точки хранятся в базе данных (PostgreSQL + PostGIS).

Каждый путь состоит из разного количества точек. Вот почему, чтобы сравнить пару путей (сравнить весь путь), я хочу разделить каждый путь на набор из 100 точек. Это проблема. Знаете ли вы какую-нибудь функцию PostGIS, которая уже реализует этот алгоритм? Я не смог найти его.

Если нет, я хотел бы решить это с помощью Java. В этом случае я хотел бы знать эффективный и простой в реализации алгоритм для разделения пути на N точек.

Самым простым примером может быть разделение этого четырехточечного пути на восемь точек:

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

И в результате должно получиться:

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)

Изменить. Под «сравнить пару путей» я подразумеваю вычисление расстояния между двумя полными путями. Я планирую разделить каждый путь на 100 точек и суммировать евклидово расстояние между каждой из этих точек как расстояние между двумя путями.


java postgis geometry
person Guido    schedule 03.05.2010    source источник
comment
Можете ли вы уточнить, чего вы пытаетесь достичь, сравнивая пути?   -  person matt b    schedule 03.05.2010
comment
В вашем вопросе все еще нет ясности... У вас возникли проблемы с расчетом расстояния? Разделение пути? Зачем вам делить путь, если вы только пытаетесь найти расстояние от точки А до точки Б? ...Что ты делаешь с этим?   -  person Jonathan    schedule 04.05.2010
comment
Еще раз отредактировал. Проблема в разделении пути. Мне нужно найти расстояние между двумя путями, то есть расстояние от каждой точки первого пути до соответствующей точки второго пути. Вот почему мне нужно, чтобы они имели одинаковое количество очков.   -  person Guido    schedule 04.05.2010

Ответы (2)


arrow_upward
5
arrow_downward

Я не уверен, что точно понимаю, чего вы хотите. Тем не менее, этот запрос PostGIS возьмет одну строку и выдаст сто точек, расположенных на равном расстоянии друг от друга вдоль этой линии:

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

Очевидно, вы будете использовать реальную геометрию, а не ST_GeomFromText(..), и не будете включать вызов ST_AsText(...). Результат в виде текста:

                  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)
person fmark    schedule 04.05.2010

arrow_upward
0
arrow_downward

Меня смущает цель разделения пути на 100 частей. Очевидным решением для получения расстояния до конца пути будет формула расстояния:

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

Если вам нужно найти расстояние по определенному маршруту между двумя точками (скажем, следовать по улицам и уклоняться от зданий), то вы можете сделать это с таким набором «пунктов назначения» и совершенно другой проблемой, но ваш пример показывает точки как прямая линия между точками в любом случае. (Я предполагаю, что вы имели в виду, что ввод «позиция 2» должен быть x = 9, y = 3).

РЕДАКТИРОВАТЬ: Если вы имели в виду, что вам дан набор точек и вам нужно найти расстояние по пути, вы должны использовать ту же формулу следующим образом:

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

... расстояние будет суммой расстояний между каждой точкой.

Если проблема заключается в разделении пути на «N» частей, вы можете использовать следующее:

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

Который вернет ArrayList заданного количества местоположений, равномерно распределенных по пути от точки A до точки B.

person Jonathan    schedule 03.05.2010
comment
Спасибо. Извините, но путь состоит из N точек, а не только из точек A и B. Я отредактировал вопрос, чтобы попытаться отразить его. Извините за неправильное понимание. - person Guido; 07.05.2010