[comp.graphics] Common questions about polygons?

mk@vall.dsv.su.se (Magnus Karlson) (09/20/89)

Two probably common questions that i need help/information about...

1) If i have several lists containing x,y pairs, and i know that each
   list really should be a closed polygon, but arn't since the closing
   line/lines is defined in some other list. Is there some easy way
   to compleat each list to a closed polygon? The only way I see at first
   glance will take too long time given a large set of lists...

2) Given a dot (x,y pair) and a lot of closed polygons is there a way
   to know which polygon the dot is inside?


	Any help would be mush appreciated, and I would be glad to
	summarize if anyone is intrested.

	Magnus Karlson

mccaugh@s.cs.uiuc.edu (09/26/89)

 (*************************************************************)
 (*                                                           *)
 (* Assumptions:  n > 2  (at least 3 sides)                   *)
 (*               0 < k < n   (at least 1 side missing/given) *)
 (*               standard Cartesian-coordinate system        *)
 (*               all constructions proceed clockwise         *)
 (*                                                           *)
 (*                                                           *)
 (*                                                           *)
 (*   TYPE  vertex = RECORD                                   *)
 (*                     x,y: Real                             *)
 (*                  END{vertex};                             *)
 (*                                                           *)
 (*************************************************************)


 PROCEDURE  Polygon (n, { number of sides altogether };
                     k: { number of vertices to find }
                        Integer;
                     VAR Points: { sequence of vertices }
                         ARRAY[1..n] OF vertex;
                    );

 { generate missing vertices of regular convex n-gon from given ones }
 { at least one side (2 vertices) given,  and missing ones come last }

       VAR  a1,b1, a2,b2, x, u,v,x2,  
            m1,mj, s,mx, M, C, T, W: Real;
            i,j: Integer;

  
      FUNCTION  Sgn (z:Real): Real;
         BEGIN
            IF  z < 0.0  THEN  Sgn := -1.0
            ELSE IF  z > 0.0  THEN  Sgn := 1.0
                 ELSE  Sgn := 0.0
         END{Sgn};


     BEGIN{Polygon}
  
     i := n - k;
     a1 := Point[i].x;   b1 := Point[i].y;
     a2 := Point[i+1].x;   b2 := Point[i+1].y;
  
     IF  n = 4  THEN
         BEGIN
            IF  a1 = a2  THEN  x := Abs(b2-b1)
            ELSE  x := Abs(a2-a1);
            FOR  j := i TO 3  DO
                 BEGIN
                    IF  a1 = a2  THEN
                        BEGIN
                           u := a2 + Sgn(b2-b1)*x;
                           v := b2
                        END
                    ELSE BEGIN { b1 = b2 }
                            u := a2;
                            v := b2 + Sgn(b1-b2)*x
                         END;
                    Point[j+1].x := u;   Point[j+1].y := v;
                    a1 := a2;   b1 := b2;
                    a2 := u;   b2 := v
                 END{FOR}
         END{IF}
  
     ELSE BEGIN  { n <> 4, so alpha <> 90 degrees }
             x2 := Sqr(a1-a2) + Sqr(b1-b2);
             x := Sqrt(x2);  { x = length(side) }
             m1 := -Tan(360.0/n);  { m1 = Tan(interior angle) }
  
             FOR  j := n-k TO n-1  DO
                  BEGIN
                     IF  m1*(b1-b2) = a1-a2  THEN
                         BEGIN { a1 <> a2 }
                            mj := (b1-b2)/(a1-a2);
                            IF  mj > 0  THEN  s := Sgn(b1-b2)
                            ELSE  s := Sgn(b2-b1);
                            u := a2;
                            v := b2 + s*x
                         END
                     ELSE BEGIN  { m1*mj <> 1 }
                             IF  a1 = a2  THEN  mx := -1.0/m1
                             ELSE BEGIN
                                     mj := (b1-b2)/(a1-a2);
                                     mx := (m1 + mj)/(1.0 - m1*mj)
                                  END;
                             M := 1.0 + Sqr(mx);
                             C := mx*a1 - b1;
                             T := a1 + (b1 + C)*mx;
                             W := x2 - Sqr(a1) - Sqr(b1 + C);
                             u := (T + Sqrt(M*W + Sqr(T)))/M;
                             v := mx*u - C
                          END;
  
                      Point[j+1].x := u;   Point[j+1].y := v;
                      a1 := a2;   b1 := b2;
                      a2 := u;   b2 := v
                  END{FOR}
  
      END{Polygon}.