Advanced Strategic Command: polygontriangulation.h Source File

00001 
00005 //     $Id: polygontriangulation.h,v 1.5 2007-04-13 16:15:54 mbickel Exp $
00006 /*
00007     This file is part of Advanced Strategic Command; http://www.asc-hq.de
00008     Copyright (C) 1994-1999  Martin Bickel  and  Marc Schellenberger
00009 
00010     This program is free software; you can redistribute it and/or modify
00011     it under the terms of the GNU General Public License as published by
00012     the Free Software Foundation; either version 2 of the License, or
00013     (at your option) any later version.
00014 
00015     This program is distributed in the hope that it will be useful,
00016     but WITHOUT ANY WARRANTY; without even the implied warranty of
00017     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00018     GNU General Public License for more details.
00019 
00020     You should have received a copy of the GNU General Public License
00021     along with this program; see the file COPYING. If not, write to the
00022     Free Software Foundation, Inc., 59 Temple Place, Suite 330,
00023     Boston, MA  02111-1307  USA
00024 */
00025 
00026 #ifndef polygontriangulationH
00027  #define polygontriangulationH
00028 
00029  #include <math.h>
00030  #include <sys/types.h>
00031  #include <stdlib.h>
00032  #include <stdio.h>
00033 
00034  namespace PolygonTriangulationLibrary {
00035  #include "libs/triangul/interfac.h"
00036  #include "libs/triangul/triangul.h"
00037  };
00038 
00039 template <class Poly>
00040 class  PolygonPainter {
00041          public:
00042              bool  paintPolygon ( const Poly& poly );
00043          protected:
00044              virtual void   sortpolygon    ( Poly& a );
00045              virtual void   painttriangle  ( typename Poly::Point p[] );
00046              virtual void   painthorizline ( int x1, int x2, int y );
00047              virtual void   paintline      ( int x1, int y1, int x2, int y2 );
00048              virtual void   setpoint       ( int x,  int y  ) = 0;
00049              virtual int    getpolydir     ( const Poly& a);
00050              virtual double getsegmentdir  ( int dx, int dy );
00052              virtual bool checkpolygon   ( const Poly& poly );
00054              virtual bool checkline      ( typename Poly::Point a, typename Poly::Point b, typename Poly::Point d, typename Poly::Point e );
00055              virtual ~PolygonPainter() {};
00056           };
00057 
00058 template <class Poly>
00059 bool  PolygonPainter<Poly>::paintPolygon ( const Poly& poly )
00060 {
00061    if ( !poly.vertex.size() )
00062       return true;
00063 
00064 //   displayLogMessage ( 10, "pp1 ");
00065    if (checkpolygon ( poly )) {
00066       if ( poly.vertex.size() == 1 ) {
00067          setpoint ( poly.vertex[0].x, poly.vertex[0].y );
00068          return true;
00069        }
00070        if ( poly.vertex.size() == 2 ) {
00071          paintline ( poly.vertex[0].x, poly.vertex[0].y, poly.vertex[1].x, poly.vertex[1].y  );
00072          return true;
00073        }
00074 
00075 //       displayLogMessage ( 10, "pp2 ");
00076        Poly pol2 = poly;
00077        sortpolygon ( pol2 );
00078 
00079 
00080        typedef double double2[2];
00081        double2*  floatpoints = new double2 [ pol2.vertex.size()+1 ];
00082        for ( int i=0; i<pol2.vertex.size() ; i++ ) {
00083           floatpoints[i+1][0] = (double) pol2.vertex[i].x;
00084           floatpoints[i+1][1] = (double) pol2.vertex[i].y;
00085        } /* endfor */
00086 
00087        typedef int int3[3];
00088 
00089        int3* triangles = new int3  [ pol2.vertex.size() ];
00090 
00091        int contours = pol2.vertex.size();
00092 
00093 //       displayLogMessage ( 10, "pp3 ");
00094        PolygonTriangulationLibrary::triangulate_polygon ( 1, &contours, floatpoints, triangles );
00095 //       displayLogMessage ( 10, "pp4 ");
00096 
00097        for ( int i=0; i<pol2.vertex.size()-2 ;i++ ) {
00098           typename Poly::Point tripos[3];
00099           tripos[0] = pol2.vertex[triangles[i][0]-1];
00100           tripos[1] = pol2.vertex[triangles[i][1]-1];
00101           tripos[2] = pol2.vertex[triangles[i][2]-1];
00102           painttriangle ( tripos );
00103        } /* endfor */
00104 
00105        delete[] triangles;
00106        delete[] floatpoints;
00107 
00108        return true;
00109    } else
00110      return false;
00111 }
00112 
00113 static const double pi = 3.141592654;
00114 
00115 
00116 template <class Poly>
00117 bool PolygonPainter<Poly>::checkline( typename Poly::Point a, typename Poly::Point b, typename Poly::Point d, typename Poly::Point e )
00118 {
00119    double r,s,t;
00120 
00121    b.x -= a.x;
00122    b.y -= a.y;
00123 
00124    e.x -= d.x;
00125    e.y -= d.y;
00126 
00127    /*
00128    if ( b.y != 0 && e.y != 0 ) {
00129       if ( abs( b.x / b.y - e.x / e.y ) < 1e-6 )
00130          return false;
00131    } else
00132       if ( b.y == 0 && e.y == 0 )
00133          return false;
00134    */
00135 
00136 
00137    t = b.x * e.y - b.y * e.x;
00138    if (t != 0) {
00139      double m = ( a.x * b.y - a.y * b.x + d.y * b.x - d.x * b.y );
00140      r = m / -t;
00141 
00142      double n = ( a.y * e.x - a.x * e.y + d.x * e.y - d.y * e.x );
00143      s = n / t;
00144      if ( s>=0 && s <= 1  &&  r>=0 && r <= 1)
00145         return false;
00146 
00147    } /* endif */
00148    return true;
00149 }
00150 
00151 
00152 template <class Poly>
00153 bool PolygonPainter<Poly>::checkpolygon   ( const Poly& poly )
00154 {
00155     if ( poly.vertex.size() > 1  && poly.vertex.size() < 3 )
00156        return true;
00157     else {
00158        size_t i,j,k;
00159 
00160        for ( i = 0; i < poly.vertex.size(); i++ )
00161           for ( j = 0; j < poly.vertex.size(); j++ )
00162              if ( i != j )
00163                if ( poly.vertex[i].x == poly.vertex[j].x  &&
00164                     poly.vertex[i].y == poly.vertex[j].y )
00165                   return false;
00166 
00167        k = poly.vertex.size() -1;
00168        for (i=0; i < k ; i++) {
00169           for (j = i +2; j < k ; j++)
00170               if (checkline ( poly.vertex[i], poly.vertex[i+1], poly.vertex[j], poly.vertex[j+1] ) == false)
00171                   return false;
00172           if (i > 0 && j == k)
00173             if (checkline ( poly.vertex[i], poly.vertex[i+1], poly.vertex[j], poly.vertex[0] ) == false)
00174                return false;
00175        } /* endfor */
00176        return true;
00177     }
00178 }
00179 
00180 
00181 
00182 template <class Poly>
00183 double  PolygonPainter<Poly>::getsegmentdir   ( int dx, int dy )
00184 {
00185    double alpha;
00186 
00187    if (dx) {
00188       alpha = atan ( (double) dy / (double) dx );
00189       if ( dy < 0 ) {
00190          if ( dx < 0)
00191             alpha = -pi + alpha;
00192       } else
00193         if ( dx < 0)
00194            alpha = pi - alpha;
00195 
00196    } else {
00197       if (dy > 0)
00198          alpha = pi/2;
00199       else
00200          alpha = -pi/2;
00201    } /* endif */
00202 
00203    return alpha;
00204 }
00205 
00206 template <class Poly>
00207 int PolygonPainter<Poly>::getpolydir     ( const Poly& a)
00208 {
00209     int p ;
00210     double alpha, beta, gamma;
00211     int   r = 0;
00212     for (p=0; p< a.vertex.size(); p++) {
00213 
00214        if (p == 0)
00215           alpha = getsegmentdir( a.vertex[p].x - a.vertex[a.vertex.size()-1].x , a.vertex[p].y - a.vertex[a.vertex.size()-1].y );
00216        else
00217           alpha = getsegmentdir( a.vertex[p].x - a.vertex[p-1].x, a.vertex[p].y - a.vertex[p-1].y );
00218 
00219        if (p+1 >= a.vertex.size())
00220           beta =  getsegmentdir( a.vertex[0].x - a.vertex[p].x , a.vertex[0].y - a.vertex[p].y  );
00221        else
00222           beta =  getsegmentdir( a.vertex[p+1].x - a.vertex[p].x,  a.vertex[p+1].y - a.vertex[p].y );
00223 
00224        gamma = beta - alpha ;
00225        if (gamma > pi)
00226           gamma = pi - gamma;
00227        if (gamma < -pi)
00228           gamma = -pi - gamma;
00229        r+= (int) ( gamma * 1000 );
00230     }
00231     return r;
00232 }
00233 
00234 
00235 template <class Poly>
00236 void PolygonPainter<Poly>::sortpolygon   ( Poly& a )
00237 {
00238    if ( a.vertex.size() >= 3 )
00239       if ( getpolydir(a) < 0 ) {
00240          for ( int i=0;i< a.vertex.size()/2 ;i++ ) {
00241             typename Poly::Point p = a.vertex[i];
00242             a.vertex[i] = a.vertex[a.vertex.size()-i-1];
00243             a.vertex[a.vertex.size()-i-1] = p;
00244          } /* endfor */
00245       }
00246 }
00247 
00248 
00249 template <class Poly>
00250 void PolygonPainter<Poly>::painttriangle  ( typename Poly::Point p[] )
00251 {
00252    int x,y,dx1,dx2,dy1,dy2;
00253 
00254    for ( int i=0; i<2 ; ) {
00255       if ( p[i+1].y < p[i].y || ( p[i+1].y == p[i].y && p[i+1].x < p[i].x )) {
00256          x        = p[i].x;
00257          p[i].x   = p[i+1].x;
00258          p[i+1].x = x;
00259          y        = p[i].y;
00260          p[i].y   = p[i+1].y;
00261          p[i+1].y = y;
00262          i        = 0;
00263        } else
00264          i++;
00265 
00266    } /* endfor */
00267 
00268 
00269    if ( p[0].y < p[1].y ) {
00270       dx1 = p[1].x - p[0].x;
00271       dx2 = p[2].x - p[0].x;
00272       dy1 = p[1].y - p[0].y;
00273       dy2 = p[2].y - p[0].y;
00274 
00275       for (y=p[0].y; y<=p[1].y ; y++)
00276           painthorizline ( p[0].x + dx1 * (y - p[0].y) / dy1 , p[0].x + dx2 * (y - p[0].y) / dy2, y );
00277 
00278       if (p[1].y < p[2].y) {
00279          dx1 = p[2].x - p[1].x;
00280          dy1 = p[2].y - p[1].y;
00281 
00282          for ( ; y<=p[2].y ; y++)
00283              painthorizline ( p[1].x + dx1 * (y - p[1].y) / dy1 , p[0].x + dx2 * (y - p[0].y) / dy2, y );
00284       }
00285    } else {
00286       if ( p[1].y < p[2].y ) {
00287 
00288          dx1 = p[2].x - p[1].x;
00289          dx2 = p[2].x - p[0].x;
00290          dy1 = p[2].y - p[0].y;
00291 
00292          for (y=p[0].y; y<=p[2].y ; y++)
00293              painthorizline ( p[1].x + dx1 * (y - p[0].y) / dy1 , p[0].x + dx2 * (y - p[0].y) / dy1, y );
00294       } else
00295         painthorizline ( p[0].x, p[2].x, p[0].y );
00296    }
00297 
00298 }
00299 
00300 
00301 template <class Poly>
00302 void   PolygonPainter<Poly>::painthorizline ( int x1, int x2, int y )
00303 {
00304    int dx;
00305    if (x1 > x2)
00306       dx = -1;
00307    else
00308       if (x1 < x2)
00309          dx = 1;
00310       else {
00311          setpoint ( x2, y );
00312          return;
00313       }
00314 
00315    int x= x1;
00316 
00317    do {
00318       setpoint ( x, y );
00319       x += dx;
00320    } while ( x != x2 ); /* enddo */
00321    setpoint ( x, y );
00322 }
00323 
00324 
00325 template <class Poly>
00326 void   PolygonPainter<Poly>::paintline   ( int x1, int y1, int x2, int y2 )
00327 {
00328         float           m, b;
00329         int             w;
00330         float           yy1, yy2, xx1, xx2;
00331 
00332 
00333 
00334     if ( x1 == x2) {
00335         for (w=y1;w<=y2 ;w++ )
00336            setpoint ( x1, w );
00337     } else {
00338        if ( y1 == y2) {
00339           for (w=x1;w<=x2 ;w++ )
00340                setpoint( w, y1 );
00341        } else {
00342                 yy1 = y1;
00343                 yy2 = y2;
00344                 xx1 = x1;
00345                 xx2 = x2;
00346                 m = (yy2 - yy1) / (xx2 - xx1);
00347                 b = y1 - m * x1;
00348                 if ((m <= 1) && (m >= -1)) {
00349                         if (x2 < x1) {
00350                                 w = x2;
00351                                 x2 = x1;
00352                                 x1 = w;
00353                                 w = y2;
00354                                 y2 = y1;
00355                                 y1 = w;
00356                         }
00357                         for (w = x1; w <= x2; w++)
00358                                 setpoint(w, (int) (m * w + b) );
00359 
00360                 } else {
00361                         if (y2 < y1) {
00362                                 w = x2;
00363                                 x2 = x1;
00364                                 x1 = w;
00365                                 w = y2;
00366                                 y2 = y1;
00367                                 y1 = w;
00368                         }
00369                         for (w = y1; w <= y2; w++) {
00370                                 setpoint( (int) ((w - b) / m), w );
00371                         }
00372 
00373                 }
00374          } /* endif */
00375     }
00376 }
00377 
00378 
00379 
00380 
00381 
00382 #endif