1 2 Previous Next 19 Replies Latest reply: Oct 9, 2012 4:51 AM by _jum Go to original post RSS
      • 15. Re: shortest distance
        don123
        Jum and Luc

        I may have 10 to 20 points depending on the situation.
        Shall I keep the upper limit of for loop as 10 if number of intermediate points are 10 ??

        thanks
        • 16. Re: shortest distance
          don123
          hi,
          --------------
          I have tested this different start point, end point, intermediate points
          The distance computation is correct.
          It has to select all three intermediate points (1,2,3) as there is no other way from start point to reach end point.
          But it has selected 1,2
          ----------------------


          DECLARE
          TYPE points IS TABLE OF sdo_geometry;
          ipoints points := points();
          apoint sdo_geometry := sdo_geometry(2001, 8307, sdo_point_type(-87.90812, 41.9673885, 0), NULL , NULL);
          epoint sdo_geometry := sdo_geometry(2001, 8307, sdo_point_type(-87.900846, 41.967396, 0), NULL, NULL);
          dist NUMBER := 0;
          sumd NUMBER := 9999999;
          route VARCHAR2(200) := '';
          BEGIN
          --initialize
          ipoints.extend(3);
          ipoints(1) := sdo_geometry(2001, 8307,sdo_point_type( -87.905464, 41.967392, 0), NULL, NULL);
          ipoints(2) := sdo_geometry(2001, 8307,sdo_point_type( -87.904189, 41.967377, 0), NULL, NULL);
          ipoints(3) := sdo_geometry(2001, 8307,sdo_point_type( -87.901859, 41.9673795,0), NULL, NULL);
          --brute force
          FOR i IN 1..2 LOOP
          FOR j IN 1..2 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
          602.985626658242

          regards
          • 17. Re: shortest distance
            _jum
            If you want to find 3 points you have to use 3 FOR LOOPs and to concat 3 indexes for ROUTE:
            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(3);
              ipoints(1) := sdo_geometry(2001, 8307,sdo_point_type( -87.905464, 41.967392, 0), NULL, NULL);
              ipoints(2) := sdo_geometry(2001, 8307,sdo_point_type( -87.904189, 41.967377, 0), NULL, NULL);
              ipoints(3) := sdo_geometry(2001, 8307,sdo_point_type( -87.901859, 41.9673795,0), NULL, NULL);
             
              --brute force
              FOR i IN 1..3 LOOP
                FOR j IN 1..3 LOOP
                  FOR k IN 1..3 LOOP
                      --dont use same point twice !
                      IF (i=j OR i=k OR j=k) 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)||to_char(k);
                      END IF;
                  END LOOP;
                END LOOP;
              END LOOP;
             
              --length of shortest path
              dbms_output.put_line ('route='||route);
              dbms_output.put_line (sumd);
            END;
            
            route=123
            3627,935355905372
            The (here very simple) brute force method needs more and more iterations for each intermediate point (n**n), so it can't be used for big numbers of points.
            In this thread there are links and hints for other methods in these cases.
            POINTS ITERATIONS
            ----------------------------
            1            1
            2            4
            3           27
            4          265
            5         3125
            6        46656
            ...
            10 10000000000
            BTW. you should def. use code-tags, to format your code and intend the lines, you see the difference, don't you?
            • 18. Re: shortest distance
              don123
              hi

              Many thanks..
              I have marked this as answered, however, we need to find alternate solution, i mean same code to solve different intermediate points.

              regards
              • 19. Re: shortest distance
                _jum
                Many thanks!
                Found another link: Oracle Spatial Network Data Model for Traveling Salesman Problem Analysis. But didn't use Oracle Spatial NetworkData Model nor this API yet.
                1 2 Previous Next