Finding All Of The Connected Polylines

[mgorecki]

First, the attached drawing is just a mini example of the actual drawing.  The actual drawing could contain 10000 bumps all connected with polylines.  Because Autocad glitches on selection sets when the drawing has been zoomed to extents, I decided to use a list of all of the polylines.  The list will contain the coordinates (start and end points) and the entity name.

(setq polyConnectionList
 '(((1677.03 6268.21) (1549.45 6390.17) (<Entity name: 1c89f2565a0>))
  ((1580.3 6129.39) (1677.03 6268.21) (<Entity name: 1c89f256540>))
  ((1778.06 6129.39) (1874.79 6268.21) (<Entity name: 1c89f256320>)) 
  ((1481.42 6030.51) (1283.66 6030.51) (<Entity name: 1c89f2560b0>))
  ((1876.94 6030.51) (1679.18 6030.51) (<Entity name: 1c89f256090>))
  ((1580.3 6129.39) (1778.06 6129.39) (<Entity name: 1c89f256080>))
  ((1382.54 6129.39) (1580.3 6129.39) (<Entity name: 1c89f256070>))))

This function will be sent the a start and end point  in a list called "polyEndpoints" ((1382.54 6129.39) (1580.3 6129.39)).

I have some code (by some great help from ronjonp) that finds a connecting coordinate.  It uses vl-some, but that stops after finding the first match.  I would like to get a list of every polyline connected in a chain to the initial polyline (polyEndpoints).

This worked great, but I only got the next polyline.

(foreach pt polyEndpoints
 (if (setq plineInfo (vl-some '(lambda (x) (if (or (equal pt (car x) 1e-8)
                                                   (equal pt (cadr x) 1e-8)) x)) polyConnectionList))
 (setq connectedPolyList (cons plineInfo connectedPolyList)
       polyConnectionList (vl-remove plineInfo polyConnectionList)))
)

This also worked, but only got the two that are connected to the initial polyline.

(foreach pt polyEndpoints
 (foreach item polyConnectionList
  (if (or (equal pt (car item) 1e-8) (equal pt (cadr item) 1e-8))
   (setq connectedPolyList (cons plineInfo connectedPolyList)
         polyConnectionList (vl-remove plineInfo polyConnectionList)))
 )
)

Does anyone have a method (not asking for code, although it would help), I'm trying to come up with a plan in plain english that will loop through the polyConnectionList and find whats connected to the first coordinates, then the next, then the next until I have a group that are all touching, taking into account the branches.  In one list there will be the five polylines, and then there will be 2 lists with just one polyline in each.

Thanks in advance.

[Sea-Haven]

There must be an algorithm out there as drainage design has been doing this for years auto connecting a "TREE" of drainage branches eg 100 pits. Yes hard part is finding. It is the sort of thing a mathematician has worked out. Some one may have stumbled on it.

[CADaSchtroumpf]

I tried myself at this task.
So far I have come to this point.
I give you the code if it can be a start for you.

(defun compare (l d l_e / prm new_l)
  (mapcar
    '(lambda (e)
      (mapcar
        '(lambda (x)
          (setq prm
            (cond
              ((equal (cadr x) (vlax-curve-getClosestPointTo e (cadr x) T) d)
                (vlax-curve-getparamatpoint e (trans (cadr x) e 0))
              )
              ((equal (last x) (vlax-curve-getClosestPointTo e (last x) T) d)
                (vlax-curve-getparamatpoint e (trans (last x) e 0))
              )
            )
          )
          (if (and prm (not (member (car x) l_e)))
            (progn
              (ssadd (car x) ss)
              (setq new_l (cons (car x) l_e))
            )
          )
        )
        l
      )
    )
    l_e
  )
  (if new_l new_l nil)
)
(defun list_pt_sel (l_e / dxf_ent)
  (mapcar
    '(lambda (e)
      (setq dxf_ent (entget e))
      (cons
        e
        (mapcar
          '(lambda (x)
            (trans x e 0)
          )
          (mapcar 'cdr
            (vl-remove-if
              '(lambda (x)
                (/= (car x) 10)
              )
              dxf_ent
            )
          )
        )
      )
    )
    l_e
  )
)
(defun c:pl_connect ( / dfzz js_all n e_all js_first ss e_master lst_pt_ori e_other lst_pt l)
  (if (not dfzz) (setq dfzz 1E-08))
  (princ "\nSelect polylines")
  (while (not (setq js_all (ssget '((0 . "LWPOLYLINE"))))))
  (repeat (setq n (sslength js_all))
    (setq e_all (cons (ssname js_all (setq n (1- n))) e_all))
  )
  (princ "\Select ONE central polyline")
  (while (not (setq js_first (ssget "_+.:E:S" '((0 . "LWPOLYLINE"))))))
  (setq ss (ssadd))
  (setq e_master (ssname js_first 0))
  (setq ss (ssadd e_master ss))
  (setq lst_pt_ori (list_pt_sel e_all))
  (cond
    (lst_pt_ori
      (setq e_other e_all)
      (setq e_other (vl-remove e_master e_other))
      (cond
        (e_other
          (setq lst_pt (list_pt_sel e_other))
          (setq l (list e_master))
          (while l
            (setq l (compare lst_pt dfzz l))
          )
        )
      )
      (sssetfirst nil ss)
    )
  )
)

[Kent1Cooper]

Set FSMODE = ON, and use FASTSEL.

[mgorecki]

Hi, thank you for the code.  I will definitely look into it.  I really appreciate your help.

[mgorecki]

Hi Kent,

I'm using lists of endpoints instead of using selection sets.  Autocad doesn't do well with selection sets when zoomed out.  

[ronjonp]

@mgorecki THIS too.

[Kent1Cooper]

---

@mgorecki wrote:

....  Autocad doesn't do well with selection sets when zoomed out.  

---

"Doesn't do well" could mean different things.  [Doesn't find everything you expect it to?  Finds things that don't belong?  A mixture of the two?]  But whatever the shortcomings, there may be ways to prevent them, without elaborate code.  If you just turn off all Layers except that of the Polylines, does FASTSEL find all the connected pieces?

[mgorecki]

Thanks Ron, I'll take a look.

[mgorecki]

Hi Kent, I created very small crossing selection windows, but it was still selecting things outside of the window.  This only happens when the drawing is zoomed out to see the whole thing, but it needs to see the whole thing.  I will check out the FASTSEL though and let you know if I can get it to work.

[ronjonp]

@mgorecki Quick test and fastsel does not grab items out of view:

[Kent1Cooper]

---

@mgorecki wrote:

....

Does anyone have a method (not asking for code, although it would help), I'm trying to come up with a plan in plain english that will loop through the polyConnectionList and find whats connected to the first coordinates, then the next, then the next until I have a group that are all touching, taking into account the branches.  .....

---

Here's a thought:  The (assoc) function in AutoLisp is typically used with a number as the association "key" [the first item in a sub-list to look for], such as in entity data lists.  But it can also use a point list for that -- any kind of thing that can be the first item in a sub-list.  So in your sample list, this would find a second entry in the list that shares a start point with the first entry:

(setq plbase1 (car polyConnectionList)); the first entry in the list

(if (setq plmeet (assoc (car plbase1) (cdr polyConnectionList)))

;; i.e. use start point to check for another with the same start point, in the list after the first entry

  (....then, put that other one into a list of those that connect to plbase1....)

And if you make another list with the start and end points switched:

(setq polyConnectionListRev

  (mapcar

    '(lambda (x) (list (nth 1 x) (nth 0 x) (nth 2 x)))

    polyConnectionList

  )

)

so that the end points are the first items in the sub-lists, then you can check whether the first entry's start point is the same as the end point of any other one:

(if (setq plmeet (assoc (car plbase1) (cdr polyConnectionListRev)))

;; i.e. use start point to check for another with the same point at its end

  (....then, put that other one into the same list....)

No need to do something like compare every point with every other -- it will directly find only what [if anything] meets a given Polyline at its ends.

A complication is if there are more than two meeting at the same point.  The above will find only the first of the meeting ones.  Do you remove one that meets from the list and try again, until it doesn't find one?

Another possible complication is the question of numerical precision.  Can you rely on those point lists to represent exactly the same value for both Polylines that meet at a given point?  I tried in your sample list, using the first point list in the second one [the ((1580.3... line], and it did find the second-to-last entry.

After finding all that meet the reference one, the list of what it found can be stepped through looking for further meeting ones in the same way.  It would need to check whether what it finds is already in the list, because some of them will be.

[Kent1Cooper]

---

@ronjonp wrote:

@mgorecki Quick test and fastsel does not grab items out of view:

---

... but of course, if they do it Zoomed out as described, and if FASTSEL finds things as desired when Zoomed out, that would not be an issue.

[ronjonp]

@Kent1Cooper Simply pointing out a limitation of your suggestion. A limitation that Lee's code does not have. 😉

[ronjonp]

@mgorecki You might as well use Lee's code .. he's done all the heavy lifting for you. The 's2' variable at the end holds all your items that are connected. Convert that to a list and do whatever it is you're trying to accomplish.

[mgorecki]

Hi Ron, thank you again for helping me out.  I'll try Lee's code and it gives me something to study and learn from.  I really appreciate you taking the time to help me with my code.

[mgorecki]

Hi Kent, Thank you for the information on the FASTSEL command.  I have it saved off and will probably use it in other programs.  Also thank you for taking the time to answer my post.

[mgorecki · Accepted solution]

Ok, I finally came up with something that creates a list of connected LWPOLYLINES based on lists of the polylines.

initialPolyEnt = ((1382.54 6129.39) (1580.3 6129.39) (<Entity name: 10fd1674070>))  ;One of the polys in the sameLayerPolyList

(setq sameLayerPolyList 

'(((1677.03 6268.21) (1803.8 6474.93) (<Entity name: 10fd16a6070>))
'((1677.03 6268.21) (1549.45 6390.17) (<Entity name: 10fd16745a0>))
'((1580.3 6129.39) (1677.03 6268.21) (<Entity name: 10fd1674540>))
'((1778.06 6129.39) (1874.79 6268.21) (<Entity name: 10fd1674320>))
'((1481.42 6030.51) (1283.66 6030.51) (<Entity name: 10fd16740b0>))
'((1876.94 6030.51) (1679.18 6030.51) (<Entity name: 10fd1674090>))
'((1580.3 6129.39) (1778.06 6129.39) (<Entity name: 10fd1674080>))
'((1382.54 6129.39) (1580.3 6129.39) (<Entity name: 10fd1674070>))))

(setq fz 1e-8) ;Point comparison tolerance
(setq connectedPolyList (list))
(setq connectedPolyList (cons initialPolyEnt connectedPolyList)
      sameLayerPolyList (vl-remove initialPolyEnt sameLayerPolyList)
      connectedCounter 0
      chainLoop T)
(while chainLoop
 (if (< connectedCounter (length connectedPolyList))
  (progn
   (setq polyEndpoints (list (car (nth connectedCounter connectedPolyList))
                             (cadr (nth connectedCounter connectedPolyList))))
   ;Check the start point and end point of the polyline with all the others
   (foreach poly sameLayerPolyList
    (if (or (or (or (equal (car poly) (car polyEndpoints) fz) (equal (car poly) (cadr polyEndpoints) fz))
                (equal (cadr poly) (car polyEndpoints) fz))
            (equal (cadr poly) (cadr polyEndpoints) fz))
     ;If there are any endpoints that match, add those polylines to a new list and remove from the original
     (setq connectedPolyList (append connectedPolyList (list poly))
           sameLayerPolyList (vl-remove poly sameLayerPolyList))
    )
   )
   (setq connectedCounter (+ connectedCounter 1))
   (if (>= connectedCounter (length connectedPolyList)) (setq chainLoop nil))
  )
 )
)

connectedPolyList is the list of all the polylines that have touching endpoints.

 It ends up looking like this:

'(((1382.54 6129.39) (1580.3 6129.39) (<Entity name: 10fd1674070>))
'((1580.3 6129.39) (1677.03 6268.21) (<Entity name: 10fd1674540>))
'((1580.3 6129.39) (1778.06 6129.39) (<Entity name: 10fd1674080>))
'((1677.03 6268.21) (1803.8 6474.93) (<Entity name: 10fd16a6070>))
'((1677.03 6268.21) (1549.45 6390.17) (<Entity name: 10fd16745a0>))
'((1778.06 6129.39) (1874.79 6268.21) (<Entity name: 10fd1674320>)))