### Author Topic: Help Finding Block Route  (Read 12300 times)

0 Members and 1 Guest are viewing this topic.

#### ymg

• Swamp Rat
• Posts: 725 ##### Re: Help Finding Block Route
« Reply #30 on: August 20, 2013, 12:35:55 PM »
Quote
I feel I should thank to ymg for brilliant Dijikstra algorithm

Marko,

Hope everybody understand that the brilliance is with Dijkstra not with me.

What tou are achieving with your SHORTTINPATH function is actually a subset of the Euclidian Minimum Spanning Tree.
The whole tree should encompass all the points.

For this there is Prim's algorithm, or even Djiktra's but Problem 1 from his 1959 paper.

You are right in the fact that the EMST will always lie along the edges of a Delaunay triangulation.

ymg

#### qdzung

• Guest ##### Re: Help Finding Block Route
« Reply #31 on: August 22, 2013, 03:55:55 AM »
Great!!!
I have try to dev. my tool to automatic cable route and mto with VBA, but ... :ugly:

Finally chang to lisp and I found this topic Thanks for all!

#### ribarm ##### Re: Help Finding Block Route
« Reply #32 on: August 22, 2013, 08:41:58 AM »
Not so great!!!

I've found some wrong calculations in Dijkstra... See my attached *.dwg and *.jpg...

So long from being correct...   Marko Ribar, d.i.a. (graduated engineer of architecture) #### ribarm ##### Re: Help Finding Block Route
« Reply #33 on: August 22, 2013, 03:20:26 PM »
I've changed my codes posted at the end of page #2... The problem was in (minpath) subfunction; also had to add (AssocOn) to make it work correctly... Also now it's slower, but that is the fact if wanted to be OK...

Cheers, M.R.   Marko Ribar, d.i.a. (graduated engineer of architecture) #### ymg

• Swamp Rat
• Posts: 725 ##### Re: Help Finding Block Route
« Reply #34 on: August 22, 2013, 03:48:19 PM »
Quote
I've found some wrong calculations in Dijkstra...

Marko,

I doubt that you can extend minpath to the sphere just like that.
That why they invented geodetic calculations.

Your distance on a sphere have to be great circle.
You will have also to take care of pole effect.

So Dijkstra's stands if you apply it to the plan.

ymg

#### ribarm ##### Re: Help Finding Block Route
« Reply #35 on: August 22, 2013, 04:33:05 PM »
I don't quite know... It gave me correct results after my modifications first time, after that checked once more and it was wrong, then rotated view (3dorbit) and picked points from 3D but now last point as first and first as last and it was OK...

I just don't understand it seems you're right ymg... But now codes are better as it may give correct result in bigger probability...
Marko Ribar, d.i.a. (graduated engineer of architecture) #### ribarm ##### Re: Help Finding Block Route
« Reply #36 on: August 22, 2013, 06:13:38 PM »
So, I've changed codes again... Now it creates 4 different 3d polylines if it's something like geodesic-sphere... One of these should be correct one, I guess...

M.R.
For planar TINs it works fine - all 4 3d polylines overlap each other - all are correct...
Marko Ribar, d.i.a. (graduated engineer of architecture) #### ribarm ##### Re: Help Finding Block Route
« Reply #37 on: August 23, 2013, 06:01:24 AM »
Here they are... FINAL VERSIONS ...  So slooooooooooooow, but finally correct result even for geodesic spheres...

Code - Auto/Visual Lisp: [Select]
1. (defun unique ( linlst )
2.   (if (car linlst) (cons (car linlst) (unique (_vl-remove (car linlst) (_vl-remove (list (cadar linlst) (caar linlst)) (cdr linlst) 1e-6) 1e-6))))
3. )
4.
5. (defun _vl-remove ( el lst fuzz )
6.   (vl-remove-if '(lambda ( x ) (and (equal (car x) (car el) fuzz) (equal (cadr x) (cadr el) fuzz))) lst)
7. )
8.
9. (defun eraseduplin ( ss / i lin p1 p2 linlst linlstn )
10.   (setq i -1)
11.   (while (setq lin (ssname ss (setq i (1+ i))))
12.     (setq p1 (cdr (assoc 10 (entget lin)))
13.           p2 (cdr (assoc 11 (entget lin)))
14.     )
15.     (setq linlst (cons (list p1 p2) linlst))
16.     (entdel lin)
17.   )
18.   (setq linlstn (unique linlst))
19.   (foreach lin linlstn
20.     (entmake (list '(0 . "LINE") (cons 10 (car lin)) (cons 11 (cadr lin))))
21.   )
22. )
23.
24. ; Find the path of minimum total length between two given nodes g and f.      ;
25. ; Using Dijkstra Algorithm                                                    ;
26. ;                                                                             ;
27. ; See http://tech-algorithm.com/articles/dijkstra-algorithm/                  ;
28. ;                                                                             ;
29. ; Written by ymg   August 2013                                                ;
30.
31. (defun minpath ( g f nodes edges / brname clnodes closedl dst1 dst2 m minpath minpathn mp new nodname old oldpos openl totdist )
32.   (setq nodes   (vl-remove g nodes)
33.         openl   (list (list g 0 nil))
34.         closedl nil
35.   )
36.   (foreach n nodes
37.     (setq nodes (subst (list n 0 nil) n nodes))
38.   )
39.   (while (not (equal (caar closedl) f 1e-6))
40.     (setq nodname (caar openl)
42.           closedl (cons (car openl) closedl)
43.           openl   (cdr openl)
44.           clnodes (mapcar 'car closedl)
45.
46.     )
47.     (foreach e edges
48.       (setq brname nil)
49.       (if (equal (car e) nodname 1e-6)
51.       )
52.       (if (equal (cadr e) nodname 1e-6)
53.         (setq brname (car e))
54.       )
55.
56.       (if brname
57.           (setq new (list brname (+ (caddr e) totdist) nodname))
58.           (cond
59.             ((member brname clnodes))
60.             ((setq oldpos (vl-position brname (mapcar 'car openl)))
61.              (setq old (nth oldpos openl))
63.                (setq openl (subst new old openl))
64.              )
65.             )
66.             (t (setq openl (cons new openl)))
67.           )
68.           (setq edges (vl-remove e edges))
69.         )
70.       )
71.     )
72.     (setq
73.       openl (vl-sort openl
75.             )
76.     )
77.   )
78.   (setq minpath (list (list (car closedl))))
79.   (setq dst1 (cadr (car closedl)))
80.   (setq m 1)
81.   (foreach k closedl
83.     (if (not (equal dst1 dst2 1e-6)) (setq m (1+ m) dst1 dst2))
84.   )
85.   (repeat m
86.     (foreach n closedl
87.       (if (= (length minpath) 1)
88.         (if (equal (car n) (caddr (caar minpath)) 1e-6) (setq mp (cons n mp)))
89.         (mapcar '(lambda (x) (if (equal (car n) (caddr (car x)) 1e-6) (setq mp (cons n mp)))) minpath)
90.       )
91.     )
92.     (setq mp (vl-sort mp '(lambda (a b) (not (equal (car b) (car a) 1e-6)))))
93.     (if (= (length minpath) 1)
94.       (setq minpath (mapcar '(lambda (x) (cons x (car minpath))) mp))
95.       (setq minpath (mapcar '(lambda (x) (mapcar '(lambda (y) (if (equal (car x) (caddr (car y)) 1e-6) (cons x y))) minpath)) mp))
96.     )
97.     (setq minpath (mapcar '(lambda (x) (vl-remove nil x)) minpath))
98.     (if (listp (caaaar minpath)) (setq minpath (apply 'append minpath)))
99.     (mapcar '(lambda (x) (if (eq (caddr (car x)) nil) (setq minpathn (cons x minpathn)))) minpath)
100.     (setq mp nil)
101.   )
102.   (setq minpathn (acet-list-remove-duplicates minpathn nil))
103.   (setq minpathn (vl-remove nil minpathn))
104. )
105.
106. (defun make3dpl ( ptlst )
107.     (list
108.       '(0 . "POLYLINE")
109.       '(100 . "AcDbEntity")
110.       '(100 . "AcDb3dPolyline")
111.       '(66 . 1)
112.       '(62 . 3)
113.       '(10 0.0 0.0 0.0)
114.       '(70 . 8)
115.       '(210 0.0 0.0 1.0)
116.     )
117.   )
118.   (foreach pt ptlst
119.       (list
120.         '(0 . "VERTEX")
121.         '(100 . "AcDbEntity")
122.         '(100 . "AcDbVertex")
123.         '(100 . "AcDb3dPolylineVertex")
124.         (cons 10 pt)
125.         '(70 . 32)
126.       )
127.     )
128.   )
129.     (list
130.       '(0 . "SEQEND")
131.       '(100 . "AcDbEntity")
132.     )
133.   )
134. )
135.
136. (defun c:shorttinpath ( / osm ss i 3df lin p1 p2 p3 linlst ptlst g f dijkstra ptlstpths pl )
137.   (setq osm (getvar 'osmode))
138.   (setq ss (ssget "_:L" '((0 . "3DFACE") (8 . "*TIN"))))
139.   (setq i -1)
140.   (while (setq 3df (ssname ss (setq i (1+ i))))
141.     (setq p1 (cdr (assoc 11 (entget 3df)))
142.           p2 (cdr (assoc 12 (entget 3df)))
143.           p3 (cdr (assoc 13 (entget 3df)))
144.     )
145.     (entmake (list '(0 . "LINE") (cons 10 p1) (cons 11 p2)))
146.     (entmake (list '(0 . "LINE") (cons 10 p2) (cons 11 p3)))
147.     (entmake (list '(0 . "LINE") (cons 10 p3) (cons 11 p1)))
148.   )
149.   (setq ss (ssget "_X" (list '(0 . "LINE") (cons 8 (getvar 'clayer)))))
150.   (eraseduplin ss)
151.   (setq ss (ssget "_X" (list '(0 . "LINE") (cons 8 (getvar 'clayer)))))
152.   (setq i -1)
153.   (while (setq lin (ssname ss (setq i (1+ i))))
154.     (setq p1 (cdr (assoc 10 (entget lin)))
155.           p2 (cdr (assoc 11 (entget lin)))
156.     )
157.     (setq linlst (cons (list p1 p2 (distance p1 p2)) linlst))
158.     (setq ptlst (cons p1 ptlst) ptlst (cons p2 ptlst))
159.     (entdel lin)
160.   )
161.   (setq ptlst (acet-list-remove-duplicates ptlst 1e-6))
162.   (setvar 'osmode 1)
163.   (setq g (getpoint "\nPick starting point on TIN : ")
164.         f (getpoint "\nPick ending point on TIN : ")
165.   )
166.   (setq dijkstra (minpath g f ptlst linlst))
167.   (setq ptlstpths (mapcar '(lambda (x) (mapcar 'car x)) dijkstra))
168.   (mapcar '(lambda (x) (make3dpl x)) ptlstpths)
169.   (prompt "\nShortest path length is : ") (princ (rtos (setq len (cadr (last (car dijkstra)))))) (prompt " - you should check length to match data")
170.   (setq ss (ssget "_X" (list '(0 . "POLYLINE") '(70 . 8) (cons 8 (getvar 'clayer)))))
171.   (setq i -1)
172.   (while (setq pl (ssname ss (setq i (1+ i))))
173.     (if (not (equal (vla-get-length (vlax-ename->vla-object pl)) len 1e-6)) (entdel pl))
174.   )
175.   (setvar 'osmode osm)
176.   (textscr)
177.   (princ)
178. )
179.

Code - Auto/Visual Lisp: [Select]
1. ; Find the path of minimum total length between two given nodes g and f.      ;
2. ; Using Dijkstra Algorithm                                                    ;
3. ;                                                                             ;
4. ; See http://tech-algorithm.com/articles/dijkstra-algorithm/                  ;
5. ;                                                                             ;
6. ; Written by ymg   August 2013                                                ;
7.
8. (defun minpath ( g f nodes edges / brname clnodes closedl dst1 dst2 m minpath minpathn mp new nodname old oldpos openl totdist )
9.   (setq nodes   (vl-remove g nodes)
10.         openl   (list (list g 0 nil))
11.         closedl nil
12.   )
13.   (foreach n nodes
14.     (setq nodes (subst (list n 0 nil) n nodes))
15.   )
16.   (while (not (equal (caar closedl) f 1e-6))
17.     (setq nodname (caar openl)
19.           closedl (cons (car openl) closedl)
20.           openl   (cdr openl)
21.           clnodes (mapcar 'car closedl)
22.
23.     )
24.     (foreach e edges
25.       (setq brname nil)
26.       (if (equal (car e) nodname 1e-6)
28.       )
29.       (if (equal (cadr e) nodname 1e-6)
30.         (setq brname (car e))
31.       )
32.
33.       (if brname
34.           (setq new (list brname (+ (caddr e) totdist) nodname))
35.           (cond
36.             ((member brname clnodes))
37.             ((setq oldpos (vl-position brname (mapcar 'car openl)))
38.              (setq old (nth oldpos openl))
40.                (setq openl (subst new old openl))
41.              )
42.             )
43.             (t (setq openl (cons new openl)))
44.           )
45.           (setq edges (vl-remove e edges))
46.         )
47.       )
48.     )
49.     (setq
50.       openl (vl-sort openl
52.             )
53.     )
54.   )
55.   (setq minpath (list (list (car closedl))))
56.   (setq dst1 (cadr (car closedl)))
57.   (setq m 1)
58.   (foreach k closedl
60.     (if (not (equal dst1 dst2 1e-6)) (setq m (1+ m) dst1 dst2))
61.   )
62.   (repeat m
63.     (foreach n closedl
64.       (if (= (length minpath) 1)
65.         (if (equal (car n) (caddr (caar minpath)) 1e-6) (setq mp (cons n mp)))
66.         (mapcar '(lambda (x) (if (equal (car n) (caddr (car x)) 1e-6) (setq mp (cons n mp)))) minpath)
67.       )
68.     )
69.     (setq mp (vl-sort mp '(lambda (a b) (not (equal (car b) (car a) 1e-6)))))
70.     (if (= (length minpath) 1)
71.       (setq minpath (mapcar '(lambda (x) (cons x (car minpath))) mp))
72.       (setq minpath (mapcar '(lambda (x) (mapcar '(lambda (y) (if (equal (car x) (caddr (car y)) 1e-6) (cons x y))) minpath)) mp))
73.     )
74.     (setq minpath (mapcar '(lambda (x) (vl-remove nil x)) minpath))
75.     (if (listp (caaaar minpath)) (setq minpath (apply 'append minpath)))
76.     (mapcar '(lambda (x) (if (eq (caddr (car x)) nil) (setq minpathn (cons x minpathn)))) minpath)
77.     (setq mp nil)
78.   )
79.   (setq minpathn (acet-list-remove-duplicates minpathn nil))
80.   (setq minpathn (vl-remove nil minpathn))
81. )
82.
83. (defun make3dpl ( ptlst )
84.     (list
85.       '(0 . "POLYLINE")
86.       '(100 . "AcDbEntity")
87.       '(100 . "AcDb3dPolyline")
88.       '(66 . 1)
89.       '(62 . 3)
90.       '(10 0.0 0.0 0.0)
91.       '(70 . 8)
92.       '(210 0.0 0.0 1.0)
93.     )
94.   )
95.   (foreach pt ptlst
96.       (list
97.         '(0 . "VERTEX")
98.         '(100 . "AcDbEntity")
99.         '(100 . "AcDbVertex")
100.         '(100 . "AcDb3dPolylineVertex")
101.         (cons 10 pt)
102.         '(70 . 32)
103.       )
104.     )
105.   )
106.     (list
107.       '(0 . "SEQEND")
108.       '(100 . "AcDbEntity")
109.     )
110.   )
111. )
112.
113. (defun c:shortlinespath ( / osm ss i lin p1 p2 linlst ptlst g f dijkstra ptlstpths pl )
114.   (setq osm (getvar 'osmode))
115.   (setq ss (ssget "_:L" '((0 . "LINE"))))
116.   (setq i -1)
117.   (while (setq lin (ssname ss (setq i (1+ i))))
118.     (setq p1 (cdr (assoc 10 (entget lin)))
119.           p2 (cdr (assoc 11 (entget lin)))
120.     )
121.     (setq linlst (cons (list p1 p2 (distance p1 p2)) linlst))
122.     (setq ptlst (cons p1 ptlst) ptlst (cons p2 ptlst))
123.   )
124.   (setq ptlst (acet-list-remove-duplicates ptlst 1e-6))
125.   (setvar 'osmode 1)
126.   (setq g (getpoint "\nPick starting point on LINES NETWORK : ")
127.         f (getpoint "\nPick ending point on LINES NETWORK : ")
128.   )
129.   (setq dijkstra (minpath g f ptlst linlst))
130.   (setq ptlstpths (mapcar '(lambda (x) (mapcar 'car x)) dijkstra))
131.   (mapcar '(lambda (x) (make3dpl x)) ptlstpths)
132.   (prompt "\nShortest path length is : ") (princ (rtos (setq len (cadr (last (car dijkstra)))))) (prompt " - you should check length to match data")
133.   (setq ss (ssget "_X" (list '(0 . "POLYLINE") '(70 . 8) (cons 8 (getvar 'clayer)))))
134.   (setq i -1)
135.   (while (setq pl (ssname ss (setq i (1+ i))))
136.     (if (not (equal (vla-get-length (vlax-ename->vla-object pl)) len 1e-6)) (entdel pl))
137.   )
138.   (setvar 'osmode osm)
139.   (textscr)
140.   (princ)
141. )
142.

I think it can't be faster...
M.R.   « Last Edit: August 23, 2013, 06:48:46 AM by ribarm »
Marko Ribar, d.i.a. (graduated engineer of architecture) #### ronjonp ##### Re: Help Finding Block Route
« Reply #38 on: August 26, 2013, 11:23:49 AM »
First off I want to thank YMG for converting the algorithm to lisp and Marko for his many examples .

Here is my contribution (for 2d) which works on a network of polylines and block locations on (or close) to those polylines.
I did a little bit of cleanup to add routes between block locations as well as for points of polylines that reside within a fuzz value of another polyline within the network.

There is still some work to be done to the code for creating the network more correctly, but it seems to be working fairly well for my uses.

Have fun. Windows 10 x64 - AutoCAD /C3D 2020

Custom Build PC

#### ribarm ##### Re: Help Finding Block Route
« Reply #39 on: August 26, 2013, 12:25:29 PM »
Well done, Ron...

I didn't follow you what do you initially wanted to achieve, but now I see it... I've picked some other home node, and it returned correct results... What is the problem with fuzz factor? I don't see where it should be different? Fuzz factor - X scale factor of nodes is 10.0 - I've changed it to 1.0 and still it did correctly calculations...
Marko Ribar, d.i.a. (graduated engineer of architecture) #### ronjonp ##### Re: Help Finding Block Route
« Reply #40 on: August 26, 2013, 01:02:47 PM »
Marko,

For the example I posted, the fuzz value will be fine. The line is just there to alert other people using the code that it may need to be adjusted for different scenarios. Windows 10 x64 - AutoCAD /C3D 2020

Custom Build PC

#### ymg

• Swamp Rat
• Posts: 725 ##### Re: Help Finding Block Route
« Reply #41 on: August 26, 2013, 07:10:56 PM »
RonJomp,

Glad I could help a bit. This being said, I still don't understand what it is you are doing ?

The network of polylines, what does it represents ?

Here,  yet another link to a paper that probably could help qdzung:

A Heuristic Technique For The Generation Of A Network Geometry For Rural Natural Gas Distribution Systems

Good thing they invented Cut&Paste with such long titles.

ymg

#### ronjonp ##### Re: Help Finding Block Route
« Reply #42 on: August 26, 2013, 07:59:41 PM »
YMG,

The existing route is a pipe network. The blocks are valves connected to the pipe network. These valves have to be wired to a controller and generally follow the path of the pipes back to the controller. Dijkstra's algorithm finds the shortest route along the pipes from each of these valves back to the controller. Clear as mud ? Ron

Windows 10 x64 - AutoCAD /C3D 2020

Custom Build PC

#### jvillarreal ##### Re: Help Finding Block Route
« Reply #43 on: June 25, 2015, 09:42:58 AM »
This is pure brilliance. Should be in the show my stuff section imo.

FYI - The _createedges function errored out for me here:

(>= (distance (setq p2 (vlax-curve-getpointatparam e (1+ (fix pa)))) p) fuzz)

changing it to:
(setq p2 (vlax-curve-getpointatparam e (1+ (fix pa))))
(>= (distance p2 p) fuzz)

worked for me.

#### ronjonp ##### Re: Help Finding Block Route
« Reply #44 on: June 25, 2015, 10:24:14 AM »
This is pure brilliance. Should be in the show my stuff section imo.

FYI - The _createedges function errored out for me here:

(>= (distance (setq p2 (vlax-curve-getpointatparam e (1+ (fix pa)))) p) fuzz)

changing it to:
(setq p2 (vlax-curve-getpointatparam e (1+ (fix pa))))
(>= (distance p2 p) fuzz)

worked for me.
Thanks for reporting the error .. Here's the updated function that checks if there is a point before passing it to the distance command.

Code - Auto/Visual Lisp: [Select]
1.   ;; If the endpoint is within the fuzz factor distance of another polyline
2.   ;; and not already at an endpoint, create 'edges' from that point
3.   ;; to the adjacent vertices
4.   (defun _createedges (p l fuzz / cp out p p1 p2 pa)
5.     (foreach e l
6.       (if (and (setq cp (vlax-curve-getclosestpointto e p))
7.                (<= (distance p cp) fuzz)
8.                (setq pa (vlax-curve-getparamatpoint e cp))
9.                (setq p1 (vlax-curve-getpointatparam e (fix pa)))
10.                (>= (distance p1 p) fuzz)
11.                (setq p2 (vlax-curve-getpointatparam e (1+ (fix pa))))
12.                (>= (distance p2 p) fuzz)
13.           )
14.         (setq out (cons (list (list p p1 (distance p p1)) (list p p2 (distance p p2))) out))
15.       )
16.     )
17.     (apply 'append out)
18.   )
« Last Edit: June 25, 2015, 10:28:30 AM by ronjonp »

Windows 10 x64 - AutoCAD /C3D 2020

Custom Build PC