kig/objects/polygon_imp.cc

   1 // Copyright (C)  2004  Pino Toscano <toscano.pino@tiscali.it>
   2
   3 // This program is free software; you can redistribute it and/or
   4 // modify it under the terms of the GNU General Public License
   5 // as published by the Free Software Foundation; either version 2
   6 // of the License, or (at your option) any later version.
   7
   8 // This program is distributed in the hope that it will be useful,
   9 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  10 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11 // GNU General Public License for more details.
  12
  13 // You should have received a copy of the GNU General Public License
  14 // along with this program; if not, write to the Free Software
  15 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  16 // 02111-1307, USA.
  17
  18 #include "polygon_imp.h"
  19
  20 #include "bogus_imp.h"
  21 #include "line_imp.h"
  22 #include "point_imp.h"
  23
  24 #include "../misc/common.h"
  25 #include "../misc/coordinate.h"
  26 #include "../misc/kigpainter.h"
  27 #include "../misc/kigtransform.h"
  28
  29 #include "../kig/kig_document.h"
  30 #include "../kig/kig_view.h"
  31
  32 #include <klocale.h>
  33
  34 #include <cmath>
  35
  36 PolygonImp::PolygonImp( uint npoints, const std::vector<Coordinate>& points,
  37                         const Coordinate& centerofmass )
  38   : mnpoints( npoints ), mpoints( points ), mcenterofmass( centerofmass )
  39 {
  40 //  mpoints = points;
  41 }
  42
  43 PolygonImp::PolygonImp( const std::vector<Coordinate>& points )
  44 {
  45   uint npoints = points.size();
  46   Coordinate centerofmassn = Coordinate( 0, 0 );
  47
  48   for ( uint i = 0; i < npoints; ++i )
  49   {
  50     centerofmassn += points[i];
  51   }
  52   mpoints = points;
  53   mcenterofmass = centerofmassn/npoints;
  54   mnpoints = npoints;
  55 }
  56
  57 PolygonImp::~PolygonImp()
  58 {
  59 }
  60
  61 Coordinate PolygonImp::attachPoint() const
  62 {
  63   return mcenterofmass;
  64 }
  65
  66 ObjectImp* PolygonImp::transform( const Transformation& t ) const
  67 {
  68 /*mp:
  69  * any projective transformation makes sense for a polygon,
  70  * since segments transform into segments (but see below...)
  71  * of course regular polygons will no longer be
  72  * regular if t is not homothetic.
  73  * for projective transformations the polygon could transform to
  74  * an unbounded nonconnected polygon; this happens if some side
  75  * of the polygon crosses the critical line that maps to infinity
  76  * this can be easily checked using the getProjectiveIndicator
  77  * function
  78  */
  79 //  if ( ! t.isHomothetic() )
  80 //    return new InvalidImp();
  81
  82   if ( ! t.isAffine() )     /* in this case we need a more extensive test */
  83   {
  84     double maxp = -1.0;
  85     double minp = 1.0;
  86     for ( uint i = 0; i < mpoints.size(); ++i )
  87     {
  88       double p = t.getProjectiveIndicator( mpoints[i] );
  89       if ( p > maxp ) maxp = p;
  90       if ( p < minp ) minp = p;
  91     }
  92     if ( maxp > 0 && minp < 0 ) return new InvalidImp;
  93   }
  94   std::vector<Coordinate> np;
  95   for ( uint i = 0; i < mpoints.size(); ++i )
  96   {
  97     Coordinate nc = t.apply( mpoints[i] );
  98     if ( !nc.valid() )
  99       return new InvalidImp;
 100     np.push_back( nc );
 101   }
 102   return new PolygonImp( np );
 103 }
 104
 105 void PolygonImp::draw( KigPainter& p ) const
 106 {
 107   p.drawPolygon( mpoints );
 108 }
 109
 110 bool PolygonImp::isInPolygon( const Coordinate& p ) const
 111 {
 112   // (algorithm sent to me by domi)
 113   // We intersect with the horizontal ray from point to the right and
 114   // count the number of intersections.  That, along with some
 115   // minor optimalisations of the intersection test..
 116   bool inside_flag = false;
 117   double cx = p.x;
 118   double cy = p.y;
 119
 120   Coordinate prevpoint = mpoints.back();
 121   bool prevpointbelow = mpoints.back().y >= cy;
 122   for ( uint i = 0; i < mpoints.size(); ++i )
 123   {
 124     Coordinate point = mpoints[i];
 125     bool pointbelow = point.y >= cy;
 126     if ( prevpointbelow != pointbelow )
 127     {
 128       // possibility of intersection: points on different side from
 129       // the X axis
 130       //bool rightofpt = point.x >= cx;
 131       // mp: we need to be a little bit more conservative here, in
 132       // order to treat properly the case when the point is on the
 133       // boundary
 134       //if ( rightofpt == ( prevpoint.x >= cx ) )
 135       if ( ( point.x - cx )*(prevpoint.x - cx ) > 0 )
 136       {
 137         // points on same side of Y axis -> easy to test intersection
 138         // intersection iff one point to the right of c
 139         if ( point.x >= cx )
 140           inside_flag = !inside_flag;
 141       }
 142       else
 143       {
 144         // points on different sides of Y axis -> we need to calculate
 145         // the intersection.
 146         // mp: we want to check if the point is on the boundary, and
 147         // return false in such case
 148         double num = ( point.y - cy )*( prevpoint.x - point.x );
 149         double den = prevpoint.y - point.y;
 150         if ( num == den*( point.x - cx ) ) return false;
 151         if ( num/den <= point.x - cx )
 152           inside_flag = !inside_flag;
 153       }
 154     }
 155     prevpoint = point;
 156     prevpointbelow = pointbelow;
 157   }
 158   return inside_flag;
 159 }
 160 #define selectpolygonwithinside 1
 161 #ifdef selectpolygonwithinside
 162 bool PolygonImp::contains( const Coordinate& p, int, const KigWidget& ) const
 163 {
 164   return isInPolygon( p );
 165 }
 166 #else
 167 bool PolygonImp::contains( const Coordinate& p, int width, const KigWidget& w ) const
 168 {
 169   bool ret = false;
 170   uint reduceddim = mpoints.size() - 1;
 171   for ( uint i = 0; i < reduceddim; ++i )
 172   {
 173     ret |= isOnSegment( p, mpoints[i], mpoints[i+1], w.screenInfo().normalMiss( width ) );
 174   }
 175   ret |= isOnSegment( p, mpoints[reduceddim], mpoints[0], w.screenInfo().normalMiss( width ) );
 176
 177   return ret;
 178 }
 179 #endif
 180
 181 bool PolygonImp::inRect( const Rect& r, int width, const KigWidget& w ) const
 182 {
 183   bool ret = false;
 184   uint reduceddim = mpoints.size() - 1;
 185   for ( uint i = 0; i < reduceddim; ++i )
 186   {
 187     SegmentImp* s = new SegmentImp( mpoints[i], mpoints[i+1] );
 188     ret |= lineInRect( r, mpoints[i], mpoints[i+1], width, s, w );
 189     delete s;
 190     s = 0;
 191   }
 192   SegmentImp* t = new SegmentImp( mpoints[reduceddim], mpoints[0] );
 193   ret |= lineInRect( r, mpoints[reduceddim], mpoints[0], width, t, w );
 194   delete t;
 195   t = 0;
 196
 197   return ret;
 198 }
 199
 200 bool PolygonImp::valid() const
 201 {
 202   return true;
 203 }
 204
 205 const uint PolygonImp::numberOfProperties() const
 206 {
 207   return Parent::numberOfProperties() + 5;
 208 }
 209
 210 const QCStringList PolygonImp::propertiesInternalNames() const
 211 {
 212   QCStringList l = Parent::propertiesInternalNames();
 213   l += "polygon-number-of-sides";
 214   l += "polygon-perimeter";
 215   l += "polygon-surface";
 216   l += "polygon-center-of-mass";
 217   l += "polygon-winding-number";
 218   assert( l.size() == PolygonImp::numberOfProperties() );
 219   return l;
 220 }
 221
 222 const QCStringList PolygonImp::properties() const
 223 {
 224   QCStringList l = Parent::properties();
 225   l += I18N_NOOP( "Number of sides" );
 226   l += I18N_NOOP( "Perimeter" );
 227   l += I18N_NOOP( "Surface" );
 228   l += I18N_NOOP( "Center of Mass of the Vertices" );
 229   l += I18N_NOOP( "Winding Number" );
 230   assert( l.size() == PolygonImp::numberOfProperties() );
 231   return l;
 232 }
 233
 234 const ObjectImpType* PolygonImp::impRequirementForProperty( uint which ) const
 235 {
 236   if ( which < Parent::numberOfProperties() )
 237     return Parent::impRequirementForProperty( which );
 238   else return PolygonImp::stype();
 239 }
 240
 241 const char* PolygonImp::iconForProperty( uint which ) const
 242 {
 243   assert( which < PolygonImp::numberOfProperties() );
 244   if ( which < Parent::numberOfProperties() )
 245     return Parent::iconForProperty( which );
 246   else if ( which == Parent::numberOfProperties() )
 247     return "en"; // number of sides
 248   else if ( which == Parent::numberOfProperties() + 1 )
 249     return "circumference"; // perimeter
 250   else if ( which == Parent::numberOfProperties() + 2 )
 251     return "areaCircle"; // surface
 252   else if ( which == Parent::numberOfProperties() + 3 )
 253     return "point"; // center of mass
 254   else if ( which == Parent::numberOfProperties() + 4 )
 255     return "w"; // winding number
 256   else assert( false );
 257   return "";
 258 }
 259
 260 ObjectImp* PolygonImp::property( uint which, const KigDocument& w ) const
 261 {
 262   assert( which < PolygonImp::numberOfProperties() );
 263   if ( which < Parent::numberOfProperties() )
 264     return Parent::property( which, w );
 265   else if ( which == Parent::numberOfProperties() )
 266   {
 267     // number of points
 268     return new IntImp( mnpoints );
 269   }
 270   else if ( which == Parent::numberOfProperties() + 1)
 271   {
 272     double circumference = 0.;
 273     // circumference
 274     for ( uint i = 0; i < mpoints.size(); ++i )
 275     {
 276       uint prev = ( i + mpoints.size() - 1 ) % mpoints.size();
 277       circumference += ( mpoints[i] - mpoints[prev] ).length();
 278     }
 279     return new DoubleImp( circumference );
 280   }
 281   else if ( which == Parent::numberOfProperties() + 2)
 282   {
 283     int wn = windingNumber ();  // not able to compute area for such polygons...
 284     if ( wn < 0 ) wn = -wn;
 285     if ( wn != 1 ) return new InvalidImp;
 286     double surface2 = 0.0;
 287     Coordinate prevpoint = mpoints.back();
 288     for ( uint i = 0; i < mpoints.size(); ++i )
 289     {
 290       Coordinate point = mpoints[i];
 291       surface2 += ( point.x - prevpoint.x ) * ( point.y + prevpoint.y );
 292       prevpoint = point;
 293     }
 294     return new DoubleImp( fabs( surface2 / 2 ) );
 295   }
 296   else if ( which == Parent::numberOfProperties() + 3 )
 297   {
 298     return new PointImp( mcenterofmass );
 299   }
 300   else if ( which == Parent::numberOfProperties() + 4 )
 301   {
 302     // winding number
 303     return new IntImp( windingNumber() );
 304   }
 305   else assert( false );
 306   return new InvalidImp;
 307 }
 308
 309 const std::vector<Coordinate> PolygonImp::points() const
 310 {
 311   std::vector<Coordinate> np;
 312   np.reserve( mpoints.size() );
 313   std::copy( mpoints.begin(), mpoints.end(), std::back_inserter( np ) );
 314   return np;
 315 }
 316
 317 const uint PolygonImp::npoints() const
 318 {
 319   return mnpoints;
 320 }
 321
 322 PolygonImp* PolygonImp::copy() const
 323 {
 324   return new PolygonImp( mpoints );
 325 }
 326
 327 void PolygonImp::visit( ObjectImpVisitor* vtor ) const
 328 {
 329   vtor->visit( this );
 330 }
 331
 332 bool PolygonImp::equals( const ObjectImp& rhs ) const
 333 {
 334   return rhs.inherits( PolygonImp::stype() ) &&
 335     static_cast<const PolygonImp&>( rhs ).points() == mpoints;
 336 }
 337
 338 const ObjectImpType* PolygonImp::stype()
 339 {
 340   static const ObjectImpType t(
 341     Parent::stype(), "polygon",
 342     I18N_NOOP( "polygon" ),
 343     I18N_NOOP( "Select this polygon" ),
 344     I18N_NOOP( "Select polygon %1" ),
 345     I18N_NOOP( "Remove a Polygon" ),
 346     I18N_NOOP( "Add a Polygon" ),
 347     I18N_NOOP( "Move a Polygon" ),
 348     I18N_NOOP( "Attach to this polygon" ),
 349     I18N_NOOP( "Show a Polygon" ),
 350     I18N_NOOP( "Hide a Polygon" )
 351     );
 352
 353   return &t;
 354 }
 355
 356 const ObjectImpType* PolygonImp::stype3()
 357 {
 358   static const ObjectImpType t3(
 359     PolygonImp::stype(), "triangle",
 360     I18N_NOOP( "triangle" ),
 361     I18N_NOOP( "Select this triangle" ),
 362     I18N_NOOP( "Select triangle %1" ),
 363     I18N_NOOP( "Remove a Triangle" ),
 364     I18N_NOOP( "Add a Triangle" ),
 365     I18N_NOOP( "Move a Triangle" ),
 366     I18N_NOOP( "Attach to this triangle" ),
 367     I18N_NOOP( "Show a Triangle" ),
 368     I18N_NOOP( "Hide a Triangle" )
 369     );
 370
 371   return &t3;
 372 }
 373
 374 const ObjectImpType* PolygonImp::stype4()
 375 {
 376   static const ObjectImpType t4(
 377     PolygonImp::stype(), "quadrilateral",
 378     I18N_NOOP( "quadrilateral" ),
 379     I18N_NOOP( "Select this quadrilateral" ),
 380     I18N_NOOP( "Select quadrilateral %1" ),
 381     I18N_NOOP( "Remove a Quadrilateral" ),
 382     I18N_NOOP( "Add a Quadrilateral" ),
 383     I18N_NOOP( "Move a Quadrilateral" ),
 384     I18N_NOOP( "Attach to this quadrilateral" ),
 385     I18N_NOOP( "Show a Quadrilateral" ),
 386     I18N_NOOP( "Hide a Quadrilateral" )
 387     );
 388
 389   return &t4;
 390 }
 391
 392 const ObjectImpType* PolygonImp::type() const
 393 {
 394   uint n = mpoints.size();
 395
 396   if ( n == 3 ) return PolygonImp::stype3();
 397   if ( n == 4 ) return PolygonImp::stype4();
 398   return PolygonImp::stype();
 399 }
 400
 401 bool PolygonImp::isPropertyDefinedOnOrThroughThisImp( uint which ) const
 402 {
 403   assert( which < PolygonImp::numberOfProperties() );
 404   if ( which < Parent::numberOfProperties() )
 405     return Parent::isPropertyDefinedOnOrThroughThisImp( which );
 406   return false;
 407 }
 408
 409 Rect PolygonImp::surroundingRect() const
 410 {
 411   Rect r( 0., 0., 0., 0. );
 412   for ( uint i = 0; i < mpoints.size(); ++i )
 413   {
 414     r.setContains( mpoints[i] );
 415   }
 416   return r;
 417 }
 418
 419 int PolygonImp::windingNumber() const
 420 {
 421   /*
 422    * this is defined as the sum of the external angles while at
 423    * all vertices, then normalized by 2pi.  The external angle
 424    * is the angle we steer at each vertex while we walk along the
 425    * boundary of the polygon.
 426    * In the end we only need to count how many time we cross the (1,0)
 427    * direction (positive x-axis) with a positive sign if we cross while
 428    * steering left and a negative sign viceversa
 429    */
 430
 431   int winding = 0;
 432   uint npoints = mpoints.size();
 433   Coordinate prevside = mpoints[0] - mpoints[npoints-1];
 434   for ( uint i = 0; i < npoints; ++i )
 435   {
 436     uint nexti = i + 1;
 437     if ( nexti >= npoints ) nexti = 0;
 438     Coordinate side = mpoints[nexti] - mpoints[i];
 439     double vecprod = side.x*prevside.y - side.y*prevside.x;
 440     int steeringdir = ( vecprod > 0 ) ? 1 : -1;
 441     if ( vecprod == 0.0 || side.y*prevside.y > 0 )
 442     {
 443       prevside = side;
 444       continue;   // cannot cross the (1,0) direction
 445     }
 446     if ( side.y*steeringdir < 0 && prevside.y*steeringdir >= 0 )
 447       winding -= steeringdir;
 448     prevside = side;
 449   }
 450   return winding;
 451 }
 452
 453 bool PolygonImp::isMonotoneSteering() const
 454 {
 455   /*
 456    * returns true if while walking along the boundary,
 457    * steering is always in the same direction
 458    */
 459
 460   uint npoints = mpoints.size();
 461   Coordinate prevside = mpoints[0] - mpoints[npoints-1];
 462   int prevsteeringdir = 0;
 463   for ( uint i = 0; i < npoints; ++i )
 464   {
 465     uint nexti = i + 1;
 466     if ( nexti >= npoints ) nexti = 0;
 467     Coordinate side = mpoints[nexti] - mpoints[i];
 468     double vecprod = side.x*prevside.y - side.y*prevside.x;
 469     int steeringdir = ( vecprod > 0 ) ? 1 : -1;
 470     if ( vecprod == 0.0 )
 471     {
 472       prevside = side;
 473       continue;   // going straight
 474     }
 475     if ( prevsteeringdir*steeringdir < 0 ) return false;
 476     prevside = side;
 477     prevsteeringdir = steeringdir;
 478   }
 479   return true;
 480 }
 481
 482 bool PolygonImp::isConvex() const
 483 {
 484   if ( ! isMonotoneSteering() ) return false;
 485   int winding = windingNumber();
 486   if ( winding < 0 ) winding = -winding;
 487   assert ( winding > 0 );
 488   return winding == 1;
 489 }
 490
 491 std::vector<Coordinate> computeConvexHull( const std::vector<Coordinate>& points )
 492 {
 493   /*
 494    * compute the convex hull of the set of points, the resulting list
 495    * is the vertices of the resulting polygon listed in a counter clockwise
 496    * order.  This algorithm is on order n^2, probably suboptimal, but
 497    * we don't expect to have large values for n.
 498    */
 499
 500   if ( points.size() < 3 ) return points;
 501   std::vector<Coordinate> worklist = points;
 502   std::vector<Coordinate> result;
 503
 504   double ymin = worklist[0].y;
 505   uint imin = 0;
 506   for ( uint i = 1; i < worklist.size(); ++i )
 507   {
 508     if ( worklist[i].y < ymin )
 509     {
 510       ymin = worklist[i].y;
 511       imin = i;
 512     }
 513   }
 514
 515   // worklist[imin] is definitely on the convex hull, let's start from there
 516   result.push_back( worklist[imin] );
 517   Coordinate startpoint = worklist[imin];
 518   Coordinate apoint = worklist[imin];
 519   double aangle = 0.0;
 520
 521   while ( ! worklist.empty() )
 522   {
 523     int besti = -1;
 524     double anglemin = 10000.0;
 525     for ( uint i = 0; i < worklist.size(); ++i )
 526     {
 527       if ( worklist[i] == apoint ) continue;
 528       Coordinate v = worklist[i] - apoint;
 529       double angle = std::atan2( v.y, v.x );
 530       while ( angle < aangle ) angle += 2*M_PI;
 531       if ( angle < anglemin )
 532       {   // found a better point
 533         besti = i;
 534         anglemin = angle;
 535       }
 536     }
 537
 538     if ( besti < 0 ) return result;   // this happens, e.g. if all points coincide
 539     apoint = worklist[besti];
 540     aangle = anglemin;
 541     if ( apoint == startpoint )
 542     {
 543       return result;
 544     }
 545     result.push_back( apoint );
 546     worklist.erase( worklist.begin() + besti, worklist.begin() + besti + 1 );
 547   }
 548   assert( false );
 549   return result;
 550 }