Object Oriented C++ Library Specifications and Design

For 2D rendering of maps

 

 

 

Version 1.0

 

 

Revision History

 

Date	Version	Description	Authors
27/2/2003	1.0 (Draft)		abhilash agarwal
9/2/2003	1.0 (Release)		abhilash agarwal

 

Table of Contents

1.            Introduction  4

1.1        Purpose  4

1.2        Scope  4

1.3        Definitions, Acronyms, and Abbreviations  4

1.4        References  4

1.5        Overview   4

2.            Design Objective  4

3.            Concepts, Terms and Terminologies  5

4.            Functional diagram   8

5.            Algorithms  9

6.            C++ Library Design  33

 

1.     Introduction

 

1.1     Purpose

 

This document is aimed at explaining design of C++ library to intended developers of Manchitra’s mapping product iMapRenderer. The library contains low-level 2D graphics APIs which uses data structure recommended by Open GIS, a consortium which develops open standards, which Manchitra follows. The library is intended to be part of the above mentioned product once it is developed and rigorously tested.

 

The document also explains all the terms and terminologies used for building concepts and various industry algorithms, along with the optimization for performance improvements.

 

1.2     Scope

 

The document primarily covers:

 

1. Design of the C++ library containing 2D graphics APIs.

 

1.3     Definitions, Acronyms, and Abbreviations

 

Line=line segment with two end point

 

1.4     References

1   Clipping link:

 

http://www.cs.utah.edu/classes/cs5600/lecture_slides/Lec04_PolygonClipping.pdf

 

2 centeriod link:

http://homepages.borland.com/efg2lab/Graphics/PolygonArea.htm

 

1.5     Overview

 

2.     Design Objective

 

1. Compatibility with Open GIS data structures i.e. OGR classes used in the product.
2. Performance optimization wherever possible by detailed analysis of various algorithms available.
3. Clean interfaces to the developers to minimize programming time.

 

 

 

 

 

Concepts, Terms and Terminologies

 

Preface:

 

Algorithmic description of Touch, Cross, Within and Overlap relationships. All possible test cases have been discussed below. They form the algorithmic part of the implementation to be done in the OGRgeometry class.

 

1)Touch: Implemented for P/P, L/L, P/L, P/Point, L/Point categories.

• P/P:

 

Example:

 

 

 

           

 

 

Algorithm: First check for ‘not-OverlapP/P’.  If the polygons are A(n edges) and B(m edges), atleast one vertex(OGRawPoint) of A lies on one of the edges of B.

So use Touches L/point   repeatedly for all edges of A or B(whichever has lesser edges).

 

• L/L:

 

Example:

 

 

 

 

 

                       

Algorithm: First check for ‘not-overlapL/L’.Use TouchesL/Point Test for all vertices of A(orB).

           

• P/L:

 

Example:

 

 

 

 

 

           

      Algorithm: Use TouchesL/Point test for all vertices of the LineString  . If passed

      check for not-CrossP/L.

     

• P/Point:

 

Example:         

 

           

  

 

 

Algorithm: Use TouchesL/Point test for all the edges of the polygon.

 

• X1,Y1

  L/Point:                                   

 

Example:

 

X2,Y2

                       

 

 

Algorithm: a) Check if point is one of the vertices of LineString.

       b) If not use point-on-line test:

            (X₁-X₃)(Y₂ –Y₃) = (X₂-X₃)(Y₁ –Y₃).

 

 

2) Crosses: Implemented for P/L and L/L categories.

 

• P/L:

Example:

 

           

 

 

 

 

            Algorithm: Use CrossesL/L for all the edges of the polygon.

 

• L/L:

Example:

 

           

 

 

Algorithm: see algorithm section

 

3) Within: Implemented for P/P, P/L, L/L and P/Point categories.

 

• P/P:

Example:

           

 

           

 

 

 

 

 

 

·        Algorithm: Use withinPoint/P test for one polygon then use TouchPoint/P test for those vertex of polygon who fail in previous test. If vertex pass   second test     then one polygon lies within another

 

·         L/L

 

Example:         

 

 

 

 

 

Algorithm: Use TouchesL/Point for all the vertices of the LineString being tested for within relationship with (possibly) enclosing LineString.

 

• P/L:

Example:

 

           

 

 

Algorithm: Test for WithinP/Point for all the vertices of the LineString.

 

 

4) Intersect: Implemented for and P/P situations.

 

·        P/P:

Example:         

                       

 

 

 

 

 

 

 

 

 

Algorithm: Atleast on vertex of one of the polygons is ‘within’ the other( and atleast one should be outside). Use WithinP/Point test for all the vertices of one of the polygons.

 

 

 

                       

 

 

 

 

3.     Functional diagram

 

Type1	Type2	Operation	Algorithm
Point	Line	Touch	Trivial
Polygon	Polygon	Touch	Derive
Polygon	Point	Touch	Derive
Line	Line	Touch	Derive
Point	Line	Distance	Trivial
Polygon	Line	Within	Derive
Line	Line	Within	Derive
Point	Polygon	Within	Philippe Reverdy algorithm
Line	Line	Cross	Trivial
Line	Polygon	Cross	Derive
Line	Polygon	Touch	Derive
Polygon	Polygon	Intersect/clip	Weiler algorithm
Line	Polygon	Clip	Liang barsky algorithm
Polygon	Polygon	Within	Derive
Polygon	Polygon	Overlap	Derive
Line		Midpoint	Derive
Polygon		Level point	Link :http://homepages.borland.com/efg2lab/Graphics/PolygonArea.htm
Point	line	distance	Trivial
Polygon	Polygon	Disjoint	derive
Polygon	Polygon	Union ,if intersect	Weiler algorithm

 

4.     Algorithms

 

 

How to find intersection of two 2d line segments:

 

Let A,B,C,D be 2-space position vectors. Then the directed line
segments AB & CD are given by:

AB=A + r(B-A), r in [0,1]
CD=C + s(D-C), s in [0,1]

If AB & CD intersect, then

A + r(B-A)=C+ s (D-C), or

Ax + r(Bx-Ax)=Cx +s(Dx-Cx)
Ay+ r(By-Ay)=Cy+ s(Dy-Cy) for some r,s in [0,1]

Solving the above for r and s yields
(Ay-Cy)(Dx-Cx)-(Ax-Cx)(Dy-Cy)
r = ----------------------------- (eqn 1)
(Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx)

(Ay-Cy)(Bx-Ax)-(Ax-Cx)(By-Ay)
s = ----------------------------- (eqn 2)
(Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx)

Let P be the position vector of the intersection point, then

P=A+r(B-A) or

Px=Ax+r(Bx-Ax)
Py=Ay+r(By-Ay)

By examining the values of r & s, you can also determine some other limiting conditions:

If 0<=r<=1 & 0<=s<=1, intersection exists
r<0 or r>1 or s<0 or s>1 line segments do not intersect

If the denominator in eqn 1 is zero, AB & CD are parallel
If the numerator in eqn 1 is also zero, AB & CD are coincident

If the intersection point of the 2 lines are needed (lines in this context mean infinite lines) regardless whether the two line segments intersect, then

If r>1, P is located on extension of AB
If r<0, P is located on extension of BA
If s>1, P is located on extension of CD
If s<0, P is located on extension of DC

Also note that the denominators of eqn 1 & 2 are identical.

 

 

 

Flow chart:

 

 

 

 

 

4.1     How do I find the distance between a point and a line?

The distance, D, between a point and a line is the length of the perpendicular line segment connecting the point and the line.

To find D:

1. Find the slope, m', of the line segment P1P2. (Since it is perpendicular to the other line, it is the inverse of its slope: 1/m.)
2. Find the slope-intercept form of the line containing P1P2 using m' and P1.
3. Find P2, the intersection of these two lines.
4. Compute the distance between P1 and P2. This is the distance between P1 and the line, D.

 

 

 

 

5.     Determining if a point lies on the interior of a polygon

 

 Philippe Reverdy algorithm is to compute the sum of the angles made between the test point and each pair of points making up the polygon. If this sum is 2pi then the point is an interior point, if 0 then the point is an exterior point. This also works for polygons with holes given the polygon is defined with a path made up of coincident edges into and out of the hole as is common practice in many CAD packages.

The inside/outside test might then be defined in C as

typedef struct {

   int h , v;

} Point;

int InsidePolygon(Point *polygon,int n,Point p)

{

   int i;

   double angle=0;

   Point p1,p2;

   for (i=0;i<n;i++) {

      p1.h = polygon[i].h - p.h;

      p1.v = polygon[i].v - p.v;

      p2.h = polygon[(i+1)%n].h - p.h;

      p2.v = polygon[(i+1)%n].v - p.v;

      angle += Angle2D(p1.h,p1.v,p2.h,p2.v);

   }

   if (ABS(angle) < PI)

      return(FALSE);

   else

      return(TRUE);

}

/*

   Return the angle between two vectors on a plane

   The angle is from vector 1 to vector 2, positive anticlockwise

   The result is between -pi -> pi

*/

double Angle2D(double x1, double y1, double x2, double y2)

{

   double dtheta,theta1,theta2;

   theta1 = atan2(y1,x1);

   theta2 = atan2(y2,x2);

   dtheta = theta2 - theta1;

   while (dtheta > PI)

      dtheta -= TWOPI;

   while (dtheta < -PI)

      dtheta += TWOPI;

   return(dtheta);

}

 

Line clipping with rectangular window

 

We have two algorithms for this:

 

1         cohen-sutherland line clipping algorithm

1                    liang-barsky line clipping

 

Draw back of cohen –sutherland  line clipping :

 

              I.      it require more intersection calculation then second algorithm

           II.      it repeatedly calculate intersections along a line path ,even though the line may be completely outside the clipped window

         III.      each intersection calculation requires both a division and a multiplication

 

Advantage of liang –barsky algorithm over cohen-sutherland method

 

              I.      intersection Calculation are reduced

           II.      window intersection of the line are computed only once ,when the final value of u1 and u2 have been computed   

         III.      it can be extended to nonrectangular clip  window becaz it is based on parametric line equations

 

 

 

 

Liang-Barsky Clipping

 

Parametric clipping - view line in parametric form and reason about the parameter values

•More efficient, as not computing the coordinate values at irrelevant vertices

•Clipping conditions on parameter: Line is inside clip region for values of t such that:

Equation of line can be represented as a

X=x1+m(x2-x1)

Y=y1+m(y2-y1)

 

Where  0<m<1

When m=0 =>x1,y1

When m=1 =>x2,y2

 

Point clipping condition can be  expressed as

Xwmin<=x1+m(x2-x1)<=Xwmax

Ywmin<=y1+m(y2-y1)<=Ywmax

 

These  can be further expressed  as

INT* pk<=qk; for k=0,1,2,3,4……..

 

 

So we have

P1=  -(x2-x1)

P2=  (x2-x1)

P3=  -(y2-y1)

P4=  (y2-y1)

Where

Q1=x1-xwmin

Q2=xwmax-x1

Q3=y1-ywmin

Q4=ywmax-y1

 

 

•Infinite line intersects clip region edges when:

•When p_k<0, line goes from outside to inside - enter

•When p_k>0, line goes from inside to outside - leave

•When p_k=0, line is parallel to an edge (clipping is easy)

•If there is a segment of the line inside the clip region, sequence of infinite line intersections must go: enter, enter, leave, leave

6.     Liang-Barsky - Algorithm

•Compute entering INT  values, which are q_k/p_k for each p_k<0

•Compute leaving INT values, which are q_k/p_k for each p_k>0

•Parameter value for small end of line is: m1=  max(0,entering INT )

•parameter value for large end of line is: m2=   min(1, leaving  INT)

•if m1<m2, there is a line segment - compute endpoints by substituting m1,m2 values

Flow chart:

 

 

 

 

 

 

 

 

 

 

procedure clipliangbarsky(winmin,winmax:dcpt2;n:integer;pts:wcpts2);

var i: integer;

 

procedure clipline(p1,p2:wcpt2);

var

u1,u2,dx,dy:real;

 

function cliptest(p,q:real;var u1,u2:real):Boolean;

var  r : real;

begin

cliptest:=true;

if p<0.0 then

begin

r=q/p;

if r>u2 then cliptest;=false

else if  r>u1 then u1=r

end

else

if p>0.0 then

begin

r=q/p;

if r>u1 then cliptest;=false

else if  r<u2 then u2=r

end

else if q<0.0 then cliptest=false

end;

begin

 

    u1=0

    u2=0

   dx=p2.x-p1.x;

   if cliptest(-dx,p1.x,-winman.x,u1,u2) then

   if cliptest(dx,winman.x,-p1.x,u1,u2) then

begin

               dy=p2.y-p1.y

   if cliptest(-dy,winmax.y,-p1.y,u1,u2) then

            begin

                        if u1>0 then

                                    p1.x=p1.x+u1*dx;

                                    p1.y=p1.y+u1*dy;

           

                        if  u2<1

                                    p2.x=p1.x+u2*dx;

                                    p2.y=p1.y+u2*dy;

            end

end

 {draw line from p1 to p2 using lineDDA algorithm}

end

 

begin

            for (I=0 to n-1 ) do clipline (pts[I],pts[I+1]);

clipline (pts[n],pts[1]);

end;

 

 

 

Weiler-Atherton polygon  clipping algorithm

PROBLEM

 

Implement Weiler-Atherton. You should draw each polygon in a different color and fill the clip areas generated with a third color.

NOTES:

 

The Weiler-Atherton algorithm is the most general of the clipping algorithms. We have two 2D polygons (may be convex or concave and they both may have holes). The polygon to be clipped is called the SUBJECT polygon and the polygon defining the clipping area is called the CLIP polygon. To make the algorithm work easier (in the data structures, etc.) we usually assume that the exterior vertices are given clockwise and the hole vertices are given counterclockwise. In clipping we usually want to find the parts of the subject polygon that are inside the clip polygon. However, this algorithm can be used in modeling to find the "union", "intersection", and "difference" of the polygons.

The data structures are several circular linked lists of vertices which are also linked together and the clipping is done by traversing these. The lists could be doubly linked and traversal in one direction would produce clipped regions and traversal in the other will produce exterior.

 

StepI    building data structure of polygon 

 

The first phase of the building of the data structures occurs when we input the edges and put them in two linked lists - the SUBJ list and the CLIP list. The vertices are place in order from input (thus clockwise). There are separate lists for the exterior and for each hole. Thus, the initial build is a standard queue insert. Note that this creates a list in which a standard list traversal is equivalent to "walking around" the polygon edge visiting the vertices in order.

 

 

StepII    Overlap P/P test

 

Test if all the vertex  of one polygon equal to another polygon then polygons are overlapping and return

 

StepIII    touch P/P test

 

If the polygons are A(n edges) and B(m edges), atleast one vertex  of A lies on one of the edges of B.

So use Touches L/point   repeatedly for all edges of A or B(whichever has lesser edges) if one or more vertex pass this test. then use within Point/P test for those vertex of polygon who fail in previous test. If all the vertex fail in second test  then one polygon touch  another and return

 

Step IV  outside P/P test

 

 Use within Point/P test for one polygon if, all the vertex fail in this test then given polygons are disjoint and  return 

    

 

Step V   within P/P test

 Use withinPoint/P test for one polygon then use TouchPoint/P test for those vertex of polygon who fail in previous test. If vertex pass   second test     then one polygon lies within another and return

 

Step VI  intersection 

 

The sixth phase of the algorithm is computing and inserting the INTERSECTION points. If we have a SUBJECT polygon edge (SVi to SVi+1) that intersects a CLIP polygon edge (CVj to CVj+1) at a point INTER. Note that the edges form straight lines that may intersect, we are assuming that the line segments SVi - SVi+1 intersects the line segment CVj - CVj+1. The intersection point INTER is then inserted on BOTH of the linked lists - SUBJ and CLIP. It is inserted BETWEEN SVi and SVi+1 on the SUBJ list and CVj and CVj+1 on the CLIP list. The idea is still that traversing the list using a standard list traversal we would encounter the points in their geometric order. Note that there may be several intersection points between any given pair of vertices and they must be inserted in the correct order in the lists. Each intersection point thus has TWO nodes - one on each list (SUBJ and CLIP). We link these two entries together which provides a way of getting from one list to the other.

STEP VI. 1:

 

 

Any straight line divides the plane into two half-planes. Thus each polygon edge (extended to a line) will divide the plane into two half-planes. Because we listed the vertices clockwise, we consider the half-plane to the right as containing the interior of the polygon. Thus the right half-plane is called the interior half-plane. If we consider ourselves as "walking along" a polygon edge, then we can categorize each of the INTERSECTION points as "entering" or "exiting". This is usually done from the SUBJ polygon's point of view. Thus, as we walk along the SUBJ polygon edge SVi to SVi+1 and we encounter intersection point INTER, we can ask the question - am I "entering" the CLIP polygon or am I "exiting" the CLIP polygon? The second part of computing the intersection point is to classify them as "entering" or "exiting". We create one or two lists - one for entering intersections and one for exiting intersections.

 

 

 

STEP VI .2:

 

 

Once the lists are build the basic idea to do the clipping is as follows

Pick an entry from the ENTERING list - it will be an intersection point (and delete it)

Locate that point on the SUBJ list

Traverse the current (SUBJ) list until you find the next intersection point - it should be an exiting or entering point. Output each vertex encountered to some data structure, say POLY

Follow the link from the current (SUBJ) list to the other (CLIP) list and

Continue the traversal until you find the next intersection (if it is an entering intersection, delete from the ENTERING list).

Terminate the traversal when you get to an intersection that is the SAME as the initial one that you removed from the ENTERING list. At this point POLY will have one of the clip regions and can be output.

REPEAT the construction and output of POLY until the ENTERING list is empty.

Notation:

polygon to be clipped à SUBJ

polygon  against which clipping is performed à CLIP

resulting polygon : POLY

 list containing  incoming intersection point : ENTERING

list containing  exiting intersection point : EXITING

 

 

Flow chart:

yes

Terminate the traversal when you get to an intersection that is the SAME as the initial one that you removed from the ENTERING list.

 

 

 

 

 

 

 

IMPLEMENTATION:

 

In the below data structures we place all of the vertices and intersection points in a 1D array and use the subscript instead of the actual coordinates.

const int MAXVERT = 500;

const int MAXPOLYV = 50;

const int MAXH = 10;

struct Point2D

{float x,y;

};

typedef Point2D Vertices[MAXVERT];

enum VerType = {Polygon, Intersection};

typedef struct ClipListRec * ClipPtr;

struct ClipListRec

{ int Vindex;

  ClipPtr next;

  VerType Kind;

  float t;

  ClipPtr otherList;

}

struct Polygon

{ int nVertex;

  int vert[MAXPOLYV];

  ClipPtr list;

}

struct GenPolygon 

{ Polygon exterior;

  int numHoles;

  Polygon Holes[MAXH];

}

GenPolygon Sub,Clip;

int entering[MAXVERT],exiting[MAXVERT];

Vertices V;

int numVertex = 0;    // size of the array of verticies

int clipPoly[MAXVERT];  // a clip polygon

int readPoint();

{ cin >> inX;  cin >> inY;

  if (numVertex < MAXVERT)

  {  V[numVertex].x = inX;

     V[numVertex].y = inY;

      idNo = numVertex;

     numVertex++;

  }

  else

     idNo = -1;

  return idNo;

}

void readPolygon (GenPolygon p)

{ cin >> p.exterior.nVertex;

  for (i = 0; i < p.exterior.nVertex; i++)

  { newId = readPoint();

    if (newId < 0)

      error

    else

    { insertAtRear (p.exterior.list,newId);

      p.exterior.vert[i] = newId;

    }

  }

  // now do the holes basically the same way 

// the "main" program loop would then be (pseudocode)<

while (!EMPTY(entering))

{ nextInter = delete (entering);

  SEARCH (SubjectPolygon,nextInter,ptr1);

  AddToOutputList (ptr1-> ….)

  StartPoint = ptr1->….

  ptr1 = prt1->next;

  while (ptr1->…. != StartPoint)

  { AddToOutputList (ptr1->….);

    if (ptr1->…  ==  INTERSECTION)

      ptr1 = prt1->otherList->next;

    else

       ptr1 = ptr1->next;

  }

  FixListForOutput;

  DrawPolygon;

  EmptyOutputList

}

 

  

  

  

  

 
 

  

  

  

 
 

  

  

  

   

    

    

    
s2
    
    
   
  
   
 
 

  

 


 

Example:           

 

  

  

  

  

 
 

  

  

 
 

  

 
 

  

  

  

  

   

    

    

    
i2
    
    
   
  
   
 


 

 

  

 
 

  

  

  

   

    

    

    
C1
    
    
   
  
   
 


 

Given two polygon  one with four vertex  is  CLIP  polygon and  other polygon is SUBJ  polygon

Now we have these  link list

Step I

SUBJ:           s1, s2 , s3 , s4 , s5,  s6,  s7, s8, s9, s10, s11, s12

CLIP:          c1,c2,c3,c4

Step II

We calculate i1 as the first intersection point ,it is entering intersection point so it is also added into ENTER link list and we add this point into SUBJ and  CLIP  link list between those vertex which involve that intersection point i1

SUBJ:           s1, s2 , i1, s3 , s4 , s5,  s6,  s7, s8, s9, s10, s11, s12

CLIP:           c1, i1,c2,c3,c4

ENTER        i1

Then We calculate i2 as the first intersection point and we add this point into SUBJ and  CLIP  link list between those vertex which involve that intersection point i2 and NOTE it is the exiting point 

SUBJ:           s1, s2 , i1, s3 , s4 , s5,  s6,  s7, s8, i2, s9, s10, s11, s12

CLIP:           c1, i2,i1,c2,c3,c4

ENTER        i1

Step III

Now we pick i1 from ENTER  list and delete it from ENTER  list  and find it in SUBJ  list and traverse the SUBJ list until next intersection point is not found that is i2 and switch to CLIP  list bia the i2 pointer which point to same point in CLIP  list ,  and add all traversed point in to a list say POLY and now we are in CLIP list at i2 node

SUBJ:           s1, s2 , i1, s3 , s4 , s5,  s6,  s7, s8, i2, s9, s10, s11, s12

CLIP:           c1, i2,i1,c2,c3,c4

ENTER        i1

POLY          i1, s3 , s4 , s5,  s6,  s7, s8, i2

Step IV

Now traverse CLIP list from i2 and continue it until we find another intersection point becaz list  are doubly so in this case we find i1 and stop traverse CLIP  list 

Becaz  ENTER list is empty  so we stop. Now POLY  list contain the intersection area

That is 

POLY          i1, s3 , s4 , s5,  s6,  s7, s8, i2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Polygon Splitting algorithm:

 

A vector method for splitting concave polygon into convex polygon is to calculate the edge  vector cross product in counter clock wise and note  the sign of z component of each cross product  if the sign of z component turn to be negative then the polygon is concave  and we split polygon along the first edge vector of cross vector product

 

 

 

 

 

 

For example:

 

 

 

 

 

E5

 

	E6
		0				1		2		3

 

 

 

 

 

 

 

 

 

Say

E1 = (1,0,0),            E2 = (1,1,0)

E3 = (1,-1,0),           E4 = (1,2,0)

E5 = (-3,0,0),           E6 = (0,-2,0)

 

 

Now we have these cross product:

 

E1*E2=(0,0,1)

E2*E3=(0,0,-2)

E3*E4=(0,0,2)

E4*E5=(0,0,6)

E5*E6=(0,0,6)

E6*E1=(0,0,2)

 

In this example we see that z component is changing in second cross product so we split polygon along the E2 edge vector and find two convex polygon becaz no other z component sign change so we stop here

 

 

Flowchart

 

 

 

 

 

 

 

 

 

 

 

 

Algorithm for finding  the level point  of polygon:

 

 

 if polygon  is convex

then simply apply the method below

 

else

 if it is cocave

then split it into set of  convex polygons and compute the area of each  convex polygon and determine which one have greater area  and then apply centeriod method on that convex polygon   

 

Method  In calculating the area of a polygon  is based on Green's Theorem in a plane.  Given points (x_i, y_i), i = 0, ..., n, with x₀ = x_n and y₀ = y_n, the following formula can be used for rapidly calculating the area of a polygon in a plane:

where

The area computed this way is a signed value, where a negative sign indicates the vertices are in clockwise order and a positive sign indicates the vertices are in a counterclockwise order.

An interesting special case of this formula is for the triangle with the vertices (a,b), (c,d), (e,f), which can be written in compact form using the following matrix determinant:

The centroid and area can be computed at the same time.  The coordinates for the centroid

 

of a closed planar region R are:

 where

 

Flowchart:

 

 

 

 

 

 

 

 

 

 

7.     C++ Library Design

 

 

Classes:

 

Class  2DPoint

{

Private:
  float  x;

  float  y;

 

Public:
2DPoint();

~2DPoint();

int  IsCollinear(2DEdge *Edge);

int  Touch(2DEdge *Edge);

int  Touch(2DPoly *Poly);

int  Distance(2DEdge *Edge, float );

int  Within(2DPoly *Poly);

 

 

};

 

 

Class  2DLine

{

 

Public:

virtual int  IsCollinear(2Dpoint *point)=0;

virtual int  Touch(2Dpoint *point)=0;

virtual int  Distance(2Dpoint *point,float)=0;

virtual int  Touch(2DEdge *Edge2)=0;

virtual int  Cross(2DEdge *Edge2)=0;

virtual int  Within(2DEdge *Edge2)=0;

 

virtual int  Within(2DPoly *Poly)=0;

virtual int  Cross(2DPoly *Poly)=0;

virtual int  Touch(2DPoly *Poly)=0;

virtual int  Clip(2DPoly *Poly, 2DEdge *)=0;

virtual int  Midpoint(2Dpoint *)=0;

virtual int  insert_ edge(2DEdge *Edge)=0;

 

};

 

Class  2D _nonMuteEdge:Public 2DEdge

{

Private:
  int  PCount;

  2Dpoint  *poPoint;

 

 

Public:
  2D_nonMuteEdge();

~2D_nonMuteEdge();

int  Collinear(2DEdge *Edge, 2Dpoint *point;

int  Touch(2DEdge *Edge, 2Dpoint *point);

int  Distance(2DEdge *Edge, 2Dpoint *point);

int  Touch(2DEdge *Edge1, 2DEdge *Edge2);

int  Cross(2DEdge *Edge1, 2DEdge *Edge2);

int  Within(2DEdge *Edge1, 2DEdge *Edge2);

 

int  Within(2DEdge *Edge, 2DPoly *Poly);

int  Cross(2DEdge *Edge, 2DPoly *Poly);

int  Touch(2DEdge *Edge, 2DPoly *Poly);

int Clip(2DEdge *Edge, 2DPoly *Poly, 2DEdge *);

int  Midpoint(2DEdge *Edge, 2Dpoint *);

 int  insert_ edge(2DEdge *Edge);

 

};

 

 

Class  2D _MuteEdge:Public 2DEdge

{

Private:
 int  PCount;

  2Dpoint  *poPoint;

  2D _MuteEdge *next;

  2D _MuteEdge *pre;

 

Public:
  2D_MuteEdge();

~2D_MuteEdge();

int  Collinear(2DEdge *Edge, 2Dpoint *point;

int  Touch(2DEdge *Edge, 2Dpoint *point);

int  Distance(2DEdge *Edge, 2Dpoint *point);

int  Touch(2DEdge *Edge1, 2DEdge *Edge2);

int  Cross(2DEdge *Edge1, 2DEdge *Edge2);

int  Within(2DEdge *Edge1, 2DEdge *Edge2);

 

int  Within(2DEdge *Edge, 2DPoly *Poly);

int  Cross(2DEdge *Edge, 2DPoly *Poly);

int  Touch(2DEdge *Edge, 2DPoly *Poly);

int  Clip(2DEdge *Edge, 2DPoly *Poly, 2DEdge *);

int Midpoint(2DEdge *Edge, 2Dpoint *);

 int   insert_ edge(2DEdge *Edge);

 

};

 

 

Class  2DPoly

{

Private:
int  ECount;

2DEdge  **poEdge;

 

Public:
  2DPoly();

~2DPoly();

virtual int  Cross(2DEdge *Edge, 2DPoly *Poly)=0;

virtual int  Touch(2DPoly *Poly, 2DPoint *Point)=0;

virtual int  Touch(2DPoly *Poly1, 2DPoly *Poly2)=0;

virtual int  Within(2DEdge *Edge, 2DPoly *Poly)=0;

virtual int  Within(2DPoly *Poly, 2DPoint *Point)=0;

virtual int  Cross(2DEdge *Edge, 2DPoly *Poly)=0;

virtual int  Touch(2DEdge *Edge, 2DPoly *Poly)=0;

virtual  int Intersection(2DPoly *Poly1, 2DPoly *Poly2, 2DPoly *)=0;

virtual int  Union(2DPoly *Poly1, 2DPoly *Poly2, 2DPoly *)=0;

virtual int Clip(2DEdge *Edge, 2DPoly *Poly, 2DEdge *)=0;

virtual int Within(2DPoly *Poly1, 2DPoly *Poly2)=0;

virtual int Disjoint(2DPoly *Poly1, 2DPoly *Poly2)=0;

virtual int LevelPoint(2DPoly *Poly, 2Dpoint *)=0;

virtual int insert_poly(2DPoly *Poly)=0;

 

 

};

 

 

 

 

Class  2D_nonMutePoly:Public  2DPoly

{

Private:
int  ECount;

2D_nonMuteEdge  **poEdge;

 

Public:
  2D_nonMutePoly();

~2D_nonMutePoly();

 

 int  Cross(2D_Edge *Edge, 2DPoly *Poly);

 int  Touch(2DPoly *Poly, 2DPoint *Point);

 int  Touch(2DPoly *Poly1, 2DPoly *Poly2);

 int  Within(2DEdge *Edge, 2DPoly *Poly);

 int  Within(2DPoly *Poly, 2DPoint *Point);

 int  Cross(2DEdge *Edge, 2DPoly *Poly);

 int  Touch(2DEdge *Edge, 2DPoly *Poly);

 int Intersection(2DPoly *Poly1, 2DPoly *Poly2, 2DPoly *);

 int  Union(2DPoly *Poly1, 2DPoly *Poly2, 2DPoly *);

 int   Clip(2DEdge *Edge, 2DPoly *Poly, 2DEdge *);

 int Within(2DPoly *Poly1, 2DPoly *Poly2);

 int Disjoint(2DPoly *Poly1, 2DPoly *Poly2);

 

int   LevelPoint(2DPoly *Poly, 2Dpoint *);

 

 

};

 

 

 

Class  2D_MutePoly:Public  2DPoly

{

Private:
int  ECount;

2D_MuteEdge  **poEdge;

2D_MutePoly =*pre;

2D_MutePoly  =*next

Public:
  2D_MutePoly();

~2D_MutePoly();

 

 int  Cross(2DEdge *Edge, 2DPoly *Poly);

 int  Touch(2DPoly *Poly, 2DPoint *Point);

 int  Touch(2DPoly *Poly1, 2DPoly *Poly2);

 int  Within(2DEdge *Edge, 2DPoly *Poly);

 int  Within(2DPoly *Poly, 2DPoint *Point);

 int  Cross(2DEdge *Edge, 2DPoly *Poly);

 int  Touch(2DEdge *Edge, 2DPoly *Poly);

 int  Intersection(2DPoly *Poly1, 2DPoly *Poly2, 2DPoly *);

 int Union(2DPoly *Poly1, 2DPoly *Poly2, 2DPoly *);

 int Clip(2DEdge *Edge, 2DPoly *Poly, 2DEdge *);

 int Within(2DPoly *Poly1, 2DPoly *Poly2);

 int Disjoint(2DPoly *Poly1, 2DPoly *Poly2);

 int  LevelPoint(2DPoly *Poly, 2Dpoint *);

 int    insert_poly(2DPoly *Poly);

 

};

 

 

API

 

First API:

 

int   GeometryTest(OGRGeometry * inputobj1 , OGRGeometry * inputobj2 , char *

testcode, OGRGeometry * outputobj   )

 

this API will take   five parameter

 

four input parameter

1 output parameter

 

 

int: it will return these different values

 

 0       return false

 1       return true

 3       test fail

 

 

 OGRGeometry * inputobj1  it is the first input geometry object  

 

 OGRGeometry * inputobj2  it is the second input geometry object  

 

 these both can be

  Point

  line

  polygon

 

char * testcode  it is input test parameter it can hold following values

 

Touch

Distance

Within

Cross

Intersect

clip

Overlap

             distance

             Disjoint

             Union

        OGRGeometry * outputobj

       

           It will hold resulting Geometry

 

Second  API

 

int   geometryoperation(OGRGeometry * inputobj , char *

opcode  )

 

int: it will return these different values

 

value     return some integer value

0           test fail

 

 OGRGeometry * inputobj    it is the  input geometry object

 

Which may be Line  or polygon

 

char * opcode  it is input operation parameter it can hold “level point”,”mid point “ value