Intersection Line & Rectangle

Here's one that is proving to be a bit tougher than I initailly thought it to be:

In plain autolisp ( no vl, vla, vlax, vlaxr.....)

Does the red line intersect inside the yellow rectangle

Given:

The 4 points of the yellow rectangle are always coplaner

The 4 points always form a rectangle

The rectangle is not always WCS

The red line is always predindicular to the the yellow plane

return nil if the red line is:

outside the rectangle

totally above the rectangle

totally below the rectangle

Return T if the any part ( 3D ) of the red line intersects the plane

-David

A query ... is the rectangle's 4 corners always on the same plane? I.e. placing a UCS on 3 of them you can change the 4 lines into a single LW Polyline? If so this is merely difficult maths, if not it would become rocket science.

Notice the hint: use UCS to obtain new values for the 6 points through the trans function.

Yes, the yellow lines are always coplaner.

I don't see how an LWPOLYLINE would help....

I can make a UCS 3PT from the rectangle. I can then find the intersection of the translated line points with the current UCS, but it still doesn't tell the relationship to the rectangle.

Thanks! -David

This will return the intersection between the Line and the Plane (should the line not be parallel to the plane):

;; Intersection between Line & Plane - Lee Mac 2011
;; Args: l1,l2    - points defining the Line
;;       p1,p2,p3 - points defining the Plane

(defun IntersLinePlane ( l1 l2 p1 p2 p3 / n v d )

 (setq n (unit (v^v (mapcar '- p3 p2) (mapcar '- p1 p2))))
 (setq v (unit (mapcar '- l2 l1)))

 (if (not (equal 0.0 (setq d (vxv n v)) 1e-)
   (mapcar '+ l1 (vxs v (/ (vxv (mapcar '- p1 l1) n) d)))
 )
)  

;; Vector Cross (Wedge) Product - Lee Mac 2010
;; Args: u,v - vectors in R^3

(defun v^v ( u v )
 (list
   (- (* (cadr u) (caddr v)) (* (cadr v) (caddr u)))
   (- (* (car  v) (caddr u)) (* (car  u) (caddr v)))
   (- (* (car  u) (cadr  v)) (* (car  v) (cadr  u)))
 )
)

;; Vector Norm - Lee Mac 2010
;; Args: v - vector in R^n

(defun norm ( v )
 (sqrt (apply '+ (mapcar '* v v)))
)

;; Unit Vector - Lee Mac 2010
;; Args: v - vector in R^n

(defun unit ( v )
 ( (lambda ( n ) (if (equal 0.0 n 1e-14) nil (vxs v (/ 1.0 n)))) (norm v))
)

;; Vector x Scalar - Lee Mac 2010
;; Args: v - vector in R^n, s - real scalar

(defun vxs ( v s )
 (mapcar '(lambda ( n ) (* n s)) v)
)

;; Vector Dot Product - Lee Mac 2010
;; Args: u,v - vectors in R^n

(defun vxv ( u v )
 (apply '+ (mapcar '* u v))
)

From there you just need to determine whether the returned point lies inside your rectangle in the plane...

Or here's a bit more of a convoluted method:

;;; rect = list containing 4 points (of a true rectangle drawn clock- or anti-clockwise),
;;;        1st, 2nd & 4th is used to obtain the UCS. 3rd is effectively ignored.
;;; line = list of 2 points
(defun line-rect-int-p (rect line / ptA ptB ptC ptD pt1 pt2 pt0 res dist distBelow distAbove)
 ;; Ensure the lists contain WCS points
 (setq rect (list (trans (car rect) 1 0) (trans (cadr rect) 1 0) (trans (caddr rect) 1 0) (trans (cadddr rect) 1 0))
       line (list (trans (car line) 1 0) (trans (cadr line) 1 0))
 )
 ;; Obtain the 6 points as translated to a UCS of the rectangle
 (command "_.UCS" "_None" (car rect) "_None" (cadr rect) "_None" (cadddr rect))
 (setq ptA (trans (car rect) 0 1)
       ptB (trans (cadr rect) 0 1)
       ptC (trans (caddr rect) 0 1)
       ptD (trans (cadddr rect) 0 1)
       pt1 (trans (car line) 0 1)
       pt2 (trans (cadr line) 0 1)
 )
 (command "_.UCS" "_Prev")

 ;; Check if line passes through the UCS
 (if (or (and (<= (caddr pt1)) (>= (caddr pt2)))
         (and (>= (caddr pt1)) (<= (caddr pt2)))
     )
   (progn
     ;; Calculate the line's point where it passes through the UCS
     (setq dist      (distance pt1 pt2)
           distBelow (min (caddr pt1) (caddr pt2))
           distAbove (max (caddr pt1) (caddr pt2))
     )
     (if (< (caddr pt1) (caddr pt2))
       (setq pt0 (list (+ (* (/ (car pt1) dist) distBelow) (* (/ (car pt2) dist) distAbove))
                       (+ (* (/ (cadr pt1) dist) distBelow) (* (/ (cadr pt2) dist) distAbove))
                       0.0
                 )
       )
       (setq pt0 (list (+ (* (/ (car pt1) dist) distAbove) (* (/ (car pt2) dist) distBelow))
                       (+ (* (/ (cadr pt1) dist) distAbove) (* (/ (cadr pt2) dist) distBelow))
                       0.0
                 )
       )
     )

     ;; Check if pt0 falls in the positive quadrant
     (if (and (>= (car pt0) 0.0) (>= (cadr pt0) 0.0))
       ;; Check if pt0 is not further than the length of the rectangle's 2 sides
       (or (and (<= (car pt0) (car ptB)) (<= (cadr pt0) (cadr ptD)))
           (and (<= (car pt0) (car ptD)) (<= (cadr pt0) (cadr ptB)))
       )
     )
   )
 )
)

My test code:

(line-rect-int-p (list (getpoint) (getpoint) (getpoint) (getpoint)) (list (getpoint) (getpoint)))

Updated my code to check for inside rectangle also:

;; Line In Rectangle - Lee Mac 2011
;; Args: l1,l2       - points defining the Line
;;       p1,p2,p3,p4 - points defining the Rectangle

(defun LineInRectangle-p ( l1 l2 p1 p2 p3 p4 / i )

 (and (setq i (IntersLinePlane l1 l2 p1 p2 p3))
   (
     (lambda ( points )
       (apply 'InsideRectangle-p
         (cons (car points)
           (mapcar
             (function
               (lambda ( op ) (apply 'mapcar (cons op (cdr points))))
             )
            '(min max)
           )
         )
       )
     )
     (
       (lambda ( norm )
         (mapcar
           (function
             (lambda ( p ) (trans p 0 norm))
           )
           (list i p1 p2 p3 p4)
         )
       )
       (unit (v^v (mapcar '- p3 p2) (mapcar '- p1 p2)))
     )
   )
 )
)

;; Point Inside Rectangle - Lee Mac 2011
;; Args: pt     - point to test
;;       ll, ur - lower-left & upper-right of rectangle

(defun InsideRectangle-p ( pt ll ur )
 (and (apply '< (mapcar 'car  (list ll pt ur)))
      (apply '< (mapcar 'cadr (list ll pt ur)))
 )
)

;; Intersection between Line & Plane - Lee Mac 2011
;; Args: l1,l2    - points defining the Line
;;       p1,p2,p3 - points defining the Plane

(defun IntersLinePlane ( l1 l2 p1 p2 p3 / n v d )

 (setq n (unit (v^v (mapcar '- p3 p2) (mapcar '- p1 p2))))
 (setq v (unit (mapcar '- l2 l1)))

 (if (not (equal 0.0 (setq d (vxv n v)) 1e-)
   (mapcar '+ l1 (vxs v (/ (vxv (mapcar '- p1 l1) n) d)))
 )
)  

;; Vector Cross (Wedge) Product - Lee Mac 2010
;; Args: u,v - vectors in R^3

(defun v^v ( u v )
 (list
   (- (* (cadr u) (caddr v)) (* (cadr v) (caddr u)))
   (- (* (car  v) (caddr u)) (* (car  u) (caddr v)))
   (- (* (car  u) (cadr  v)) (* (car  v) (cadr  u)))
 )
)

;; Vector Norm - Lee Mac 2010
;; Args: v - vector in R^n

(defun norm ( v )
 (sqrt (apply '+ (mapcar '* v v)))
)

;; Unit Vector - Lee Mac 2010
;; Args: v - vector in R^n

(defun unit ( v )
 ( (lambda ( n ) (if (equal 0.0 n 1e-14) nil (vxs v (/ 1.0 n)))) (norm v))
)

;; Vector x Scalar - Lee Mac 2010
;; Args: v - vector in R^n, s - real scalar

(defun vxs ( v s )
 (mapcar '(lambda ( n ) (* n s)) v)
)

;; Vector Dot Product - Lee Mac 2010
;; Args: u,v - vectors in R^n

(defun vxv ( u v )
 (apply '+ (mapcar '* u v))
)

Wow. Had to step out for a bit. I'll dig into these today Thanks! -David

Some simplifications ( mainly for me )

1. Set UCS to WCS
   
2. Make a UCS for any 3 WCS translated rectangle points
   
3. Translate WCS Line points to the current ( rectangle ) UCS
   
4. If the Line Z axis goes thru 0.0 then there is an intersection
   
5. If an intersection exists, if any angle from the intersection point to any corner of the rectangle is > pi, then the intersection point is outside the rectangle
   

I might go back to > test to see if the point is in the box. I'd have to test the translations more to be comfortable with it.

irneb, we are convoluted in a similar method.

Lee, The math was a bit over my head.

Thanks -David

Lee, The math was a bit over my head.

Apologies, I should've commented it

Just for completeness, here is the outline to my method:

Plane can be described by:

[color=green](x - x0) · n = 0[/color]

Where [color=blue][color=green]x[/color] [/color]is any point in the plane, [color=green]x0[/color] is a fixed point in the plane and [color=green]n[/color] is the plane normal.

Just using the fact that any vector in the plane will be perpendicular to the plane normal 
=> Dot product between those vectors = 0

Line can be decribed by:

[color=green]y = y0 + vt[/color]

Where [color=green]y [/color]is a point on the line, [color=green]y0[/color] is a fixed point on the line, [color=green]v [color=black]is the direction vector of the line, and[/color] t[/color] is the parameter, 

For intersection we want [color=green]x = y[/color], hence:

[color=green](y0 + vt - x0) · n = 0

[color=black]Dot product is distributive, so:

[color=green]vt [/color][/color][/color][color=green]· n + (y0 - x0) [/color][color=green]· n = 0

[color=black]Finally, rearranging for our parameter [color=green]t:

t = (y0 - x0) [/color][/color][/color][color=green]· n  /  v [/color][color=green]· n

[color=black]If the line is parallel to the plane, its direction vector will be
perpendicular to the plane normal, and hence 

[/color][/color][color=green]v [/color][color=green]· n = 0

[color=black]So we test for that before performing the division.
[/color][/color]

Hope this clarifies things better.

Lee,

Thanks for the description. You're a lot further along in school than I made it or ever wanted to.

I'm getting a false positive:

(prin1
 (LineInRectangle-p '(14 4 5) '(25 4 5) '(2 2 4) '(2 10 4) '(2 10 14) '(2 2 14))
 )

-David

I'm getting a false positive...

Ah yes, my current code assumes an infinite line -

I've updated the code to add an 'onseg' argument to my IntersLinePlane function:

;; Line In Rectangle - Lee Mac 2011
;; Args: l1,l2       - points defining the Line
;;       p1,p2,p3,p4 - points defining the Rectangle

(defun LineInRectangle-p ( l1 l2 p1 p2 p3 p4 / i )

 (and (setq i (IntersLinePlane l1 l2 p1 p2 p3 T))
   (
     (lambda ( points )
       (apply 'InsideRectangle-p
         (cons (car points)
           (mapcar
             (function
               (lambda ( op ) (apply 'mapcar (cons op (cdr points))))
             )
            '(min max)
           )
         )
       )
     )
     (
       (lambda ( norm )
         (mapcar
           (function
             (lambda ( p ) (trans p 0 norm))
           )
           (list i p1 p2 p3 p4)
         )
       )
       (unit (v^v (mapcar '- p3 p2) (mapcar '- p1 p2)))
     )
   )
 )
)

;; Point Inside Rectangle - Lee Mac 2011
;; Args: pt     - point to test
;;       ll, ur - lower-left & upper-right of rectangle

(defun InsideRectangle-p ( pt ll ur )
 (and (apply '< (mapcar 'car  (list ll pt ur)))
      (apply '< (mapcar 'cadr (list ll pt ur)))
 )
)

;; Intersection between Line & Plane - Lee Mac 2011
;; Args: l1,l2    - points defining the Line
;;       p1,p2,p3 - points defining the Plane
;;       onseg    - if nil, lines are considered infinite in length

(defun IntersLinePlane ( l1 l2 p1 p2 p3 onseg / n v d )

 (setq n (unit (v^v (mapcar '- p3 p2) (mapcar '- p1 p2))))
 (setq v (unit (mapcar '- l2 l1)))

 (if (not (equal 0.0 (setq d (vxv n v)) 1e-)
   (if onseg
     (if (< 0.0 (setq d (/ (vxv (mapcar '- p1 l1) n) d)) (norm (mapcar '- l2 l1)))
       (mapcar '+ l1 (vxs v d))
     )
     (mapcar '+ l1 (vxs v d))
   )
 )
)  

 
;; Vector Cross (Wedge) Product - Lee Mac 2010
;; Args: u,v - vectors in R^3

(defun v^v ( u v )
 (list
   (- (* (cadr u) (caddr v)) (* (cadr v) (caddr u)))
   (- (* (car  v) (caddr u)) (* (car  u) (caddr v)))
   (- (* (car  u) (cadr  v)) (* (car  v) (cadr  u)))
 )
)

;; Vector Norm - Lee Mac 2010
;; Args: v - vector in R^n

(defun norm ( v )
 (sqrt (apply '+ (mapcar '* v v)))
)

;; Unit Vector - Lee Mac 2010
;; Args: v - vector in R^n

(defun unit ( v )
 ( (lambda ( n ) (if (equal 0.0 n 1e-14) nil (vxs v (/ 1.0 n)))) (norm v))
)

;; Vector x Scalar - Lee Mac 2010
;; Args: v - vector in R^n, s - real scalar

(defun vxs ( v s )
 (mapcar '(lambda ( n ) (* n s)) v)
)

;; Vector Dot Product - Lee Mac 2010
;; Args: u,v - vectors in R^n

(defun vxv ( u v )
 (apply '+ (mapcar '* u v))
)