This discussion is archived
1 2 Previous Next 19 Replies Latest reply: Oct 9, 2012 2:51 AM by _jum RSS

shortest distance

don123 Newbie
Currently Being Moderated
hi, i have point geometry table, want to select the intermediate points that gives shortest between two predefined points (point 1 and point 2) by using sdo_geom.sdo_distance.

ID X Y
point 1: 6143 -87.910994 41.982889
point 2: 6048 -87.907813 41.982816

intermediate points:

point 3: 5991 -87.909845 41.9828835
point 4: 5994 -87.908649 41.98287
point 5: 5993 -87.908798 41.9826835
point 6: 6033 -87.908493 41.9825935

any suggestions ??
thanks
  • 1. Re: shortest distance
    _jum Journeyer
    Currently Being Moderated
    IMO the SRID are not valid, so I changed them a little for an example:
    WITH apoints AS
     (SELECT 1 id, sdo_geometry(2001, 2143, sdo_point_type(-87.910994, 41.982889 , 0),  NULL, NULL) geom FROM dual UNION ALL
      SELECT 2   , sdo_geometry(2001, 2048, sdo_point_type(-87.907813, 41.982816 , 0),  NULL, NULL)      FROM dual),
         ipoints AS
     (SELECT 3 id, sdo_geometry(2001, 2991, sdo_point_type(-87.909845, 41.9828835, 0),  NULL, NULL) geom FROM dual UNION ALL
      SELECT 4   , sdo_geometry(2001, 2994, sdo_point_type(-87.908649, 41.98287  , 0),  NULL, NULL)      FROM dual UNION ALL
      SELECT 5   , sdo_geometry(2001, 2993, sdo_point_type(-87.908798, 41.9826835, 0),  NULL, NULL)      FROM dual UNION ALL
      SELECT 6   , sdo_geometry(2001, 2033, sdo_point_type(-87.908493, 41.9825935, 0),  NULL, NULL)      FROM dual)
    SELECT ap.id, ip.id,
           sdo_geom.sdo_distance(SDO_CS.TRANSFORM(ap.geom,2143),SDO_CS.TRANSFORM(ip.geom,2143),1) dist
      FROM apoints ap, ipoints ip
     ORDER BY dist desc; 
    
    
            ID       ID_1       DIST
    ---------- ---------- --------------
             2          3 21273804,0
             2          5 21273804,0
             2          4 21273745,6
             2          6 16101842,9
             1          3 7962325,10
             1          5 7962325,10
             1          4 7962236,87
             1          6 363017,330
    
    8 rows selected.
    For the calculation of the distance I transformed the coordinates in a common SRID.
    The WITH clause is to build up the example "on the fly" without your tables.

    Edited by: _jum on 25.09.2012 11:53                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                           
  • 2. Re: shortest distance
    don123 Newbie
    Currently Being Moderated
    hi, thanks for your reply.

    (1) what i have mentioned is point id but not SRID. I am using SRID=8307.

    (2) what i need is i need to travel from point 1 to point 2 by using any available intermediate points (point 3, point 4, point 5, point 6) so that distance should be minimum.

    (3) In the present example, i can travel from point 1 to point 2 by using two intermediate points (point 3 and point 4), so it should select four points (1,2,3,4).

    It is something like network analysis problem without line geometry.

    thanks
  • 3. Re: shortest distance
    _jum Journeyer
    Currently Being Moderated
    You mean the Travelling salesman problem.
    There are some articles in the web for (spatia)l solutions of this problem.
    As a first step you could calculate all possible ways ("brute Force") and find the shortest one.
    But this method is only for small numbers of points.
  • 4. Re: shortest distance
    _jum Journeyer
    Currently Being Moderated
    Here a little PL/SQL program as start:
    SET SERVEROUTPUT ON SIZE 900000;
    
    DECLARE
      TYPE points IS TABLE OF sdo_geometry;
    
      ipoints points :=  points();
      apoint sdo_geometry := sdo_geometry(2001, 8307, sdo_point_type(-87.910994, 41.982889 , 0), NULL , NULL);
      epoint sdo_geometry := sdo_geometry(2001, 8307, sdo_point_type(-87.907813, 41.982816 , 0), NULL, NULL);   
      
      dist   NUMBER := 0;
      sumd   NUMBER := 9999999;
    
    BEGIN
    
      --initialize
      ipoints.extend(4);
      ipoints(1) := sdo_geometry(2001, 8307,sdo_point_type(-87.909845, 41.9828835, 0), NULL, NULL);
      ipoints(2) := sdo_geometry(2001, 8307,sdo_point_type(-87.908649, 41.98287  , 0), NULL, NULL);
      ipoints(3) := sdo_geometry(2001, 8307,sdo_point_type(-87.908798, 41.9826835, 0), NULL, NULL);
      ipoints(4) := sdo_geometry(2001, 8307,sdo_point_type(-87.908493, 41.9825935, 0), NULL, NULL);
    
      --brute force
      FOR i IN 1..4 LOOP
        FOR j IN 1..4 LOOP
          FOR k IN 1..4 LOOP
            FOR l IN 1..4 LOOP
              dist := sdo_geom.sdo_distance(apoint    ,ipoints(i),1) +  
                      sdo_geom.sdo_distance(ipoints(i),ipoints(j),1) +
                      sdo_geom.sdo_distance(ipoints(k),ipoints(l),1) +
                      sdo_geom.sdo_distance(ipoints(l),    epoint,1);
              sumd := least(dist,sumd);
            END LOOP;
          END LOOP;
        END LOOP;
      END LOOP;
    
      --length of shortest path
      dbms_output.put_line (sumd);
    END;  
    
    156,7576157626734
    PL/SQL procedure successfully completed.
  • 5. Re: shortest distance
    Luc Van Linden Pro
    Currently Being Moderated
    Have you thought of the following approach?

    1. Triangulate your points
    2. decompose the triangles into their 3 lines
    3. remove redundant lines
    4. build network topology (with your points and the remaining lines from the triangles)
    5. apply the shortest path on to this network.

    2,3,4 might be possible by structuring them as a polygon topology and use the edges as your network to travel

    Contact me directly should you require further assistance.

    Regards

    Luc
  • 6. Re: shortest distance
    don123 Newbie
    Currently Being Moderated
    hi jum, thanks for the reply.

    In fact, the minimum aerial distance should be 263.7 between the two points (apoint and epoint) as computed below. When it travels between intermediate points, it should be more than 263.7.


    apoint coordinates
    ---------------------------

    SQL> select a.eid, a.geometry.sdo_point.x, a.geometry.sdo_point.y from np a where a.eid=6143;

    EID GEOMETRY.SDO_POINT.X GEOMETRY.SDO_POINT.Y
    ---------- -------------------- --------------------
    6143 -87.910994 41.982889

    epoint coordinates
    -----------------------------

    SQL> select a.eid, a.geometry.sdo_point.x, a.geometry.sdo_point.y from np a where a.eid=6048;

    EID GEOMETRY.SDO_POINT.X GEOMETRY.SDO_POINT.Y
    ---------- -------------------- --------------------
    6048 -87.907813 41.982816

    distance between apoint and epoint
    ------------------------------------------------------

    SQL> select sdo_geom.sdo_distance(a.geometry, b.geometry, 0.5) from np a, np b where a.eid=6143 and b.eid=6048;

    SDO_GEOM.SDO_DISTANCE(A.GEOMETRY,B.GEOMETRY,0.5)
    ------------------------------------------------
    263.702277
  • 7. Re: shortest distance
    don123 Newbie
    Currently Being Moderated
    Hi Luc, thanks

    your approach is interesting, can you explain further what procedures and functions to use ?
  • 8. Re: shortest distance
    don123 Newbie
    Currently Being Moderated
    hi jum,

    i have modified your loop (for j and k) by adding one more as below, the distance is 263.7.

    sdo_geom.sdo_distance(ipoints(j),ipoints(k),1)

    can you tell me how to get the intermediate points used to compute least distance.
  • 9. Re: shortest distance
    _jum Journeyer
    Currently Being Moderated
    You are absolutely right I missed a segment.
    Here a very simple solution to concat the 4 (same) points:
    SET SERVEROUTPUT ON SIZE 900000;
     
    DECLARE
      TYPE points IS TABLE OF sdo_geometry;
     
      ipoints points :=  points();
      apoint sdo_geometry := sdo_geometry(2001, 8307, sdo_point_type(-87.910994, 41.982889 , 0), NULL , NULL);
      epoint sdo_geometry := sdo_geometry(2001, 8307, sdo_point_type(-87.907813, 41.982816 , 0), NULL, NULL);   
      
      dist   NUMBER := 0;
      sumd   NUMBER := 9999999;
      
      route  VARCHAR2(200) := '';
     
    BEGIN
     
      --initialize
      ipoints.extend(4);
      ipoints(1) := sdo_geometry(2001, 8307,sdo_point_type(-87.909845, 41.9828835, 0), NULL, NULL);
      ipoints(2) := sdo_geometry(2001, 8307,sdo_point_type(-87.908649, 41.98287  , 0), NULL, NULL);
      ipoints(3) := sdo_geometry(2001, 8307,sdo_point_type(-87.908798, 41.9826835, 0), NULL, NULL);
      ipoints(4) := sdo_geometry(2001, 8307,sdo_point_type(-87.908493, 41.9825935, 0), NULL, NULL);
     
      --brute force
      FOR i IN 1..4 LOOP
        FOR j IN 1..4 LOOP
          FOR k IN 1..4 LOOP
            FOR l IN 1..4 LOOP
              --dont use same point twice !
              --IF (i=j OR i=k OR i=l or j=k or j=l or k=l) THEN CONTINUE;END IF;
              dist  := sdo_geom.sdo_distance(apoint    ,ipoints(i),1) +  
                       sdo_geom.sdo_distance(ipoints(i),ipoints(j),1) +
                       sdo_geom.sdo_distance(ipoints(j),ipoints(k),1) +
                       sdo_geom.sdo_distance(ipoints(k),ipoints(l),1) +
                       sdo_geom.sdo_distance(ipoints(l),    epoint,1);
              --get the actual route
              IF sumd>dist THEN
                sumd  := dist;
                route := to_char(i)||to_char(j)||to_char(k)||to_char(l);
              END IF;
            END LOOP;
          END LOOP;
        END LOOP;
      END LOOP;
     
      --length of shortest path
      dbms_output.put_line ('route='||route);
      dbms_output.put_line (sumd);
    END;
    
    route=1111
    263,7877339557591
    If you uncomment the IF-clause that looks for identical points, you get the solution for travelling all points:
    route=1324
    303,762351747099
  • 10. Re: shortest distance
    don123 Newbie
    Currently Being Moderated
    hi, sorry for the delay.

    i have displayed all the six points in sql developer-georatper, manually measured and checked
    the shortest distance (263.7) is correct, but the route should include these following points. (start point, intermediate point 1, intermediate point 2 and end point)
    you mentioned route includes (1111) ??

    ORIGIN - apoint sdo_geometry := sdo_geometry(2001, 8307, sdo_point_type(-87.910994, 41.982889 , 0), NULL , NULL);

    INTERMEDIATE POINT - ipoints(1) := sdo_geometry(2001, 8307,sdo_point_type(-87.909845, 41.9828835, 0), NULL, NULL);

    INTERMEDIATE POINT - ipoints(2) := sdo_geometry(2001, 8307,sdo_point_type(-87.908649, 41.98287 , 0), NULL, NULL);

    DESTINATION - epoint sdo_geometry := sdo_geometry(2001, 8307, sdo_point_type(-87.907813, 41.982816 , 0), NULL, NULL);

    thanks
  • 11. Re: shortest distance
    _jum Journeyer
    Currently Being Moderated
    The modifications of the code for exactly TWO points are very simply and show the expected result AP->1->2->EP. just play around with the code...:
    SET SERVEROUTPUT ON SIZE 900000;
     
    DECLARE
      TYPE points IS TABLE OF sdo_geometry;
     
      ipoints points :=  points();
      apoint sdo_geometry := sdo_geometry(2001, 8307, sdo_point_type(-87.910994, 41.982889 , 0), NULL , NULL);
      epoint sdo_geometry := sdo_geometry(2001, 8307, sdo_point_type(-87.907813, 41.982816 , 0), NULL, NULL);   
      
      dist   NUMBER := 0;
      sumd   NUMBER := 9999999;
      
      route  VARCHAR2(200) := '';
     
    BEGIN
     
      --initialize
      ipoints.extend(4);
      ipoints(1) := sdo_geometry(2001, 8307,sdo_point_type(-87.909845, 41.9828835, 0), NULL, NULL);
      ipoints(2) := sdo_geometry(2001, 8307,sdo_point_type(-87.908649, 41.98287  , 0), NULL, NULL);
      ipoints(3) := sdo_geometry(2001, 8307,sdo_point_type(-87.908798, 41.9826835, 0), NULL, NULL);
      ipoints(4) := sdo_geometry(2001, 8307,sdo_point_type(-87.908493, 41.9825935, 0), NULL, NULL);
     
      --brute force
      FOR i IN 1..4 LOOP
        FOR j IN 1..4 LOOP
              --dont use same point twice !
              IF i=j THEN CONTINUE;END IF;
              dist  := sdo_geom.sdo_distance(apoint    ,ipoints(i),1) +  
                       sdo_geom.sdo_distance(ipoints(i),ipoints(j),1) +
                       sdo_geom.sdo_distance(ipoints(j),    epoint,1);
              --get the actual route
              IF sumd>dist THEN
                sumd  := dist;
                route := to_char(i)||to_char(j);
              END IF;
        END LOOP;
      END LOOP;
     
      --length of shortest path
      dbms_output.put_line ('route='||route);
      dbms_output.put_line (sumd);
    END;
    route=12
    263,8913886024336
  • 12. Re: shortest distance
    don123 Newbie
    Currently Being Moderated
    hi,

    can you please confirm whether brute force logic has considered all four intermediate points in addition to start point and end point ?
    can i use the same logic by increasing number of intermediate points ?

    thanks
  • 13. Re: shortest distance
    _jum Journeyer
    Currently Being Moderated
    can you please confirm whether brute force logic has considered all four intermediate points in addition to start point and end point ?
    In the first query it is allowed to use a intermediate point more than once. So the solution "goes" from the start point to point 1, from there again to point 1 (stays there), this three times and finaly to the end point. So the solution is "strange" but correct. In the new query I don't use the same point twice.
    can i use the same logic by increasing number of intermediate points ?
    You can extend the number of FOR LOOP according to the number of intermediare points until the time for calculating the solution becomes to high or ORACLE "gives up". This is the main problem with brute force search.
    But now, as you have an example just try it!
  • 14. Re: shortest distance
    Luc Van Linden Pro
    Currently Being Moderated
    What is the the number of points in your dataset?

    tx

    Luc
1 2 Previous Next

Legend

  • Correct Answers - 10 points
  • Helpful Answers - 5 points