Konstantin's BLog
Polygon Intersection Algorithms
home top contents previous up next

/*
Main tasks:     1. Find do two polylines or two polygon boundaries intersect.
                2. Find do two convex polygons intersect.

Accuracy:       Absolute accuracy: not prone for floating point arithmetic inaccuracy.
Implementation: C#

License:        Copyright (C) 2008 Konstantin Kirillov, Landkey Computers.

                This Source Code is free for any use and modifications if above copyright line is provided.
                If text under / / and / *     * / comments is stripped from this Source Code, then this copyright note is not required.
                In any case, credit to author will be appreciated.
                
                THIS SOFTWARE IS PROVIDED "AS IS". ANY WARRANTIES ARE DISCLAIMED.                
                
Date:           July 13 - September 28 - November 11, 2008.


Extensibility:  Can be modified from integers to other numbers like float.
                Accuracy, speed, restrictions can change.
Dependencies:   None on any special geometrical package.
                Some methods of this module are interdpendent. 
                To remove calls' speed overhead, combine all methods in one.
   
Definition:     Polyline P is a sequence of line segments Ei=[Pi,Pi+1] where
                      i from 0 to n-1, n>1;
                      points Pi, Pi+1 belong |R^2;
                      Po can be equal Pn, points Pi,Pj for other pairs, i<>j, are different,
                Ei and Ei+1 called consequent segments.               
                      
Definition:     P is closed polyline iff Po = Pn.
                In this case, segments [Pn-2,Po] and [Po,P1] are consequent by definition.

                
Theorem:        If closed polyline P is not self-intersecting except points Po, then it divides |R^2 to 
                two areas P- and P+, external and closed. More accurate:
                          there exist two unique sets P- and P+:
                               i.    Intersection of P- and P+ is empty,
                               ii.   P- U P+ = |R^2.
                               iii.  P is inserted in P+.
                               iv.   P is a boundary between P+ and P-.
                               v.    P+ is bounded
                This implies that n>2.
               
Definition:     Polygon   df=  P+ from above theorem and
                no consequent segments Ei belong to the same line (we need this "normalization" for simplicity of algorithms).
                Plainly, for convenience. we include internals and boundary of polygon into polygon.
                We'll call poligon's polyline's segments edges or sides. 
 
Definition C:   Convex   df=   poligon P when any line segment g with end points on P belongs P+ and   (1)
                no consequent edges lie on the same line.                                              (2)
                We added restriction (2) for convenience of some our programs.
 
Definition O:   Orientation.
                Orientation of vector b in respect to vector a is a sign(a*b).
                a*b is a vector product. By definition sign(0)=0.
                If a*b < 0, b is negatively oriented to a.
                Point X is positively oriented in respect to segment [A,B] iff AB*AX > 0.
                Set of such X forms open half-plane which we call "positive site".

Theorem S:      Let C - convex and E its edge.
                 i.  All points in C-E have the same orientation to E.
                     Plainly, all edeges are on the same site form E.
                 ii. Let [AB] and [BC] consequent edges.
                     Then BC has the same orientatinon to AB as C to AB.
                     Plainly, polyline rotates to the same direction were polygon lies.
 
Definition:     For any two non-intersecting convexes X, X', internal angle a of X is a repeller iff
                it does not inbersect with X'.
                
                For example: a,c are repellers, b is not:
                                                     
                             *-----------* a          *----------------*
                            /             \           |               /
                           /      X        \          |      X'     /  
                        b *-----------------*        c*------------*
                                                    
                        
Theorem R:      If two convexes do not intersect, then each of them has a repeller.
                
Terminology:    polyline: polygonal chain, polygonal curve, polygonal path, or piecewise linear curve.
                L(s):     df=  line which contains line segment s.
References:     http://en.wikipedia.org/wiki/Closed_polygonal_chain


*/

using System;

namespace PG {

    class Poly {


        //==================================================================================
        //Primitive test cases.
        //Assume we have two convex polygons P1 and P2.
        //For example, consider following test:
        public static int[,] Poly1 = { { 0, 0 }, { 10, 0 }, { 10, 2 }, { 0, 2 } };
        public static int[,] Poly2 = { { 1, 1 }, { 11, 3 }, { 5, 5 }, { 3, 6 }, { 0, 3 } };
        public static int[,] Poly3 = { { 0, 0 }, { 1, -1 }, { 0, -2 }, { -1, -1 } };
        public static int[,] Poly4 = { { 11, 0 }, { 12, 0 }, { 12, -1 }, { 11, -1 } };
        //Interwoven boundaries with Poly1:
        //        ------
        //        |    |
        //   ---------------
        //   |    |    |   |
        //   ---------------
        //        |    |
        //        ------
        public static int[,] Poly5 = { { 5, -5 }, { 7, -5 }, { 7, 5 }, { 5, 5 } };

        //==================================================================================

        //Auxiliary constants denoting position of a point in respect to line segment and
        //given orientation:
        private const int POINT_POSITIVE =  1;
        private const int POINT_NEGATIVE = -1;
        private const int POINT_AHEAD    = -2;
        private const int POINT_INSIDE   = -0;
        private const int POINT_BEHIND   = -3;


        //**************************************************
        // Main methods for convex polygons.
        //==================================================


        //DESCRIPTION: This is probably most direct and most slow method of
        //             finding out do two convex polygons are intersect or not.
        //
        //             At the first step, it checks is fisrt vertex of first 
        //             polygon inside of the sectod.
        //             If it is, we are lucky and our mission is completed.
        //
        //             If not, then struggle of second step begins ...
        //             In second step we simply check does the boundary of first
        //             polygon intersects boundary of the second.
        //             
        //COST:        Worse case:  about   nP1*nP2*64m
        //             nP1,nP2 are numbers of vertices, m - multiplication.
        //
        public static bool TwoConvexPolygonsDoIntersectI(int[,] P1, int[,] P2) {

            if (IsInsideOfConvexPolygon(P1[0, 0], P1[0, 1], P2)) return true;     //Step 1. 
            return PolylinesIntersect(P1, P2, 1);                                 //Step 2.

        }



        //Method TwoConvexPolygonsDoIntersectII(...) tests two convex polygons P1 and P2 intersection.
        //       P1,P2 have arbitrary number of vertices > 2.
        //       Polyline rotation of P1, P2 is arbitrary.
        //       Touching polygons considered as intersected.

        //       Poligons are represented as array of consequent vertices.
        //       No consequent sides are collinear. No vertices coinside.
        public static bool TwoConvexPolygonsDoIntersectII(int[,] P1, int[,] P2) {

            //Just test: are some vertices of P1 inside of P2 or vice versa:
            if (SomeAreInside(P1, P2) || SomeAreInside(P2, P1)) return true;

            //This is an interesting case. Boundaries of poligons can be interwoven
            //Or they can not intersect at all. 
            //Apparently to resolve this cases, there can be fast method, but
            //in mean time we use possibly slow method which directly tests
            //an intersection of boundaries:

            return PolylinesIntersect(P1, P2, 1);  // 1 means P1,P2 are ArePolygons.

        }

        /// <summary>
        /// This method is not finished yet although passes simple tests.
        /// Tests do Polygons G and H intersect.
        /// Based on Theorem R.
        /// </summary>
        /// <param name="G">To loop via its angles.</param>
        /// <param name="H">To loop via its vertices.</param>
        /// <returns>True if G and H intersect.</returns>
        public static bool TwoConvexPolygonsDoIntersectIII(int[,] G, int[,] H) {

            const int PIERCED = -1;

            //Define orientation of G:
            int oriG = Orientation(G[2, 0], G[2, 1], G[0, 0], G[0, 1], G[1, 0], G[1, 1]);
            int nG1 = G.GetUpperBound(0);
            int nG = nG1+1;
            int nH = H.GetUpperBound(0)+1;
            //We need this array to hunt a repeller:
            int[] repA = new int[nG];
            //This index, iA, means: all angles with iX < iA failed repeller 
            //test and are not repellers. 
            //We start from iA = 0 which means no andgles have been tested yet:
            int iA = 0;
            //Initially, it is unknown is an angle repeller or not:
            //we flag "unknown" state by value which will be never used when parsing G:
            for (int iG = 1; iG < nG; iG++) repA[iG] = nH;
            //Now, we begin to scan all vertices of H and check do they belong to G:
            //At the same time, collecting negative statistics to hunt a repeller:
            for (int iH = 0; iH < nH; iH++) {
                //Remove from A-loop all failed angles:
                if (repA[iA] == PIERCED) {
                    while (repA[iA] == PIERCED) {
                        iA = (iA + 1) % nG;
                        if (0 == iA) return true;
                    }
                    repA[iA] = iH;
                }
                //Later, we will start to test repeller candidate from some vertex J of H.
                //We keep J in repA to avoid redundant tests.
                int iStart = iA;
                //Loop via angles in polygon G.
                //We break this loop when vertex iH is repelled by the angle.
                for (int iGR = 0; iGR < nG; iGR++) {
                     //Index iGR is relative to iStart. It merely loops via "number" of vertices.
                     //We really start from vertex iStart:
                     int iG     = (iGR+iStart) % nG;
                     int iGNext = (iG +1     ) % nG;
                     //Find out: relation of vertex iH to polygon G: inside, on edge, or outside:
                     switch (PointRelationToASegment(oriG, H[iH, 0], H[iH, 1], G[iG, 0], G[iG, 1], G[iGNext, 0], G[iGNext, 1])) {
                         case POINT_POSITIVE: 
                                  //iH is in the side of G.
                                  //This is "good" for inside test, "bad" for repeller test.
                                  //Check if an angle is a repeller:
                                  if(iGR>0) {
                                     //We are testing second edge of an angle.
                                     repA[iA]=PIERCED; 
                                     //Set new repeller candidate for test:
                                     iA = iG;
                                     if (repA[iA] != PIERCED) repA[iA] = iH;
                                  }
                                  //We continue iGR loop:
                                  break;
                          case POINT_NEGATIVE:
                                  //iH is outside of G: 
                                  //Break loop G:
                                  goto ContinueH;
                         case POINT_AHEAD:     
                                  //This case is most interesting. Edge is pierced, but angle V still can be a repeller.
                                  //         U              V
                                  //          o------------o              * iH
                                  //                  iG    \
                                  //                         \
                                  //                          \
                                  //                    iGNext \
                                  //                            \
                                  //                             o
                                  //
                                  //Angle U is pierced:
                                  if (iG > iA) {
                                      //U=A => iA is pierced:
                                      repA[iA] = PIERCED;
                                      //Set new repeller candidate for test:
                                      iA = iGNext;
                                      if( repA[iA] != PIERCED ) repA[iA] = iH;
                                  } else {
                                      //V=A => iA predecessor is pierced:
                                      if (iA == 0) {
                                          //We care only about angle nG1. Others are already marked PIERCED.
                                          //Apparently good in context of low vertex number.
                                          repA[nG1] = PIERCED;
                                      }
                                  }
                                  //Break loop G:
                                  goto ContinueH;
                         case POINT_BEHIND:
                                  //  The angle V is not a repeller:
                                  //
                                  //    iH   U              V
                                  //    *     o------------o   
                                  //         /        iG    \
                                  //        /                \
                                  //       /                  \
                                  //      /             iGNext \
                                  //     /                      \
                                  //    o                        o
                                  //
                                  //
                                  if (iG > iA) {
                                      //A=U, next=V is pierced:
                                      repA[iGNext] = PIERCED;
                                  } else {
                                      //A=V and is pierced:
                                      repA[iA] = PIERCED;
                                      //Set new repeller candidate for test:
                                      iA = iGNext;
                                      if (repA[iA] != PIERCED) repA[iA] = iH;
                                  }
                                  //Break loop G:
                                  goto ContinueH;
                         case POINT_INSIDE:
                                  //iH is on the edge, we are lucky to finish cycles so early:
                                  //
                                  //         U       iH     V
                                  //          o-----*------o   
                                  //                  iG    \
                                  //                         \
                                  //                          \
                                  //                    iGNext \
                                  //                            \
                                  //                             o
                                  //
                                  return true;
                     }//switch( oriG * 
                } //for (int iGR 
                //do1 Don't know how to break loop iGR. Doing this in wierd way:
            ContinueH: iStart = iStart;
            }//for (int iH

            //Now, we have no vertices of H inside of G.
            //Let us find out do remianing angles repell H.

            //First, set a limit for incomplete test of angle iA.
            int nHA = repA[iA];
            for (int iG = iA; iG < nG; iG++) {
                if (iG == nG1) {
                    if (repA[iG] == PIERCED) return true;            //Polygons intersect even no vertices of H are inside of G.
                }
                if (PIERCED == repA[iG]) continue;                   //Previous or next angles were already tested.
                for (int iH = 0; iH < nHA; iH++) {
                    //Loop via iGA, first and second side of an angle iG:
                    for (int iGA = 0; iGA < 2; iGA++) {
                        int iG0 = (iG  + iGA) % nG;
                        int iG1 = (iG0 +   1) % nG;
                        switch (PointRelationToASegment(oriG, H[iH, 0], H[iH, 1], G[iG0, 0], G[iG0, 1], G[iG1, 0], G[iG1, 1])) {
                            case POINT_POSITIVE: goto ContinueG;     //Pierced.
                            case POINT_NEGATIVE: break;              //Survived: repelled this point.
                            case POINT_BEHIND: 
                                if (0 == iGA) {
                                    goto ContinueG;                  //iG is pierced.
                                } else {
                                    repA[iG1] = PIERCED;             //Next is pierced.
                                }
                                break;                               //iG is survived. 
                            case POINT_AHEAD: 
                                if (0 == iGA) {                      //Previous is pierced.
                                    if (0 == iG0) {
                                        repA[nG1] = PIERCED;
                                    }
                                } else {
                                    goto ContinueG;                  //iG is pieced.
                                }
                                break;                               //iG is survived.
                            case POINT_INSIDE: return true;          //Poligons intersect.
                        }//switch
                    }//for (iGA
                }//for( int iH
                //Repeller is found. It iG.
                return false;
            ContinueG:
                nHA = nH;
            }
            //No repellers.
            return true;
        }//TwoConvexPolygonsDoIntersectIII
        
        //==================================================
        // Main methods for convex polygons.
        //**************************************************



        //**************************************************
        // Auxiliary mehods for polylines.
        //==================================================

        /// <summary>
        /// Find out relation of point H to line segment [A,B] in respect to
        /// given orientation ori.
        /// </summary>
        /// <param name="oriG">Selected orientation.</param>
        /// <param name="Hx"></param>
        /// <param name="Hy"></param>
        /// <param name="Ax"></param>
        /// <param name="Ay"></param>
        /// <param name="Bx"></param>
        /// <param name="By"></param>
        /// <returns>1 - H is cooriented with ori, -1 controriented, 0 belongs [A,B], -2 ahead of [A,B], -3 - behind of [A,B]</returns>
        public static int PointRelationToASegment( int ori, int Hx, int Hy, int Ax, int Ay, int Bx, int By ) {
            int relation = ori * Orientation(Hx, Hy, Ax, Ay, Bx, By);
            if (relation != 0) return relation;
            //This special case is probably most technically complex:
            //Point H belongs L(A,B) but can be inside of [A,B] or out.
            //This should be a rare case for random polygons.
            //Find out the relation of vector r=H-A to vector s=B-A:
            int sx = Ax - Bx;
            int sy = Ay - By;
            int scalarProduct = (Hx - Ax) * sx + (Hy - Ay) * sy;
                                  
            if (scalarProduct > sx * sx + sy * sy) {
                                      //This case is most interesting. 
                                      //In case if AB is an edge, the edge is pierced, but angle B still can be a repeller.
                                      //         A              B
                                      //          o------------o              * H
                                      //                  iG    \
                                      //                         \
                                      //                          \
                                      //                    iGNext \
                                      //                            \
                                      //                             o
                                      //
                                      return POINT_AHEAD;
            }
            if (scalarProduct >= 0) {
                                      //
                                      //         A       H      B
                                      //          o-----*------o   
                                      //                  iG    \
                                      //                         \
                                      //                          \
                                      //                    iGNext \
                                      //                            \
                                      //                             o
                                      //
                                      return POINT_INSIDE;
            } 
                                      //In case if AB is an edge, the angle B is not a repeller:
                                      //
                                      //    H    A              B
                                      //    *     o------------o   
                                      //         /        iG    \
                                      //        /                \
                                      //       /                  \
                                      //      /             iGNext \
                                      //     /                      \
                                      //    o                        o
                                      //
                                      //
                                      return POINT_BEHIND;
            }//PointRelationToPolygon




        //PURPOSE:      Find are two polylines or two polygon boundaries intersect.
        //INPUT:        g,h - two polylines submitted as arrays of their vertices.
        //              ArePolygons = 1, polylines are polygons:
        //                               segments [G(n-1),Go], [H(m-1),Ho] are included in comparision.
        //              ArePolygons = 0, not considering segments which closing polylines.
        //RESTRICTIONS: Due |int|~<2^31, magnitude of vertices is less than about 64000.
        //METHOD:       Consequently check does each pair of segments intersect until first intersection
        //              is found or no intersectios are found.
        //COST:         Worse case:    nP1*(8m+16a)*nP2(8m+16a).
        //              nP1,nP2 are numbers of vertices.
        //              Average case?: n*(8m+16a)
        public static bool PolylinesIntersect(int[,] g, int[,] h, int ArePolygons) {
            int gLastVertex = g.GetUpperBound(0);
            int hLastVertex = h.GetUpperBound(0);
            int gVertices = gLastVertex + 1;
            int hVertices = hLastVertex + 1;
            int gVertexLimit = gLastVertex + ArePolygons;           //n for Polygons, n-1 for polylines.
            int hVertexLimit = gLastVertex + ArePolygons;
            for (int i = 0; i < gVertexLimit; i++) {
                int iNext = (i + 1) % gVertices;
                for (int j = 0; j < hVertexLimit; j++) {
                    int jNext = (j + 1) % hVertices;
                    if (TwoLineSegmentsIntersect(g[i, 0], g[i, 1], g[iNext, 0], g[iNext, 1],
                                                 h[j, 0], h[j, 1], h[jNext, 0], h[jNext, 1])) {
                        return true;
                    }
                } //for j
            } //for i
            return false;
        }// PolylinesIntersect()



        //DESCRIPTION Find out are two arbitrary non-zero line segments in |R^2 intersect.
        //RETURNS     true  <=> intersect,
        //            false <=> not intersect.
        public static bool TwoLineSegmentsIntersect(int A1x, int A1y, int A2x, int A2y,
                                                    int B1x, int B1y, int B2x, int B2y) {
            int result1 = PointsBAreOnOneSideFromPointsA(A1x, A1y, A2x, A2y, B1x, B1y, B2x, B2y);
            if (result1 >= 0) {
                //Not on one side.
                int result2 = PointsBAreOnOneSideFromPointsA(B1x, B1y, B2x, B2y, A1x, A1y, A2x, A2y);
                if (result2 >= 0) {
                    if (result1 == 0 || result2 == 0) return true;
                    if (result1 != 3) {
                        //La and Lb are not collinear, but one of Bi is on La
                        // if( result2 == 3 //Cannot happen ... some redundancy ...
                        // The only choice is some Ai=some Bi: intersect ...
                        return true;
                    }
                    //At this moment, both sides are along the same line:
                    if (CollinearSegmentsIntersect(A1x, A1y, A2x, A2y, B1x, B1y, B2x, B2y)) return true;
                } // if( result2 >=0 )
            }
            return false;
        }



        //==================================================
        // Auxiliary mehods for polylines.
        //**************************************************





        //**************************************************
        // Auxiliary mehods for convex polygons.
        //==================================================

        //To find out are some vertices of P1 inside of P2 make a loop via P1:
        public static bool SomeAreInside(int[,] P1, int[,] P2) {
            int v = P1.GetUpperBound(0) + 1;
            for (int i = 0; i < v; i++) {
                if (IsInsideOfConvexPolygon(P1[i, 0], P1[i, 1], P2)) return true;
            }
            return false;
        }



        //To find out is point inside the polygon we just test 
        //   1) is point cooriented with each edge of polygon or
        //   2) belons to at least one of the edges.
        //We call point cooriented with side if point has the same orientation as polygon.
        //We call orientation of polygon positive if path trough polyline vertices is counterclockwise, negative if clockwise.
        //
        //Now, we have enough definitions to write a method.
        //
        //INPUT:  (x,y) point to be tested to be inside of polygon P or not.
        //        We assume that polygon P is ordered: each element is a consequent vertex.
        //        No consequent edges are collinear.
        //COST    (n+1)*(2m+5a) (wihthout boundary touching case)
        //        m - multiplications, a-addtions, n - vertices number.
        //
        //DEPEND: Orientation
        public static bool IsInsideOfConvexPolygon(int x, int y, int[,] P) {
            //Theorem: Polygon's orientation is an orientation of an arbitrary edge to previous edge:
            int polygonOrientation = Orientation(P[0, 0], P[0, 1], P[1, 0], P[1, 1],
                                                 P[2, 0], P[2, 1]);
            //Find number of vertices, v:
            int v = P.GetUpperBound(0) + 1;
            for (int i = 0; i < v; i++) {
                int j = (i + 1) % v;  //j is a next vertex after i.
                switch (Orientation(P[i, 0], P[i, 1], P[j, 0], P[j, 1], x, y) * polygonOrientation) {
                    case -1: return false;  //Counteroriented.
                    case 0:  //This is a special case. Point (x,y) belongs the line of the polygon's side, but can be inside or out.
                        //Find out that projection of vector r=(x,y)-P[i] is in side's limits:
                        int rx = x - P[i, 0];
                        int ry = y - P[i, 1];
                        int sx = P[j, 0] - P[i, 0];
                        int sy = P[j, 1] - P[i, 1];
                        int scalarProduct = rx * sx + ry * sy;
                        if (scalarProduct <= sx * sx + sy * sy && scalarProduct >= 0) {
                            //This means the point belongs the side.
                            //Wrong: if( (x-P[i,0])*(x-P[j,0] ) <= 0 ) {
                            return true;
                        }
                        break;
                }
            }
            return true;
        } //method IsInsideOfConvexPolygon


        //==================================================
        // Auxiliary mehods for convex polygons.
        //**************************************************









        //**************************************************
        // Self-sufficient methods. Do not depend on
        // other methods in this module.
        //==================================================

        //Following Definition O, Orientation can be defined by using a cross product:
        //
        //        | i   j   k |
        //        | ax ay   0 |
        //        | bx by   0 |
        //
        //Saying it simpler, Orientation is a sign of determinant:
        //
        //        | ax  ay |
        //        | bx  by |
        //
        //Function Orientation:
        //  INPUT  points O,A,B
        //  OUTPUT  1 B  is positive to OA
        //          0 OB is collinear to OA
        //         -1 B  is negative to OA
        //  COST   2 multiplications and 5 differences.
        public static int Orientation(int Ox, int Oy, int Ax, int Ay, int Bx, int By) {
            int ax = Ax - Ox;
            int ay = Ay - Oy;
            int bx = Bx - Ox;
            int by = By - Oy;
            return Math.Sign(ax * by - bx * ay);
        } //Orientation


        //DESCRIPTION:  Checks is line [A1,A2] between two points B1,B2 or not.
        //INPUT:        Two line segemts [A1,A2], [B1,B2] set by their end points.
        //              a=(A1,A2), b=(B1,B2).
        //              A1=(A1x,A1y), ...
        //RESTRICTIONS: A1<>A2, B1<>B2.
        //RETURNS -1 <=> on one side of line La which contains segment a,
        //         1 <=> B1 belongs La,
        //         2 <=> B2 belongs La,
        //         3 <=> La = Lb
        //         0 <=> on different sides,
        //METHOD:       Comparing signs of two cross products.
        //COST          4m+8a.  m - multiplications, a-addtions.
        public static int PointsBAreOnOneSideFromPointsA(int A1x, int A1y, int A2x, int A2y,
                                                          int B1x, int B1y, int B2x, int B2y) {
            int ax = A2x - A1x;
            int ay = A2y - A1y;
            int c1x = B1x - A1x;
            int c1y = B1y - A1y;
            int c2x = B2x - A1x;
            int c2y = B2y - A1y;
            int posB1 = ax * c1y - c1x * ay;
            int posB2 = ax * c2y - c2x * ay;
            int result = (posB1 == 0 ? 1 : 0) + (posB2 == 0 ? 2 : 0);
            if (result > 0) return result;
            return 0 < posB1 * posB2 ? -1 : 0;
        } //PointsBAreOnOneSideFromPointsA



        //DESCRIPTION Finds out do closed line segments intersect.
        //INPUT a=(A1x,A1y),(A2x,...
        //      For example:
        //      ..........-------------------->............. a
        //      ....<------------........................... b
        //RETURN true <=> segments intersect,
        //       false <=> not intersect.
        public static bool CollinearSegmentsIntersect(int A1x, int A1y, int A2x, int A2y,
                                                      int B1x, int B1y, int B2x, int B2y) {
            //First take our unit of measurement, a, and point of reference A1.
            //We do at most three tests:
            //B1 in a:
            int ax = A2x - A1x;
            int ay = A2y - A1y;
            int b1x = B1x - A1x;
            int b1y = B1y - A1y;
            int a2 = ax * ax + ay * ay;
            //Ready for the fist test:
            int s = b1x * ax + b1y * ay;
            if (s >= 0 && s <= a2) return true;
            //No, B1 is outside of a.
            //Test, B2 in a.
            int b2x = B2x - A1x;
            int b2y = B2y - A1y;
            s = b2x * ax + b2y * ay;
            if (s >= 0 && s <= a2) return true;
            //Now swap roles. Test A1 in b
            int bx = B2x - B1x;
            int by = B2y - B1y;
            s = -(bx * b1x + by * b1y);
            int b2 = bx * bx + by * by;
            if (s >= 0 && s <= b2) return true;
            //Other cases are useless ...
            return false;
        } //CollinearSegmentsIntersect



        //We plan to add additional method which generalizes
        //method "IsInsideOfConvexPolygon" and based on 
        //Theorem R.
        //The search strategy is while checking does
        //the vertex fall into another polygon, keep records
        //about repelling angles.
        //In other words, if vertex falls into polygon in
        //two conseqent edges, then the angle is excluded
        //from repeller candidates.


        //==================================================
        // Self-sufficient methods. Do not depend on
        // other methods in this module.
        //**************************************************



    } //class Poly
} //namespace PolyNS

Copyright (C) 2008 Landkey Computers