Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!iuvax!ux1.cso.uiuc.edu!uxc.cso.uiuc.edu!uxc.cso.uiuc.edu!m.cs.uiuc.edu!s.cs.uiuc.edu!mccaugh
From: mccaugh@s.cs.uiuc.edu
Newsgroups: comp.graphics
Subject: Re: Intersection between a line and a p
Message-ID: <207400031@s.cs.uiuc.edu>
Date: 4 Oct 89 05:00:00 GMT
References: <2972@ndsuvax.UUCP>
Lines: 102
Nf-ID: #R:ndsuvax.UUCP:2972:s.cs.uiuc.edu:207400031:000:2914
Nf-From: s.cs.uiuc.edu!mccaugh    Oct  4 00:00:00 1989


>   I need to find a formula/algorithm to determine if a line intersects
>   a polygon.  I would perfer a method that would do this in as litte
>   time as possible.  I need this for use in a forward raytracing
>   program.
> 

 
   CONST  n = 20;  (* e.g. *)

    TYPE  line = RECORD
                    a,b,c: Real
                 END{line};

          vertex = RECORD
                      x,y: Real
                   END{vertex};

          side = RECORD
                    A,B: vertex
                 END{side};

          index = 1..n;

          polygon = ARRAY[index] OF side;


  FUNCTION  InSegment (VAR A,B,Q:vertex): Boolean;
            (* given that Q lies upon the line AB, *)
            (* determine if Q lies between A and B *)

       VAR p: Real;

     BEGIN
        IF  A.x <> B.x  THEN  p  :=  (Q.x - B.x)/(A.x - B.x) 
        ELSE  p  :=  (Q.y - B.y)/(A.y - B.y);
        InSegment  :=  (0.0<=p) AND (p<=1.0)
     END{InSegment};



 FUNCTION  Intersects: Boolean;  (* see if line L intersects extended side *)
      VAR  Q: vertex;  (* point of intersection *)

    BEGIN  (* if intersected, calls InSegment to see if point lies in side *)
       IF  b1 = 0.0  THEN
           IF  b2 = 0.0  THEN  Intersects  :=  a1*c2 = a2*c1
           ELSE BEGIN
                   WITH Q DO
                        BEGIN
                        x  :=  c1/a1;
                        y  :=  (c2 - a2*c1/a1)/b2
                        END;
                   Intersects := InSegment(A,B,Q)
                END
      ELSE IF  b2 = 0.0  THEN
               BEGIN
                  WITH Q DO
                       BEGIN
                       x  :=  c2/a2;
                       y  :=  (c1 - a1*c2/a2)/b1
                       END;
                  Intersects := InSegment(A,B,Q)
               END
           ELSE Intersects  :=  b2*c1 = b1*c2
   END{Intersects};



   FUNCTION  LineXPolygon (VAR L:line; VAR P:polygon): Boolean;
   (* returns TRUE if and only if line L intersects polygon P *)

        VAR  s: index;  (* index of current side of polygon P *)
             a1,b1,c1, (* coefficients of line L: normal form *)
             a2,b2,c2: Real; (* and of current side: "    "   *)

      BEGIN {LineXPolygon}

         WITH  L  DO  BEGIN
                      a1 := a;
                      b1 := b;
                      c1 := c
                      END{WITH};

         FOR  s  :=  1 TO n  DO
              BEGIN
                 WITH  P[s] DO
                       BEGIN
                       a2  :=  B.y - A.y;
                       b2  :=  A.x - B.x;
                       c2  :=  a2*B.x + b2*B.y
                       END{WITH};

                  IF  Intersects  THEN
                      BEGIN
                      LineXPolygon := True;
                      Exit
                      END
              END{FOR};

         LineXPolygon := False
      END{LineXPolygon};