Connecting the dots

[M76]

I'd like to connect two sets of points. There are always exactly the same number of points in each set.

 

The trick is how to avoid intersecting lines.

 

I think I need a recursive algorithm to find the solution when no lines intersect, but I never could think that way.

 

I'm not asking that somone else write the program for me, I just need hints on the recursive part, what to pass on as parameters and how to start processing, when to roll back.

[Lee Mac]

This looks like it could use a similar recursive backtracking method as I used in this 'challenge', replacing the predicate function with a function to test intersection between two sets of points (think 'inters').

 

Hope this helps.

[BlackBox]

[M76]

This looks like it could use a similar recursive backtracking method as I used in this 'challenge', replacing the predicate function with a function to test intersection between two sets of points (think 'inters').

 

Hope this helps.

 

 

Thanks, by the time I've seen your code I already started implementing my solution, the basic idea is the same, only my code is far less efficient and streamlined, but it seems to be working.

 

This is what I came up with:

 

(defun connect (paired plista plista2 / i j pa pb done ul s p1 p2)
   (setq done nil)
   (setq pa (cdar plista))
   (setq i 0)
   (if (= 0 (length plista2)) (setq done paired))
   (while (and (not done) (< i (length plista2)))
       
       (setq pb (nth i plista2))
       (setq ul (vl-remove (nth i plista2) plista2))
       
       (setq j 0)
       (setq s T)
       (repeat (length paired)
           (setq p1 (cadr (nth j paired)))
           (setq p2 (last (nth j paired)))
                     (if (inters p1 p2 pa pb) (setq s nil))
           (setq j (1+ j))
             
       )
       
       (if s 
           (setq done (connect (append paired (list (list (caar plista) (cdar plista) pb))) (cdr plista) ul ))
       
       )
       (setq i (1+ i))
       
       
       
   )
   (setq ret done)
)

The complications in the list handling is because I actually have a number attached to the points in "plista", and I need to keep those associations.

 

So plista looks like this: (("12881" 658886.0 231817.0 0.0) ("10388" 658885.0 231819.0 0.0) ("10387" 658885.0 231819.0 0.0))

 

and the result of the function is this with the points from plista2

 

(("12881" (658886.0 231817.0 0.0) (658889.0 231819.0 0.0)) ("10388" (658885.0 231819.0 0.0) (658889.0 231820.0 0.0)) ("10387" (658885.0 231819.0 0.0) (658889.0 231821.0 0.0)))