Connect selected blocks with the smallest polyline length possible

[jtm2020hyo]

the attached file (connect.lsp) connect selected blocks to their individual nearest block without repeat a link between them.

lisp request for a starting point then connects all block since there but depending on where you put the starting point the line can have different lengths.

(numbers in the image are the length of their respective polylines)

What I need is find the smallest polyline length possible that create a link connection between selected blocks. 

like the image here

(number in the image is the length of their respective polyline)

[marko_ribar · Accepted solution]

I think that you are asking too much if there are more than 10 points... With each new point added computation required to finish the task grows geometrically, so like I said to @Anonymous you are practically doomed... The problem eventually collapses to TSP - Traveling Salesman Problem very known in computer science and it has no adequate solution that is fast and correct enough to be assumed that problem is solved... Problem existed from very long time and only approaches to answer this was through trying various greedy algorithms that may and may not be satisfactory...

Brute force method that is accurate for less than 10 pts can be found here :

http://www.theswamp.org/index.php?topic=54636.msg591196#msg591196

For more you have to dig that on your own, but I am afraid that very soon you'll be stuck with no solution...

HTH., M.R.

[jtm2020hyo]

---

@marko_ribar wrote:

I think that you are asking too much if there are more than 10 points... With each new point added computation required to finish the task grows geometrically, so like I said to @Anonymous you are practically doomed... The problem eventually collapses to TSP - Traveling Salesman Problem very known in computer science and it has no adequate solution that is fast and correct enough to be assumed that problem is solved... Problem existed from very long time and only approaches to answer this was through trying various greedy algorithms that may and may not be satisfactory...

Brute force method that is accurate for less than 10 pts can be found here :

http://www.theswamp.org/index.php?topic=54636.msg591196#msg591196

For more you have to dig that on your own, but I am afraid that very soon you'll be stuck with no solution...

HTH., M.R.

---

A solution can be forced.

creating a lisp that uses our attached "connect.lsp" below in each point/block-basepoint selected.

then for example, if I select 20 blocks, the new lisp create to manipulate "connect.lsp" should compare 20 different lengths and give us the smallest between those, and issue solved.

a comparison between length should be possible for our processor.

[dbhunia · Accepted solution]

Hi

---

@jtm2020hyo wrote: ...............

then for example, if I select 20 blocks, the new lisp create to manipulate "connect.lsp" should compare 20 different lengths and give us the smallest between those, and issue solved.

a comparison between length should be possible for our processor.

---

Check this.....(7.1.4 Permutation of n different objects)

http://ncert.nic.in/ncerts/l/keep207.pdf

There you will get (for 20 blocks) "2432902008176640000" different lengths (factorial 20 gives this value)....... including those lines which are intersecting with other lines........

Your requirement is ...... not to intersect.......

[jtm2020hyo]

Basically that happens when you consider the number of possibilities of connections between blocks, right?

But the Lisp routine attached only general 1 lines per block. The lines that pass above itself should be discarded.

What I'm trying to say is that the solution must be to begin with For the blocks furthest from the geometric center (considering a boundary arround selected blocks with aa polyline hypotitica  that encloses all selected blocks)

I do not know if it is possible to detect the blocks furthest from the center but I only describe how I would solve the problem manually by myself. It's just an idea.

PD: If it is not possible to solve it with the furthest block, then lisp try use the second furthest, then the third.

[jtm2020hyo]

---

@dbhunia wrote:

Hi

---

@jtm2020hyo wrote: ...............

then for example, if I select 20 blocks, the new lisp create to manipulate "connect.lsp" should compare 20 different lengths and give us the smallest between those, and issue solved.

a comparison between length should be possible for our processor.

---

Check this.....(7.1.4 Permutation of n different objects)

http://ncert.nic.in/ncerts/l/keep207.pdf

There you will get (for 20 blocks) "2432902008176640000" different lengths (factorial 20 gives this value)....... including those lines which are intersecting with other lines........

Your requirement is ...... not to intersect.......

---

An option to compare length between polylines created since "selected starting points" to next attached lisp (connect_blocks_all_option_bydbhunia.lsp) might be easier.

after active lisp-routine, lisp should show 2 options, the first to request to the user to choose a point, and another one that allows the user to choose some blocks/points (minimal 2) to create a polyline with this lisp individually, then comparing them and use the smallest polyline length.

the user just should choose the points that are furthest blocks/points of the center.

for example, in this image, I have 3 polyline lengths created with this LISP attached, block marked with green are points selected for the user. then lisp just should compare that 3 lengths to finding the smallest between them.

[john.uhden]

Try this.  It is currently written to connect only circles, but that's easy to change.

(defun c:route ( / ss i p plist route @closer)
  ;; Routine to draw a polyline along the shortest route from
  ;; any starting point through all circles in Modelspace
  ;; John Uhden (07-22-18)
  (defun @closer (a b c)(< (distance a b)(distance a c)))
  (and
    (setq ss (ssget "X" '((0 . "CIRCLE")(410 . "Model"))))
    (setq p (getpoint "\nStarting point: "))
    (repeat (setq i (sslength ss))
      (setq plist (cons (cdr (assoc 10 (entget (ssname ss (setq i (1- i)))))) plist))
    )
    (setq route (list p))
    (while plist
      (setq p (car (vl-sort plist '(lambda (a b)(@closer p a b))))
            plist (vl-remove p plist)
            route (cons p route)
      )
    )
    (setvar "osmode" 0)
    (setvar "cmdecho" 0)
    (vl-cmdf "_.pline")
    (mapcar 'vl-cmdf (reverse route))
    (vl-cmdf "")
  )
  (princ)
)

[jtm2020hyo]

---

@john.uhden wrote:

Try this.  It is currently written to connect only circles, but that's easy to change.

---

I was testing a lot your code.

that do what you said. in some cases not perfect but your code is better to connec.lsp ( attached)


In image a comparison. attached file tested below.

Now I have another question: Its possible add all option that has Connect_block.lsp (attached) to your ROUTE.lsp? (connect.lsp work in dynamic blocks and regular blocks)

 ... and additionally, its possible add an option to compare multiple lines create from different points/blocks/dynamic-blocks?

[jtm2020hyo]

---

@jtm2020hyo wrote:

---

@john.uhden wrote:

Try this.  It is currently written to connect only circles, but that's easy to change.

---

I was testing a lot your code.

that do what you said. in some cases not perfect but your code is better to connec.lsp ( attached)


In image a comparison. attached file tested below.

Now I have another question: Its possible add all option that has Connect_block.lsp (attached) to your ROUTE.lsp? (connect.lsp work in dynamic blocks and regular blocks)

 ... and additionally, its possible add an option to compare multiple lines create from different points/blocks/dynamic-blocks?

---

here is the link where was developed all option for connect_block.lsp attached above

[marko_ribar]

Both codes works the same way, and connect.lsp by me is faster than john's version... You added one imaginary point on your left example and starting point isn't the same... Sorry, but you haven't convinced me that your marked solution is correct... This is like I said just greedy algorithms attempts... Solution can't be found for more than 10 points... Real solution also should include beside checking for shortest overall distance intersections that may occur, like @dbhunia mentioned, and neither route.lsp nor connect.lsp check for this... Look in picture to see what I mean... You are cheating - see red circles...

[jtm2020hyo]

---

@marko_ribar wrote:

Both codes works the same way, and connect.lsp by me is faster than john's version... You added one imaginary point on your left example and starting point isn't the same... Sorry, but you haven't convinced me that your marked solution is correct... This is like I said just greedy algorithms attempts... Solution can't be found for more than 10 points... Real solution also should include beside checking for shortest overall distance intersections that may occur, like @dbhunia mentioned, and neither route.lsp nor connect.lsp check for this... Look in picture to see what I mean... You are cheating - see red circles...

---

You are right. I did not noticed that Route.lsp generated a point from the biggest circle. (because route.lisp just link circles)

(file tested attached) In this image, I compared 3 lisp routines (route.lsp, connect_block.lsp attached named 'connect' in this image and connectblk.lsp attached and named 'connect-closed' in image). now and this is the result.

connect_block.lsp is the smallest length in this image. but connect_closed.lsp connect all points with a clear polyline. but routes did not the best here.

I already read that post from swamp.org, they are trying a mathematical solution, but in the real world does not have sense generate that unnecessary work for our CPU, because of obviously polylines that has the longest length always draw lines that going over other lines and vice versa.

I never thought to add an imaginary point to create the smallest line length. this is pretty interesting and is new for me. maybe creating an imaginary point might solve this issue.

 EDIT: route.lsp and connect.lsp should have the same result. but I'm that test did not happen. I don't know what happened there.

[jtm2020hyo]

second test.

I can confirm that route.lsp and connect.lsp have same result.

connect_closed have the better result.

but I'm still impressed that an imaginary point can generate the smallest length.


ATTACHED tested file.

[john.uhden · Accepted solution]

Marko:

It may well be that making a left instead of a right may ultimately produce a shorter polyline overall, but as you pointed out the program would have to test all possible routes and then draw the shortest, all of which would be very slow and perhaps memory over-intensive.

It reminds my of my Garmin... when I take my short cut and the voice says "recalculating."  We just use Google on our Samsungs these days, but we can also run into data overages.

[john.uhden]

Here is a version with your prompts:

(defun c:route ( / ss i p plist route @closer)
  ;; Routine to draw a polyline along the shortest route from
  ;; any starting point through selected circles or inserts in Modelspace
  ;; John Uhden (07-22-18)
  ;; Rev. (11-25-18) to include inserts and selection.
  (defun @closer (a b c)(< (distance a b)(distance a c)))
  (and
    (while (or (prompt "\nSelect blocks or circles...") (not (setq ss (ssget '((0 . "INSERT,CIRCLE"))))))
      (princ "\nEmpty sel. set...")
    )
    (setq p (getpoint "\nPick or specify start point - use osnap cen or ins : "))
    (repeat (setq i (sslength ss))
      (setq plist (cons (cdr (assoc 10 (entget (ssname ss (setq i (1- i)))))) plist))
    )
    (setq route (list p))
    (while plist
      (setq p (car (vl-sort plist '(lambda (a b)(@closer p a b))))
            plist (vl-remove p plist)
            route (cons p route)
      )
    )
    (setvar "osmode" 0)
    (setvar "cmdecho" 0)
    (vl-cmdf "_.pline")
    (mapcar 'vl-cmdf (reverse route))
    (vl-cmdf "")
  )
  (princ)
)

[jtm2020hyo]

I was testing your code but do nothing in my drawing. Maybe I did something bad?

Command: Specify opposite corner or [Fence/WPolygon/CPolygon]:
Command: ROUTE-2-BY-JOHN_UHDEN
Select blocks or circles...33 found
Command:
Command: Specify opposite corner or [Fence/WPolygon/CPolygon]:
Command: ROUTE-2-BY-JOHN_UHDEN
Select blocks or circles...33 found
Command:
Command: ROUTE-2-BY-JOHN_UHDEN
Select blocks or circles...
Select objects: Specify opposite corner: 33 found
Select objects:
Command:
Command: *Cancel*
Automatic save to C:\Users\JUAN-MINIPC\AppData\Local\Temp\Drawing1_1_20175_ea9c535a.sv$ ...
Command:
Command: Specify opposite corner or [Fence/WPolygon/CPolygon]:
Command: _.erase 1 found
Command: Specify opposite corner or [Fence/WPolygon/CPolygon]:

attached file where I tested your code.

[dbhunia · Accepted solution]

Try this .......to get only the PLINE .......

(defun c:route-2-by-john_uhden ( / ss i p plist route @closer)
  ;; Routine to draw a polyline along the shortest route from
  ;; any starting point through selected circles or inserts in Modelspace
  ;; John Uhden (07-22-18)
  ;; Rev. (11-25-18) to include inserts and selection.
  (defun @closer (a b c)(< (distance a b)(distance a c)))
  (and
    ;(while (or (prompt "\nSelect blocks or circles...") (not (setq ss (ssget '((0 . "INSERT,CIRCLE"))))))
      ;(princ "\nEmpty sel. set...")
    ;)
    (setq ss (ssget '((0 . "INSERT,CIRCLE"))))
    (setq p (getpoint "\nPick or specify start point - use osnap cen or ins : "))
    (repeat (setq i (sslength ss))
      (setq plist (cons (cdr (assoc 10 (entget (ssname ss (setq i (1- i)))))) plist))
    )
    (setq route (list p))
    (while plist
      (setq p (car (vl-sort plist '(lambda (a b)(@closer p a b))))
            plist (vl-remove p plist)
            route (cons p route)
      )
    )
    (setvar "osmode" 0)
    (setvar "cmdecho" 0)
    (vl-cmdf "_.pline")
    (mapcar 'vl-cmdf (reverse route))
    (vl-cmdf "")
  )
  (princ)
)

[rpajounia]

anyway we can make this work with plines instead of circles. I will need it to only be able to get to a point through the pline below is an attachment. I was thinking best way to accomplish this if someone can write is is same concept but use the lisp shortest path since that works on a pline basis to see which point is the next closest path

[marko_ribar · Accepted solution]

I've found this result : 73.34

You have here TSP solver, though not really 100% reliable, but can give good results in a short time

(used TSP-FN.lsp)

https://www.cadtutor.net/forum/files/file/42-tspzip-travelling-salesman-problem-autolisp/ 

HTH.

M.R.

[marko_ribar]

---

@marko_ribar wrote:

I've found this result : 73.34

You have here TSP solver, though not really 100% reliable, but can give good results in a short time

(used TSP-FN.lsp)

https://www.cadtutor.net/forum/files/file/42-tspzip-travelling-salesman-problem-autolisp/ 

HTH.

M.R.

---

@jtm2020hyo 

I have update *.ZIP posted at cadtutor, so recheck it (download it again) if you need latest additions...

I have to say this, because TSP is hard problem and it needs exhaustive workaround to make something "close" or "correct to close" result...