1 2 Previous Next 19 Replies Latest reply on Oct 9, 2012 9:51 AM by _jum Go to original post
• ###### 15. Re: shortest distance
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
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
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
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
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