Intersection Line & Rectangle

David Bethel · 发表于 2022-7-6 09:53:48

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

irneb · 发表于 2022-7-6 10:00:22

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.

David Bethel · 发表于 2022-7-6 10:10:34

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

Lee Mac · 发表于 2022-7-6 10:15:15

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

copy

;; 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...

irneb · 发表于 2022-7-6 10:20:41

Or here's a bit more of a convoluted method:
[code];;; 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 pt2))) (and (>= (caddr pt1)) (

Lee Mac · 发表于 2022-7-6 10:24:03

Updated my code to check for inside rectangle also:

copy

;; 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)))

David Bethel · 发表于 2022-7-6 10:34:48

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

David Bethel · 发表于 2022-7-6 10:41:01

Some simplifications ( mainly for me )

Set UCS to WCS
Make a UCS for any 3 WCS translated rectangle points
Translate WCS Line points to the current ( rectangle ) UCS
If the Line Z axis goes thru 0.0 then there is an intersection
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 Mac · 发表于 2022-7-6 10:47:28

Apologies, I should've commented it

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

copy

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 = 0Line 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 beperpendicular 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.

David Bethel · 发表于 2022-7-6 10:52:10

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:

copy

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

-David

[编程交流] Intersection Line & Rectangle

发表回复

精选推荐