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

0 Members and 1 Guest are viewing this topic.

Red Nova

  • Newt
  • Posts: 69
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]
  1. (defun c:test ( / lst1 lst2 CollisionMarker)
  2.   (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))
  3.         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)))
  4.   (CheckOverlap lst1 lst2)
  5.   );defun
  6.  
  7. (defun CheckOverlap (lst1 lst2 / lst1Length lst2Length)
  8.   (setq lst2Length (length lst2))
  9.   (foreach n lst1
  10.     (progn
  11.       (setq i 0)
  12.       (while (< i lst2Length)
  13.         (if
  14.           (or
  15.             (and
  16.               (> (car n) (car (nth i lst2)))
  17.               (< (car n) (cadr (nth i lst2))))
  18.             (and
  19.               (> (cadr n) (car (nth i lst2)))
  20.               (< (cadr n) (cadr (nth i lst2))))
  21.             );or
  22.           (setq CollisionMarker t)
  23.           );if
  24.         (setq i (+ 1 i))
  25.         );while
  26.       );progn
  27.     );foreach
  28.   (setq lst1Length (length lst1))
  29.   (foreach n lst2
  30.     (progn
  31.       (setq i 0)
  32.       (while (< i lst1Length)
  33.         (if
  34.           (or
  35.             (and
  36.               (> (car n) (car (nth i lst1)))
  37.               (< (car n) (cadr (nth i lst1))))
  38.             (and
  39.               (> (cadr n) (car (nth i lst1)))
  40.               (< (cadr n) (cadr (nth i lst1))))
  41.             );or
  42.           (setq CollisionMarker t)
  43.           );if
  44.         (setq i (+ 1 i))
  45.         );while
  46.       );progn
  47.     );foreach
  48.   );defun
« Last Edit: November 08, 2017, 09:46:18 AM by Red Nova »

David Bethel

  • Swamp Rat
  • Posts: 656
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]
  1. (defun c:olap (/ lst1 lst2 rl)
  2.   (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))
  3.         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)))
  4.   (foreach l1 lst1
  5.     (foreach l2 lst2
  6.       (cond ((and (< (car  l1) (car  l2))
  7.                   (> (cadr l1) (cadr l2)))
  8.              (setq rl (cons (list l1 l2) rl))))))
  9.   (prin1 rl)
  10.   (prin1))


This would be very slow on large lists.

-David
R12 Dos - A2K

Lee Mac

  • Seagull
  • Posts: 12905
  • 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]
  1. (defun rnglap-p ( ls1 ls2 )
  2.     (
  3.         (lambda ( a b )
  4.             (vl-some
  5.                 (function
  6.                     (lambda ( c )
  7.                         (vl-some
  8.                             (function
  9.                                 (lambda ( d )
  10.                                     (vl-some
  11.                                         (function
  12.                                             (lambda ( e f )
  13.                                                 (vl-some
  14.                                                     (function
  15.                                                         (lambda ( g )
  16.                                                             (< (car f) g (cadr f))
  17.                                                         )
  18.                                                     )
  19.                                                     e
  20.                                                 )
  21.                                             )
  22.                                         )
  23.                                         (list c d) (list d c)
  24.                                     )
  25.                                 )
  26.                             )
  27.                             b
  28.                         )
  29.                     )
  30.                 )
  31.                 a
  32.             )
  33.         )
  34.         ls1 (vl-sort ls2 '(lambda ( a b ) (< (car a) (car b))))
  35.     )
  36. )

Grrr1337

  • Swamp Rat
  • Posts: 812
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]
  1. (RangeInters nil
  2.   '((12.0767 18.0747) (36.0767 42.0747) (60.0767 66.0747) (84.0767 90.0747) (108.077 114.075) (132.077 138.075))
  3.   '((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))
  4. )
  5. >> (((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]
  1. (defun RangeInters ( onseg L1 L2 / rec UniqueOut )
  2.  
  3.   (defun rec ( L1 L2 f / tmp )
  4.     (cond  ( (not L1) L1) ( (not L2) L2)
  5.       (
  6.         (append
  7.           (cond
  8.             ( (vl-some '(lambda (x) (if (f (car x) (caar L1) (cadr x)) (list (list (car L1) x)))) L2) )
  9.             ( (vl-some '(lambda (x) (if (f (car x) (cadar L1) (cadr x)) (list (list (car L1) x)))) L2) )
  10.           )
  11.           (cond
  12.             ( (vl-some '(lambda (x) (if (f (car x) (caar L2) (cadr x)) (list (list (car L2) x)))) L1) )
  13.             ( (vl-some '(lambda (x) (if (f (car x) (cadar L2) (cadr x)) (list (list (car L2) x)))) L1) )
  14.           )
  15.           (rec (cdr L1) L2 f)
  16.           (rec (cdr L2) L1 f)
  17.         )
  18.       )
  19.     )
  20.   )
  21.  
  22.   (defun UniqueOut ( L fuzz / a )
  23.     (cond
  24.       ( (not L) L)
  25.       (
  26.         (append (list (setq a (car L)))
  27.           (UniqueOut (apply 'append (mapcar '(lambda (x) (if (and (not (equal a x fuzz)) (not (equal (reverse a) x fuzz))) (list x))) L)) fuzz)
  28.         )
  29.       )
  30.     )
  31.   )
  32.   (UniqueOut
  33.     (rec
  34.       (vl-sort L1 '(lambda (a b) (< (car a) (car b))))
  35.       (vl-sort L2 '(lambda (a b) (< (car a) (car b))))
  36.       (if onseg <= <)
  37.     )
  38.     1e-4
  39.   )
  40. ); defun RangeInters

Simple tests/examples:

Code - Auto/Visual Lisp: [Select]
  1. (RangeInters T ; <- because of this flag
  2.   '((10 20)(20 30)(30 40)(50 60))
  3.   '((90 100)(80 90)(10 0)) ; (10 0) will intersect
  4. )
  5. >> (((10 0) (10 20)))
  6.  
  7. (RangeInters nil ; <- because of this flag
  8.   '((10 20)(20 30)(30 40)(50 60))
  9.   '((90 100)(80 90)(10 0)) ; (10 0) will NOT intersect
  10. )
  11. >> nil
  12.  
  13. (RangeInters nil
  14.   '((10 20)(20 30)(30 40)(50 60))
  15.   '((90 100)(80 90)) ; no intersection
  16. )
  17. >> nil
  18.  
  19. (RangeInters nil
  20.   '((10 20)(20 30)(30 40)(50 60))
  21.   '((90 100)(80 90)(15 25)) ; only (15 25) will intersect the above list
  22. )
  23. >> (((10 20) (15 25)) ((20 30) (15 25)))
  24.  
  25. (RangeInters nil
  26.   '((10 20)(20 30)(30 40)(50 60))
  27.   '((90 100)(80 90)(15 25)(39 51)) ; (15 25) and (39 51) will intersect the above list
  28. )
  29. >> (((10 20) (15 25)) ((20 30) (15 25)) ((30 40) (39 51)) ((50 60) (39 51)))
  30.  
  31. (RangeInters nil
  32.   '((10 20)(20 30)(30 40)(50 60))
  33.   '((90 100)(80 90)(15 25)(41 51)) ; (15 25) and (41 51) will intersect the above list
  34. )
  35. >> (((10 20) (15 25)) ((20 30) (15 25)) ((50 60) (41 51)))
  36.  

Probably not the most effective code, but it was fun to write.
(apply ''((a b c)(a b c))
  '(
    (( f L ) (apply 'strcat (f L)))
    (( L ) (if L (cons (chr (car L)) (f (cdr L)))))
    (72 101 108 108 111 32 87 111 114 108 100)
  )
)
vevo.bg

Red Nova

  • Newt
  • Posts: 69
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

  • Swamp Rat
  • Posts: 812
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]
  1. ; returns boole if there are grouped ranges that intersect
  2. (defun RangeOverlap-p ( L1 L2 / r )
  3.   (mapcar 'set '(L1 L2) (mapcar (function (lambda (L) (vl-sort L (function (lambda (a b) (< (car a) (car b))))))) (list L1 L2)))
  4.   (while (and (not r) L1)
  5.     (while (and (not r) L2)      
  6.       (and (< (caar L1) (caar L2)) (> (cadar L1) (cadar L2)) (setq r T))
  7.       (setq L2 (cdr L2))
  8.     )
  9.     (setq L1 (cdr L1))
  10.   )
  11.   r
  12. )
  13.  
  14. ; returns grouped ranges that intersect
  15. (defun RangeOverlap ( L1 L2 / r )
  16.   (mapcar 'set '(L1 L2) (mapcar (function (lambda (L) (vl-sort L (function (lambda (a b) (< (car a) (car b))))))) (list L1 L2)))
  17.   (foreach a L1
  18.     (foreach b L2
  19.       (and (< (car a) (car b)) (> (cadr a) (cadr b)) (setq r (cons (list a b) r)))
  20.     )
  21.   )
  22.   r
  23. )

Second one is similar to David's,  but the initial sorting of the lists might help for a faster performance.  :rolleyes2:
(apply ''((a b c)(a b c))
  '(
    (( f L ) (apply 'strcat (f L)))
    (( L ) (if L (cons (chr (car L)) (f (cdr L)))))
    (72 101 108 108 111 32 87 111 114 108 100)
  )
)
vevo.bg

Lee Mac

  • Seagull
  • Posts: 12905
  • 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: 12905
  • 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]
  1. (defun rnglap ( ls1 ls2 )
  2.     (
  3.         (lambda ( a b )
  4.             (vl-remove nil
  5.                 (apply 'append
  6.                     (mapcar
  7.                         (function
  8.                             (lambda ( c )
  9.                                 (mapcar
  10.                                     (function
  11.                                         (lambda ( d )
  12.                                             (if
  13.                                                 (vl-some
  14.                                                     (function
  15.                                                         (lambda ( e f )
  16.                                                             (vl-some
  17.                                                                 (function
  18.                                                                     (lambda ( g )
  19.                                                                         (< (car f) g (cadr f))
  20.                                                                     )
  21.                                                                 )
  22.                                                                 e
  23.                                                             )
  24.                                                         )
  25.                                                     )
  26.                                                     (list c d) (list d c)
  27.                                                 )
  28.                                                 (list c d)
  29.                                             )
  30.                                         )
  31.                                     )
  32.                                     b
  33.                                 )
  34.                             )
  35.                         )
  36.                         a
  37.                     )
  38.                 )
  39.             )
  40.         )
  41.         ls1 (vl-sort ls2 '(lambda ( a b ) (< (car a) (car b))))
  42.     )
  43. )

Code - Auto/Visual Lisp: [Select]
  1. _$ (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)))
  2. (((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: 12905
  • 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]
  1. (defun rnglap-p ( ls1 ls2 )
  2.     (vl-some '(lambda ( a ) (vl-some '(lambda ( b ) (and (< (car b) (cadr a)) (< (car a) (cadr b)))) ls2)) ls1)
  3. )
Code - Auto/Visual Lisp: [Select]
  1. (defun rnglap ( ls1 ls2 )
  2.     (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)))
  3. )

Grrr1337

  • Swamp Rat
  • Posts: 812
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>
(apply ''((a b c)(a b c))
  '(
    (( f L ) (apply 'strcat (f L)))
    (( L ) (if L (cons (chr (car L)) (f (cdr L)))))
    (72 101 108 108 111 32 87 111 114 108 100)
  )
)
vevo.bg

Red Nova

  • Newt
  • Posts: 69
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]
  1. (defun rnglap-p ( ls1 ls2 )
  2.     (vl-some '(lambda ( a ) (vl-some '(lambda ( b ) (and (< (car b) (cadr a)) (< (car a) (cadr b)))) ls2)) ls1)
  3. )
Code - Auto/Visual Lisp: [Select]
  1. (defun rnglap ( ls1 ls2 )
  2.     (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)))
  3. )

Thanks Lee Mac. I believe that is the shortest.  :-)

David Bethel

  • Swamp Rat
  • Posts: 656
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: 12905
  • 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]
  1. (defun rnglap-p ( ls1 ls2 )
  2.     (vl-some '(lambda ( a ) (vl-some '(lambda ( b ) (and (< (car b) (cadr a)) (< (car a) (cadr b)))) ls2)) ls1)
  3. )
Code - Auto/Visual Lisp: [Select]
  1. (defun rnglap ( ls1 ls2 )
  2.     (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)))
  3. )
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.