使用 Java 或 PostgreSQL/PostGIS 将路径分为 N 段

发布于 2024-08-31 07:42:05 字数 742 浏览 1 评论 0原文

想象一下一个跟踪多个物体位置的 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 个点，并将每个点之间的欧氏距离相加，作为两条路径之间的距离。

原文

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.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

尽揽少女心 2024-09-07 07:42:05

我不确定我是否完全理解你想要什么。尽管如此，这个 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)

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)

回复收藏 0 原文

潜移默化 2024-09-07 07:42:05

我对将路径分为 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;
}

它将返回沿从 pointA 到 pointB 的路径等距分布的给定数量位置的 ArrayList。

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.

回复收藏 0 原文

~没有更多了~