1 2 Previous Next 19 Replies Latest reply: Oct 9, 2012 4:51 AM by _jum RSS

    shortest distance

    don123
      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
          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
            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
              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
                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
                  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
                    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
                      Hi Luc, thanks

                      your approach is interesting, can you explain further what procedures and functions to use ?
                      • 8. Re: shortest distance
                        don123
                        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
                          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
                            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
                              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
                                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
                                  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
                                    What is the the number of points in your dataset?

                                    tx

                                    Luc
                                    1 2 Previous Next