Author Topic: Shortest way o test if 2 ranges overlap.  (Read 215 times)

0 Members and 1 Guest are viewing this topic.

Red Nova

• Newt
• Posts: 34
Shortest way o test if 2 ranges overlap.
« on: November 08, 2017, 07:46:58 am »
Hi. I have 2 lists of ranges represented by pairs of numbers. What is the shortest way to test if any of ranges from list1 overlap with any of ranges of list2?

This is what I have now.

Code - Auto/Visual Lisp: [Select]
`(defun c:test ( / lst1 lst2 CollisionMarker)  (setq lst1 '((12.0767 18.0747) (36.0767 42.0747) (60.0767 66.0747) (84.0767 90.0747) (108.077 114.075) (132.077 138.075))	lst2 '((13.9835 17.9835) (22.3731 26.3731) (49.7626 53.7626) (55.6846 59.6846) (68.5158 72.5158) (101.334 105.334) (108.49 112.49) (123.048 127.048) (138.593 142.593)))  (CheckOverlap lst1 lst2)  );defun (defun CheckOverlap (lst1 lst2 / lst1Length lst2Length)  (setq lst2Length (length lst2))  (foreach n lst1    (progn      (setq i 0)      (while (< i lst2Length)	(if	  (or	    (and	      (> (car n) (car (nth i lst2)))	      (< (car n) (cadr (nth i lst2))))	    (and	      (> (cadr n) (car (nth i lst2)))	      (< (cadr n) (cadr (nth i lst2))))	    );or	  (setq CollisionMarker t)	  );if	(setq i (+ 1 i))	);while      );progn    );foreach  (setq lst1Length (length lst1))  (foreach n lst2    (progn      (setq i 0)      (while (< i lst1Length)	(if	  (or	    (and	      (> (car n) (car (nth i lst1)))	      (< (car n) (cadr (nth i lst1))))	    (and	      (> (cadr n) (car (nth i lst1)))	      (< (cadr n) (cadr (nth i lst1))))	    );or	  (setq CollisionMarker t)	  );if	(setq i (+ 1 i))	);while      );progn    );foreach  );defun`
« Last Edit: November 08, 2017, 09:46:18 am by Red Nova »

David Bethel

• Swamp Rat
• Posts: 617
Re: Shortest way o test if 2 ranges overlap.
« Reply #1 on: November 08, 2017, 10:21:27 am »
I think I understand your querry:

Code - Auto/Visual Lisp: [Select]
`(defun c:olap (/ lst1 lst2 rl)  (setq lst1 '((12.0767 18.0747) (36.0767 42.0747) (60.0767 66.0747) (84.0767 90.0747) (108.077 114.075) (132.077 138.075))	lst2 '((13.9835 17.9835) (22.3731 26.3731) (49.7626 53.7626) (55.6846 59.6846) (68.5158 72.5158) (101.334 105.334) (108.49 112.49) (123.048 127.048) (138.593 142.593)))  (foreach l1 lst1    (foreach l2 lst2      (cond ((and (< (car  l1) (car  l2))                  (> (cadr l1) (cadr l2)))             (setq rl (cons (list l1 l2) rl))))))  (prin1 rl)  (prin1))`

This would be very slow on large lists.

-David
R12 Dos - A2K

Lee Mac

• Seagull
• Posts: 11831
• AutoCAD 2015 Windows 7 London, England
Re: Shortest way o test if 2 ranges overlap.
« Reply #2 on: November 08, 2017, 01:05:38 pm »
Assuming you want a boolean return:

Code - Auto/Visual Lisp: [Select]
`(defun rnglap-p ( ls1 ls2 )    (        (lambda ( a b )            (vl-some                (function                    (lambda ( c )                        (vl-some                            (function                                (lambda ( d )                                    (vl-some                                        (function                                            (lambda ( e f )                                                (vl-some                                                    (function                                                        (lambda ( g )                                                            (< (car f) g (cadr f))                                                        )                                                    )                                                    e                                                )                                            )                                        )                                        (list c d) (list d c)                                    )                                )                            )                            b                        )                    )                )                a            )        )        ls1 (vl-sort ls2 '(lambda ( a b ) (< (car a) (car b))))    ))`

Grrr1337

• Bull Frog
• Posts: 416
Re: Shortest way o test if 2 ranges overlap.
« Reply #3 on: November 08, 2017, 03:34:05 pm »
Heres a recursive one - the return will be grouped ranges that intersect:

Code - Auto/Visual Lisp: [Select]
`(RangeInters nil  '((12.0767 18.0747) (36.0767 42.0747) (60.0767 66.0747) (84.0767 90.0747) (108.077 114.075) (132.077 138.075))  '((13.9835 17.9835) (22.3731 26.3731) (49.7626 53.7626) (55.6846 59.6846) (68.5158 72.5158) (101.334 105.334) (108.49 112.49) (123.048 127.048) (138.593 142.593)))>> (((13.9835 17.9835) (12.0767 18.0747)) ((108.49 112.49) (108.077 114.075))) ; Return like David Bethel's`

Code - Auto/Visual Lisp: [Select]
`(defun RangeInters ( onseg L1 L2 / rec UniqueOut )   (defun rec ( L1 L2 f / tmp )    (cond  ( (not L1) L1) ( (not L2) L2)      (        (append          (cond             ( (vl-some '(lambda (x) (if (f (car x) (caar L1) (cadr x)) (list (list (car L1) x)))) L2) )            ( (vl-some '(lambda (x) (if (f (car x) (cadar L1) (cadr x)) (list (list (car L1) x)))) L2) )          )          (cond             ( (vl-some '(lambda (x) (if (f (car x) (caar L2) (cadr x)) (list (list (car L2) x)))) L1) )            ( (vl-some '(lambda (x) (if (f (car x) (cadar L2) (cadr x)) (list (list (car L2) x)))) L1) )          )          (rec (cdr L1) L2 f)          (rec (cdr L2) L1 f)        )      )    )  )   (defun UniqueOut ( L fuzz / a )    (cond       ( (not L) L)      (        (append (list (setq a (car L)))          (UniqueOut (apply 'append (mapcar '(lambda (x) (if (and (not (equal a x fuzz)) (not (equal (reverse a) x fuzz))) (list x))) L)) fuzz)        )      )    )  )  (UniqueOut     (rec       (vl-sort L1 '(lambda (a b) (< (car a) (car b))))      (vl-sort L2 '(lambda (a b) (< (car a) (car b))))      (if onseg <= <)    )     1e-4  )); defun RangeInters `

Simple tests/examples:

Code - Auto/Visual Lisp: [Select]
`(RangeInters T ; <- because of this flag  '((10 20)(20 30)(30 40)(50 60))  '((90 100)(80 90)(10 0)) ; (10 0) will intersect)>> (((10 0) (10 20))) (RangeInters nil ; <- because of this flag  '((10 20)(20 30)(30 40)(50 60))  '((90 100)(80 90)(10 0)) ; (10 0) will NOT intersect)>> nil (RangeInters nil  '((10 20)(20 30)(30 40)(50 60))  '((90 100)(80 90)) ; no intersection)>> nil (RangeInters nil  '((10 20)(20 30)(30 40)(50 60))  '((90 100)(80 90)(15 25)) ; only (15 25) will intersect the above list)>> (((10 20) (15 25)) ((20 30) (15 25))) (RangeInters nil  '((10 20)(20 30)(30 40)(50 60))  '((90 100)(80 90)(15 25)(39 51)) ; (15 25) and (39 51) will intersect the above list)>> (((10 20) (15 25)) ((20 30) (15 25)) ((30 40) (39 51)) ((50 60) (39 51))) (RangeInters nil  '((10 20)(20 30)(30 40)(50 60))  '((90 100)(80 90)(15 25)(41 51)) ; (15 25) and (41 51) will intersect the above list)>> (((10 20) (15 25)) ((20 30) (15 25)) ((50 60) (41 51))) `

Probably not the most effective code, but it was fun to write.

Red Nova

• Newt
• Posts: 34
Re: Shortest way o test if 2 ranges overlap.
« Reply #4 on: November 08, 2017, 03:55:12 pm »
Thank you gens.

Didn't test it yet, will do. By the way, is there actually a way to get a report in vlide about how many operations it takes for a cod to complete? I mean just to have a way to compare speed of two similar codes like these ones? Need to analyze very long lists of ranges so going for speed.

Grrr1337

• Bull Frog
• Posts: 416
Re: Shortest way o test if 2 ranges overlap.
« Reply #5 on: November 08, 2017, 04:21:48 pm »
Just two more:

Code - Auto/Visual Lisp: [Select]
`; returns boole if there are grouped ranges that intersect(defun RangeOverlap-p ( L1 L2 / r )  (mapcar 'set '(L1 L2) (mapcar (function (lambda (L) (vl-sort L (function (lambda (a b) (< (car a) (car b))))))) (list L1 L2)))  (while (and (not r) L1)    (while (and (not r) L2)            (and (< (caar L1) (caar L2)) (> (cadar L1) (cadar L2)) (setq r T))      (setq L2 (cdr L2))    )    (setq L1 (cdr L1))  )  r) ; returns grouped ranges that intersect(defun RangeOverlap ( L1 L2 / r )  (mapcar 'set '(L1 L2) (mapcar (function (lambda (L) (vl-sort L (function (lambda (a b) (< (car a) (car b))))))) (list L1 L2)))  (foreach a L1    (foreach b L2      (and (< (car a) (car b)) (> (cadr a) (cadr b)) (setq r (cons (list a b) r)))    )  )  r)`

Second one is similar to David's,  but the initial sorting of the lists might help for a faster performance.

Lee Mac

• Seagull
• Posts: 11831
• AutoCAD 2015 Windows 7 London, England
Re: Shortest way o test if 2 ranges overlap.
« Reply #6 on: November 08, 2017, 06:44:05 pm »
@Grrr1337, David:

Code: [Select]
`_\$ (RangeOverlap '((1.0 2.0)(3.0 4.0)(5.0 6.0)) '((0.5 1.5)(2.5 3.5)(4.5 5.5)))nil_\$ (RangeOverlap-p '((1.0 2.0)(3.0 4.0)(5.0 6.0)) '((0.5 1.5)(2.5 3.5)(4.5 5.5)))nil`
Code: [Select]
`_\$ (defun c:olap (/ lst1 lst2 rl)      (setq lst1 '((1.0 2.0)(3.0 4.0)(5.0 6.0))            lst2 '((0.5 1.5)(2.5 3.5)(4.5 5.5)))      (foreach l1 lst1        (foreach l2 lst2          (cond ((and (< (car  l1) (car  l2))                      (> (cadr l1) (cadr l2)))                 (setq rl (cons (list l1 l2) rl))))))      (prin1 rl)      (prin1))C:OLAP_\$ (c:olap)nil`
Code: [Select]
`_\$ (rnglap-p '((1.0 2.0)(3.0 4.0)(5.0 6.0)) '((0.5 1.5)(2.5 3.5)(4.5 5.5)))T`
« Last Edit: November 08, 2017, 07:02:28 pm by Lee Mac »

Lee Mac

• Seagull
• Posts: 11831
• AutoCAD 2015 Windows 7 London, England
Re: Shortest way o test if 2 ranges overlap.
« Reply #7 on: November 08, 2017, 06:52:40 pm »
To return the overlaps:
Code - Auto/Visual Lisp: [Select]
`(defun rnglap ( ls1 ls2 )    (        (lambda ( a b )            (vl-remove nil                (apply 'append                    (mapcar                        (function                            (lambda ( c )                                (mapcar                                    (function                                        (lambda ( d )                                            (if                                                (vl-some                                                    (function                                                        (lambda ( e f )                                                            (vl-some                                                                (function                                                                    (lambda ( g )                                                                        (< (car f) g (cadr f))                                                                    )                                                                )                                                                e                                                            )                                                        )                                                    )                                                    (list c d) (list d c)                                                )                                                (list c d)                                            )                                        )                                    )                                    b                                )                            )                        )                        a                    )                )            )        )        ls1 (vl-sort ls2 '(lambda ( a b ) (< (car a) (car b))))    ))`

Code - Auto/Visual Lisp: [Select]
`_\$ (rnglap '((1.0 2.0)(3.0 4.0)(5.0 6.0)) '((0.5 1.5)(2.5 3.5)(4.5 5.5)))(((1.0 2.0) (0.5 1.5)) ((3.0 4.0) (2.5 3.5)) ((5.0 6.0) (4.5 5.5)))`

Lee Mac

• Seagull
• Posts: 11831
• AutoCAD 2015 Windows 7 London, England
Re: Shortest way o test if 2 ranges overlap.
« Reply #8 on: November 08, 2017, 07:04:47 pm »
Actually, I think this should suffice:
Code - Auto/Visual Lisp: [Select]
`(defun rnglap-p ( ls1 ls2 )    (vl-some '(lambda ( a ) (vl-some '(lambda ( b ) (and (< (car b) (cadr a)) (< (car a) (cadr b)))) ls2)) ls1))`
Code - Auto/Visual Lisp: [Select]
`(defun rnglap ( ls1 ls2 )    (vl-remove nil (apply 'append (mapcar '(lambda ( a ) (mapcar '(lambda ( b ) (if (and (< (car b) (cadr a)) (< (car a) (cadr b))) (list a b))) ls2)) ls1))))`

Grrr1337

• Bull Frog
• Posts: 416
Re: Shortest way o test if 2 ranges overlap.
« Reply #9 on: November 08, 2017, 07:33:21 pm »
@Grrr1337, David:

Code: [Select]
`_\$ (RangeOverlap '((1.0 2.0)(3.0 4.0)(5.0 6.0)) '((0.5 1.5)(2.5 3.5)(4.5 5.5)))nil_\$ (RangeOverlap-p '((1.0 2.0)(3.0 4.0)(5.0 6.0)) '((0.5 1.5)(2.5 3.5)(4.5 5.5)))nil`

Thanks Lee, I felt there was something wrong.. <duh>

Red Nova

• Newt
• Posts: 34
Re: Shortest way o test if 2 ranges overlap.
« Reply #10 on: November 08, 2017, 08:11:25 pm »
Actually, I think this should suffice:
Code - Auto/Visual Lisp: [Select]
`(defun rnglap-p ( ls1 ls2 )    (vl-some '(lambda ( a ) (vl-some '(lambda ( b ) (and (< (car b) (cadr a)) (< (car a) (cadr b)))) ls2)) ls1))`
Code - Auto/Visual Lisp: [Select]
`(defun rnglap ( ls1 ls2 )    (vl-remove nil (apply 'append (mapcar '(lambda ( a ) (mapcar '(lambda ( b ) (if (and (< (car b) (cadr a)) (< (car a) (cadr b))) (list a b))) ls2)) ls1))))`

Thanks Lee Mac. I believe that is the shortest.

David Bethel

• Swamp Rat
• Posts: 617
Re: Shortest way o test if 2 ranges overlap.
« Reply #11 on: November 09, 2017, 04:57:51 am »
Maybe I don't understand the OP definition of 'overlapping'

Are the comparison values :
Partially / Completlly / Exactly /
within the boundaries of the base values ?

-David
R12 Dos - A2K

Lee Mac

• Seagull
• Posts: 11831
• AutoCAD 2015 Windows 7 London, England
Re: Shortest way o test if 2 ranges overlap.
« Reply #12 on: November 09, 2017, 07:52:41 am »
Actually, I think this should suffice:
Code - Auto/Visual Lisp: [Select]
`(defun rnglap-p ( ls1 ls2 )    (vl-some '(lambda ( a ) (vl-some '(lambda ( b ) (and (< (car b) (cadr a)) (< (car a) (cadr b)))) ls2)) ls1))`
Code - Auto/Visual Lisp: [Select]
`(defun rnglap ( ls1 ls2 )    (vl-remove nil (apply 'append (mapcar '(lambda ( a ) (mapcar '(lambda ( b ) (if (and (< (car b) (cadr a)) (< (car a) (cadr b))) (list a b))) ls2)) ls1))))`
Thanks Lee Mac. I believe that is the shortest.

You're welcome - please note that these functions make the assumption that each range has the lowest number appearing first.