Author Topic: Help Finding Block Route  (Read 15123 times)

0 Members and 1 Guest are viewing this topic.

ronjonp

  • Needs a day job
  • Posts: 7327
Re: Help Finding Block Route
« Reply #15 on: August 11, 2013, 06:44:48 PM »
Yep, looks like the solution.  ::)

I don't understand, this:

This reeks of Dijkstra's algorithm...

Seems like a perfectly good response to the question:

Could someone help out or at least get me started on the thought process?

Amongst the other responses in the thread. It identifies the problem, a way to solve it and antes up pseudo code to boot.

What's the problem?


Huh?


Thanks guys .. will take a look at it on Monday. Have a nice weekend.
« Last Edit: August 11, 2013, 06:50:49 PM by ronjonp »

Windows 10 x64 - AutoCAD /C3D 2020

Custom Build PC

ymg

  • Swamp Rat
  • Posts: 725
Re: Help Finding Block Route
« Reply #16 on: August 12, 2013, 11:57:32 AM »
Ronjomp,

If it is really Dijkstra that you are after, the routine itself is not so bad to program.

The challenging part is to get the input (the graph) in correctly. You basically needs your nodes and edges and their weight (distance).
We could select it from a dwg , assuming your nodes are block and your edges would be polylines.  But this does impose good discipline as you do your drawing.

Here is a link: A Note on Two Problems in Connexion with Graphs to his original paper. 

He was a man of few words and a great mind !

ymg

Krushert

  • Seagull
  • Posts: 13656
  • FREE BEER Tomorrow!!
Re: Help Finding Block Route
« Reply #17 on: August 13, 2013, 04:29:19 PM »
Ron,

You are probably looking for code approach but I will throw out another method of skinning the cat.

Question though; would the the control wires be on identifiable with layer name or something?  A home run polyline from each remote point back to home and it length and other pertinent data can be extracted utilizing AutoCADs DataExtraction Wizard. 

Check out the attached spreadsheet that I just did yesterday for tallying up cracks and spalls in concrete.  The wizard will dump to a AutoCAD table or Excel.
I + XI = X is true ...  ... if you change your perspective.

I no longer CAD or Model, I just hang out here picking up the empties beer cans

ronjonp

  • Needs a day job
  • Posts: 7327
Re: Help Finding Block Route
« Reply #18 on: August 13, 2013, 04:41:21 PM »
Krushert,


Unfortunately the routes do not exist. I need to automate a way to figure these out :).


Thanks.


Ron

Windows 10 x64 - AutoCAD /C3D 2020

Custom Build PC

Krushert

  • Seagull
  • Posts: 13656
  • FREE BEER Tomorrow!!
Re: Help Finding Block Route
« Reply #19 on: August 13, 2013, 04:43:14 PM »
Whoops!  I thought they were already created.   :-D

I will go back to my cracks now.  Yes I am drawing more crack. 
I + XI = X is true ...  ... if you change your perspective.

I no longer CAD or Model, I just hang out here picking up the empties beer cans

ronjonp

  • Needs a day job
  • Posts: 7327
Re: Help Finding Block Route
« Reply #20 on: August 13, 2013, 05:02:15 PM »
Whoops!  I thought they were already created.   ;D

I will go back to my cracks now.  Yes I am drawing more crack. 


 :D

Windows 10 x64 - AutoCAD /C3D 2020

Custom Build PC

ymg

  • Swamp Rat
  • Posts: 725
Re: Help Finding Block Route
« Reply #21 on: August 14, 2013, 04:46:31 PM »
RonJomp,

In the attached image, do you have a node at position 8.

If it is the case, with Dijkstra  your return would be 7-6-8-4-3-2-1-0

If you don't means you have a branch from 4 to 5 and 5 to 6
but no branch from 4 to 6. In this case the return would be
7-6-5-4-3-2-1-0

In other word if you have a junction box at 8, it should be a node.

ymg


ronjonp

  • Needs a day job
  • Posts: 7327
Re: Help Finding Block Route
« Reply #22 on: August 15, 2013, 10:32:19 AM »
My thoughts were to compile a list of points based on each polyline vertex (yellow x's in the image below) . So there would be a "node" at 8 because it's an end point of a polyline.


Thanks for the reply :)

Windows 10 x64 - AutoCAD /C3D 2020

Custom Build PC

ymg

  • Swamp Rat
  • Posts: 725
Re: Help Finding Block Route
« Reply #23 on: August 16, 2013, 05:22:35 PM »
Ronjomp,

Here is my implementation of Dijkstra's algorithm plus a link http://tech-algorithm.com/articles/dijkstra-algorithm/
to probably the clearest article I've seen on it.  The test graph is the same as in this article.

You will still have to come up with a way to transform a selection into a valid graph.
There, It very much depends on how you draft your conduits.

ymg

Code - Auto/Visual Lisp: [Select]
  1. (defun c:test ()
  2.    (setq nodes '("a" "b" "c" "d" "e" "f" "g" "h")
  3.          edges '(("a" "b" 1)
  4.                  ("a" "e" 2)
  5.                  ("a" "f" 1)
  6.                  ("b" "c" 2)
  7.                  ("b" "g" 1)
  8.                  ("c" "d" 1)
  9.                  ("d" "e" 1)
  10.                  ("d" "g" 2)
  11.                  ("d" "h" 0.5)
  12.                  ("e" "f" 2)
  13.                  ("g" "h" 0.5)
  14.                 )
  15.   )
  16.  
  17.   (print (minpath "g" "f" nodes edges))
  18.  
  19.   (princ)
  20. )
  21.  
  22. ; Find the path of minimum total length between two given nodes g and f.      ;
  23. ; Using Dijkstra Algorithm                                                    ;
  24. ;                                                                             ;
  25. ; See http://tech-algorithm.com/articles/dijkstra-algorithm/                  ;
  26. ;                                                                             ;
  27. ; Written by ymg   August 2013                                                ;
  28.  
  29. (defun minpath (g f nodes edges / )
  30.         (setq   nodes (vl-remove g nodes)
  31.                 openl (list (list g 0 nil))
  32.               closedl nil
  33.         )            
  34.         (foreach n nodes
  35.              (setq nodes (subst (list n 0 nil) n nodes))
  36.         )
  37.         (while (not (= (caar closedl) f))
  38.             (setq nodname (caar openl)
  39.                   totdist (cadar openl)
  40.                   closedl (cons (car openl) closedl)
  41.                     openl (cdr openl)
  42.                   clnodes (mapcar 'car closedl)
  43.                    
  44.             )
  45.             (foreach e edges
  46.                  (setq brname nil)
  47.                  (if (= (car e) nodname) (setq brname (cadr e)))
  48.                  (if (= (cadr e) nodname) (setq brname (car e)))
  49.                  
  50.                  (if brname
  51.                     (progn
  52.                        (setq new (list brname (+ (caddr e) totdist) nodname))
  53.                        (cond
  54.                           ((member brname clnodes))                              
  55.                           ((setq oldpos (vl-position brname (mapcar 'car openl)))
  56.                              (setq old (nth oldpos openl))
  57.                              (if (< (cadr new) (cadr old))
  58.                                 (setq openl (subst new old openl))
  59.                              )  
  60.                           )    
  61.                           (t (setq openl (cons new openl)))
  62.                        )               
  63.                        (setq edges (vl-remove e edges))
  64.                     )
  65.                  )
  66.             )
  67.             (setq openl (vl-sort openl (function (lambda (a b) (< (cadr a) (cadr b))))))
  68.         )
  69.         (setq minpath (list (car closedl)))
  70.         (foreach n closedl
  71.             (if (= (car n) (caddr (car minpath)))
  72.               (setq minpath (cons n minpath))
  73.             )
  74.         )  
  75.   )
  76.  

ronjonp

  • Needs a day job
  • Posts: 7327
Re: Help Finding Block Route
« Reply #24 on: August 16, 2013, 08:53:15 PM »
Thanks ymg ..I'll take a look on Monday. Have a nice weekend. :)

Windows 10 x64 - AutoCAD /C3D 2020

Custom Build PC

Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: Help Finding Block Route
« Reply #25 on: August 16, 2013, 09:35:07 PM »

I haven't read through the entire thread, but I think you'll need a node at each block location and each pline intersection so that your edges can be defined --- that applies if the edge distance (traversal) is important.

I see the problem in 2 parts.
Defining the data. ie: node locations and edge distances.
Determining the traversal.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

--> Donate to theSwamp<--

ymg

  • Swamp Rat
  • Posts: 725
Re: Help Finding Block Route
« Reply #26 on: August 17, 2013, 12:56:38 PM »
Quote
Unfortunately the routes do not exist. I need to automate a way to figure these out .

Ronjomp,

Based on that quote, If it is automatic conduit layout that you are after, the problem is much more complicated
than simply following a route in a graph.

All kind of complications arises when you try to define the constraints.

Here is a link to a recent patent http://www.google.com/patents/WO2013086135A1?cl=en.

Even reading this it is not very clear how they do it.

In the litterature there is also some apps for laying out connection that are somewhat related.

So I am afraid that the problem is really hard.

ymg

ymg

  • Swamp Rat
  • Posts: 725
Re: Help Finding Block Route
« Reply #27 on: August 19, 2013, 01:51:18 PM »
Ronjomp,

If my assumptions are right, what you are trying to achieve is:  Given a set of instruments, find a route that will minimize the length of  conduits/wire to connect them all.

This leads you to Minimum Spanning Tree (MST)

You also probably want your conduits to run parrallel to the building lines. So you are now looking for:

 Rectilinear Minimum Spanning Tree (RMST).

 For this the problem is tractable. Look at the following link:

 Efficient minimum spanning tree construction without Delaunay triangulation

In there you’ll find some pseudocode describing an efficient way to go about it. What you would do is simply select all the blocks without any connections (No need for LWPolyline joining the blocks) and you could generate the RMST.

However your problem does not stop there.  Because by inserting junction boxes on your conduits network,  you still can minimize the length of it. So this leads you to another beast that they call:

Rectilinear Steiner Minimum Tree (RSMT)

There the problem becomes very difficult.  Here is a quote from the next paper I propose to you:

Quote
However, Garey and Johnson [3] prove that the RSMT problem is NP-complete, indicating that a polynomial-time algorithm to compute an optimal RSMT is unlikely to exist.

It does not mean that the problem cannot be resolved but that a closed solution in reasonable computing time probably does  not exist.  However some heuristic can approach the solution in computable time.

In this paper:

An Efficient Rectilinear Steiner Minimum Tree Algorithm Based on Ant Colony Optimization

They managed with their Aco-Steiner procedure to get a near optimal solution in about 50 iterations. They also give some pseudocode for achieving it.

Now enough Blah, Blah you got some coding to do :-D.

ymg
« Last Edit: August 19, 2013, 04:13:52 PM by ymg »

ronjonp

  • Needs a day job
  • Posts: 7327
Re: Help Finding Block Route
« Reply #28 on: August 19, 2013, 04:48:47 PM »
YMG,


Thanks for looking into this for me. Unfortunately I have some "real" work to do  :)  right now so this is on the back burner. I hope to look at it later in the month.


Thanks,

Ron

Windows 10 x64 - AutoCAD /C3D 2020

Custom Build PC

ribarm

  • Gator
  • Posts: 2527
  • Marko Ribar, architect
Re: Help Finding Block Route
« Reply #29 on: August 20, 2013, 11:35:41 AM »
I feel I should thank to ymg for brilliant Dijikstra algorithm... So here are some codes based on it...

THIS IS FOR TIN NETWORK

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. (defun AssocOn ( SearchTerm Lst func fuzz )
  25.   (car
  26.     (vl-member-if
  27.       (function
  28.         (lambda (pair) (equal SearchTerm (apply func (list pair)) fuzz))
  29.       )
  30.       lst
  31.     )
  32.   )
  33. )
  34.  
  35. ; Find the path of minimum total length between two given nodes g and f.      ;
  36. ; Using Dijkstra Algorithm                                                    ;
  37. ;                                                                             ;
  38. ; See http://tech-algorithm.com/articles/dijkstra-algorithm/                  ;
  39. ;                                                                             ;
  40. ; Written by ymg   August 2013                                                ;
  41.  
  42. (defun minpath ( g f nodes edges s / brname clnodes closedl dst1 dst2 m minpath mp new nodname old oldpos openl totdist )
  43.   (setq nodes   (vl-remove g nodes)
  44.         openl   (list (list g 0 nil))
  45.         closedl nil
  46.   )
  47.   (foreach n nodes
  48.     (setq nodes (subst (list n 0 nil) n nodes))
  49.   )
  50.   (while (not (equal (caar closedl) f 1e-6))
  51.     (setq nodname (caar openl)
  52.           totdist (cadar openl)
  53.           closedl (cons (car openl) closedl)
  54.           openl   (cdr openl)
  55.           clnodes (mapcar 'car closedl)
  56.  
  57.     )
  58.     (foreach e edges
  59.       (setq brname nil)
  60.       (if (equal (car e) nodname 1e-6)
  61.         (setq brname (cadr e))
  62.       )
  63.       (if (equal (cadr e) nodname 1e-6)
  64.         (setq brname (car e))
  65.       )
  66.  
  67.       (if brname
  68.         (progn
  69.           (setq new (list brname (+ (caddr e) totdist) nodname))
  70.           (cond
  71.             ((member brname clnodes))
  72.             ((setq oldpos (vl-position brname (mapcar 'car openl)))
  73.              (setq old (nth oldpos openl))
  74.              (if (< (cadr new) (cadr old))
  75.                (setq openl (subst new old openl))
  76.              )
  77.             )
  78.             (t (setq openl (cons new openl)))
  79.           )
  80.           (setq edges (vl-remove e edges))
  81.         )
  82.       )
  83.     )
  84.     (setq
  85.       openl (vl-sort openl
  86.                      (function (lambda (a b) (< (cadr a) (cadr b))))
  87.             )
  88.     )
  89.   )
  90.   (setq minpath (list (car closedl)))
  91.   (setq dst1 (cadr (car closedl)))
  92.   (setq m 1)
  93.   (foreach k closedl
  94.     (setq dst2 (cadr k))
  95.     (if (not (equal dst1 dst2 1e-6)) (setq m (1+ m) dst1 dst2))
  96.   )
  97.   (repeat m
  98.     (foreach n closedl
  99.       (if (equal (car n) (caddr (car minpath)) 1e-6)
  100.         (setq mp (cons n mp))
  101.       )
  102.     )
  103.     (setq
  104.       mp (vl-sort mp
  105.                   (function (lambda (a b) (s (vl-position (assocon (caddr a) closedl 'car 1e-6) closedl) (vl-position (assocon (caddr b) closedl 'car 1e-6) closedl))))
  106.          )
  107.     )
  108.     (setq minpath (cons (car mp) minpath))
  109.     (setq mp nil)
  110.   )
  111.   (vl-remove nil minpath)
  112. )
  113.  
  114. (defun make3dpl ( ptlst )
  115.   (entmake
  116.     (list
  117.       '(0 . "POLYLINE")
  118.       '(100 . "AcDbEntity")
  119.       '(100 . "AcDb3dPolyline")
  120.       '(66 . 1)
  121.       '(62 . 3)
  122.       '(10 0.0 0.0 0.0)
  123.       '(70 . 8)
  124.       '(210 0.0 0.0 1.0)
  125.     )
  126.   )
  127.   (foreach pt ptlst
  128.     (entmake
  129.       (list
  130.         '(0 . "VERTEX")
  131.         '(100 . "AcDbEntity")
  132.         '(100 . "AcDbVertex")
  133.         '(100 . "AcDb3dPolylineVertex")
  134.         (cons 10 pt)
  135.         '(70 . 32)
  136.       )
  137.     )
  138.   )
  139.     (list
  140.       '(0 . "SEQEND")
  141.       '(100 . "AcDbEntity")
  142.     )
  143.   )
  144. )
  145.  
  146. (defun c:shorttinpath ( / osm ss i 3df lin p1 p2 p3 linlst ptlst g f dijkstra1 ptlstpth1 dijkstra2 ptlstpth2 )
  147.   (setq osm (getvar 'osmode))
  148.   (setq ss (ssget "_:L" '((0 . "3DFACE") (8 . "*TIN"))))
  149.   (setq i -1)
  150.   (while (setq 3df (ssname ss (setq i (1+ i))))
  151.     (setq p1 (cdr (assoc 11 (entget 3df)))
  152.           p2 (cdr (assoc 12 (entget 3df)))
  153.           p3 (cdr (assoc 13 (entget 3df)))
  154.     )
  155.     (entmake (list '(0 . "LINE") (cons 10 p1) (cons 11 p2)))
  156.     (entmake (list '(0 . "LINE") (cons 10 p2) (cons 11 p3)))
  157.     (entmake (list '(0 . "LINE") (cons 10 p3) (cons 11 p1)))
  158.   )
  159.   (setq ss (ssget "_X" (list '(0 . "LINE") (cons 8 (getvar 'clayer)))))
  160.   (eraseduplin ss)
  161.   (setq ss (ssget "_X" (list '(0 . "LINE") (cons 8 (getvar 'clayer)))))
  162.   (setq i -1)
  163.   (while (setq lin (ssname ss (setq i (1+ i))))
  164.     (setq p1 (cdr (assoc 10 (entget lin)))
  165.           p2 (cdr (assoc 11 (entget lin)))
  166.     )
  167.     (setq linlst (cons (list p1 p2 (distance p1 p2)) linlst))
  168.     (setq ptlst (cons p1 ptlst) ptlst (cons p2 ptlst))
  169.     (entdel lin)
  170.   )
  171.   (setq ptlst (acet-list-remove-duplicates ptlst 1e-6))
  172.   (setvar 'osmode 1)
  173.   (setq g (getpoint "\nPick starting point on TIN : ")
  174.         f (getpoint "\nPick ending point on TIN : ")
  175.   )
  176.   (setq dijkstra1 (minpath g f ptlst linlst >))
  177.   (setq ptlstpth1 (mapcar 'car dijkstra1))
  178.   (setq dijkstra2 (minpath f g ptlst linlst >))
  179.   (setq ptlstpth2 (mapcar 'car dijkstra2))
  180.   (setq dijkstra3 (minpath g f ptlst linlst <))
  181.   (setq ptlstpth3 (mapcar 'car dijkstra3))
  182.   (setq dijkstra4 (minpath f g ptlst linlst <))
  183.   (setq ptlstpth4 (mapcar 'car dijkstra4))
  184.   (make3dpl ptlstpth1)
  185.   (make3dpl ptlstpth2)
  186.   (make3dpl ptlstpth3)
  187.   (make3dpl ptlstpth4)
  188.   (setvar 'osmode osm)
  189.   (prompt "\nShortest path length is : ") (princ (rtos (cadr (last dijkstra1)))) (prompt " - you should check length of all 4 3d polylines to match data")
  190.   (textscr)
  191.   (princ)
  192. )
  193.  

THIS IS FOR LINES NETWORK

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 s / brname clnodes closedl dst1 dst2 m minpath 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)
  18.           totdist (cadar 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)
  27.         (setq brname (cadr e))
  28.       )
  29.       (if (equal (cadr e) nodname 1e-6)
  30.         (setq brname (car e))
  31.       )
  32.  
  33.       (if brname
  34.         (progn
  35.           (setq new (list brname (+ (caddr e) totdist) nodname))
  36.           (cond
  37.             ((member brname clnodes))
  38.             ((setq oldpos (vl-position brname (mapcar 'car openl)))
  39.              (setq old (nth oldpos openl))
  40.              (if (< (cadr new) (cadr old))
  41.                (setq openl (subst new old openl))
  42.              )
  43.             )
  44.             (t (setq openl (cons new openl)))
  45.           )
  46.           (setq edges (vl-remove e edges))
  47.         )
  48.       )
  49.     )
  50.     (setq
  51.       openl (vl-sort openl
  52.                      (function (lambda (a b) (< (cadr a) (cadr b))))
  53.             )
  54.     )
  55.   )
  56.   (setq minpath (list (car closedl)))
  57.   (setq dst1 (cadr (car closedl)))
  58.   (setq m 1)
  59.   (foreach k closedl
  60.     (setq dst2 (cadr k))
  61.     (if (not (equal dst1 dst2 1e-6)) (setq m (1+ m) dst1 dst2))
  62.   )
  63.   (repeat m
  64.     (foreach n closedl
  65.       (if (equal (car n) (caddr (car minpath)) 1e-6)
  66.         (setq mp (cons n mp))
  67.       )
  68.     )
  69.     (setq
  70.       mp (vl-sort mp
  71.                   (function (lambda (a b) (s (vl-position (assocon (caddr a) closedl 'car 1e-6) closedl) (vl-position (assocon (caddr b) closedl 'car 1e-6) closedl))))
  72.          )
  73.     )
  74.     (setq minpath (cons (car mp) minpath))
  75.     (setq mp nil)
  76.   )
  77.   (vl-remove nil minpath)
  78. )
  79.  
  80. (defun AssocOn ( SearchTerm Lst func fuzz )
  81.   (car
  82.     (vl-member-if
  83.       (function
  84.         (lambda (pair) (equal SearchTerm (apply func (list pair)) fuzz))
  85.       )
  86.       lst
  87.     )
  88.   )
  89. )
  90.  
  91. (defun make3dpl ( ptlst )
  92.   (entmake
  93.     (list
  94.       '(0 . "POLYLINE")
  95.       '(100 . "AcDbEntity")
  96.       '(100 . "AcDb3dPolyline")
  97.       '(66 . 1)
  98.       '(62 . 3)
  99.       '(10 0.0 0.0 0.0)
  100.       '(70 . 8)
  101.       '(210 0.0 0.0 1.0)
  102.     )
  103.   )
  104.   (foreach pt ptlst
  105.     (entmake
  106.       (list
  107.         '(0 . "VERTEX")
  108.         '(100 . "AcDbEntity")
  109.         '(100 . "AcDbVertex")
  110.         '(100 . "AcDb3dPolylineVertex")
  111.         (cons 10 pt)
  112.         '(70 . 32)
  113.       )
  114.     )
  115.   )
  116.     (list
  117.       '(0 . "SEQEND")
  118.       '(100 . "AcDbEntity")
  119.     )
  120.   )
  121. )
  122.  
  123. (defun c:shortlinespath ( / osm ss i lin p1 p2 linlst ptlst g f dijkstra1 ptlstpth1 dijkstra2 ptlstpth2 )
  124.   (setq osm (getvar 'osmode))
  125.   (setq ss (ssget "_:L" '((0 . "LINE"))))
  126.   (setq i -1)
  127.   (while (setq lin (ssname ss (setq i (1+ i))))
  128.     (setq p1 (cdr (assoc 10 (entget lin)))
  129.           p2 (cdr (assoc 11 (entget lin)))
  130.     )
  131.     (setq linlst (cons (list p1 p2 (distance p1 p2)) linlst))
  132.     (setq ptlst (cons p1 ptlst) ptlst (cons p2 ptlst))
  133.   )
  134.   (setq ptlst (acet-list-remove-duplicates ptlst 1e-6))
  135.   (setvar 'osmode 1)
  136.   (setq g (getpoint "\nPick starting point on LINES NETWORK : ")
  137.         f (getpoint "\nPick ending point on LINES NETWORK : ")
  138.   )
  139.   (setq dijkstra1 (minpath g f ptlst linlst >))
  140.   (setq ptlstpth1 (mapcar 'car dijkstra1))
  141.   (setq dijkstra2 (minpath f g ptlst linlst >))
  142.   (setq ptlstpth2 (mapcar 'car dijkstra2))
  143.   (setq dijkstra3 (minpath g f ptlst linlst <))
  144.   (setq ptlstpth3 (mapcar 'car dijkstra3))
  145.   (setq dijkstra4 (minpath f g ptlst linlst <))
  146.   (setq ptlstpth4 (mapcar 'car dijkstra4))
  147.   (make3dpl ptlstpth1)
  148.   (make3dpl ptlstpth2)
  149.   (make3dpl ptlstpth3)
  150.   (make3dpl ptlstpth4)
  151.   (setvar 'osmode osm)
  152.   (prompt "\nShortest path length is : ") (princ (rtos (cadr (last dijkstra1)))) (prompt " - you should check length of all 4 3d polylines to match data")
  153.   (textscr)
  154.   (princ)
  155. )
  156.  

And this one removes duplicate lines and 0 lines - it's different from overkill, for it doesn't combine overlapped lines into big line - it just removes sufficient ones...

Code: [Select]
(defun unique ( linlst )
  (if (car linlst) (cons (car linlst) (unique (_vl-remove (car linlst) (_vl-remove (list (cadar linlst) (caar linlst)) (cdr linlst) 1e-6) 1e-6))))
)

(defun _vl-remove ( el lst fuzz )
  (vl-remove-if '(lambda ( x ) (and (equal (car x) (car el) fuzz) (equal (cadr x) (cadr el) fuzz))) lst)
)

(defun eraseduplin ( ss / i lin p1 p2 lay linlst linlstn )
  (setq i -1)
  (while (setq lin (ssname ss (setq i (1+ i))))
    (setq p1 (cdr (assoc 10 (entget lin)))
          p2 (cdr (assoc 11 (entget lin)))
          lay (cdr (assoc 8 (entget lin)))
    )
    (setq linlst (cons (list p1 p2) linlst))
    (entdel lin)
  )
  (setq linlstn (unique linlst))
  (foreach lin linlstn
    (entmake (list '(0 . "LINE") (cons 8 lay) (cons 10 (car lin)) (cons 11 (cadr lin))))
  )
)

(defun c:eraseduplines-0lines ( / ss s i lin )
  (setq ss (ssget "_:L" '((0 . "LINE"))))
  (setq s (ssadd))
  (setq i -1)
  (while (setq lin (ssname ss (setq i (1+ i))))
    (if (equal (cdr (assoc 10 (entget lin))) (cdr (assoc 11 (entget lin))) 1e-6) (entdel lin) (ssadd lin s))
  )
  (eraseduplin s)
  (princ)
)

(defun c:ed0l nil (c:eraseduplines-0lines))

M.R.
« Last Edit: August 22, 2013, 06:09:36 PM by ribarm »
Marko Ribar, d.i.a. (graduated engineer of architecture)

:)

M.R. on Youtube