kig/objects/locus_imp.cc

   1 // Copyright (C)  2003  Dominique Devriese <devriese@kde.org>
   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 "locus_imp.h"
  19
  20 #include "bogus_imp.h"
  21 #include "point_imp.h"
  22 #include "../misc/object_hierarchy.h"
  23 #include "../misc/kigpainter.h"
  24 #include "../misc/coordinate.h"
  25 #include "../misc/common.h"
  26
  27 #include "../kig/kig_view.h"
  28
  29 #include <klocale.h>
  30
  31 #include <cmath>
  32
  33 using namespace std;
  34
  35 static double cachedparam = 0.0;
  36
  37 LocusImp::~LocusImp()
  38 {
  39   delete mcurve;
  40 }
  41
  42 ObjectImp* LocusImp::transform( const Transformation& t ) const
  43 {
  44   return new LocusImp( mcurve->copy(), mhier.transformFinalObject( t ) );
  45 }
  46
  47 void LocusImp::draw( KigPainter& p ) const
  48 {
  49   p.drawCurve( this );
  50 }
  51
  52 bool LocusImp::contains( const Coordinate& p, int width, const KigWidget& w ) const
  53 {
  54   return internalContainsPoint( p, w.screenInfo().normalMiss( width ), w.document() );
  55 }
  56
  57 bool LocusImp::inRect( const Rect&, int, const KigWidget& ) const
  58 {
  59   // TODO ?
  60   return false;
  61 }
  62
  63 const Coordinate LocusImp::getPoint( double param, const KigDocument& doc ) const
  64 {
  65   Coordinate arg = mcurve->getPoint( param, doc );
  66   if ( ! arg.valid() ) return arg;
  67   PointImp argimp( arg );
  68   Args args;
  69   args.push_back( &argimp );
  70   vector<ObjectImp*> calcret = mhier.calc( args, doc );
  71   assert( calcret.size() == 1 );
  72   ObjectImp* imp = calcret.front();
  73   Coordinate ret;
  74   if ( imp->inherits( PointImp::stype() ) )
  75   {
  76     cachedparam = param;
  77     ret = static_cast<PointImp*>( imp )->coordinate();
  78   }
  79   else
  80     ret = Coordinate::invalidCoord();
  81
  82   delete imp;
  83   return ret;
  84 }
  85
  86 LocusImp::LocusImp( CurveImp* curve, const ObjectHierarchy& hier )
  87   : mcurve( curve ), mhier( hier )
  88 {
  89 }
  90
  91 const uint LocusImp::numberOfProperties() const
  92 {
  93   return Parent::numberOfProperties();
  94 }
  95
  96 const QCStringList LocusImp::propertiesInternalNames() const
  97 {
  98   return Parent::propertiesInternalNames();
  99 }
 100
 101 const QCStringList LocusImp::properties() const
 102 {
 103   return Parent::properties();
 104 }
 105
 106 const ObjectImpType* LocusImp::impRequirementForProperty( uint which ) const
 107 {
 108   return Parent::impRequirementForProperty( which );
 109 }
 110
 111 const char* LocusImp::iconForProperty( uint which ) const
 112 {
 113   return Parent::iconForProperty( which );
 114 }
 115
 116 ObjectImp* LocusImp::property( uint which, const KigDocument& w ) const
 117 {
 118   return Parent::property( which, w );
 119 }
 120
 121 LocusImp* LocusImp::copy() const
 122 {
 123   return new LocusImp( mcurve->copy(), mhier );
 124 }
 125
 126 const CurveImp* LocusImp::curve() const
 127 {
 128   return mcurve;
 129 }
 130
 131 const ObjectHierarchy& LocusImp::hierarchy() const
 132 {
 133   return mhier;
 134 }
 135
 136 /**
 137  * This function returns the distance between the point with parameter
 138  * param and point p.  param is allowed to not be between 0 and 1, in
 139  * which case we consider only the decimal part.
 140  */
 141 double LocusImp::getDist(double param, const Coordinate& p, const KigDocument& doc) const
 142 {
 143   param = fmod( param, 1 );
 144   if( param < 0 ) param += 1.;
 145   Coordinate p1 = getPoint( param, doc );
 146   // i don't think the p1.valid() switch is really necessary, but I
 147   // prefer to not take any chances :)
 148   return p1.valid() ? ( p1 - p ).length() : +double_inf;
 149 }
 150
 151 /**
 152  * This function searches starting from x1 for the first interval in
 153  * which the function of the distance from the point at coordinate x
 154  * starts to increase.  The range found is returned in the parameters
 155  * x1 and x2: [x1,x2].
 156  */
 157 void LocusImp::getInterval( double& x1, double& x2,
 158                             double incr,const Coordinate& p,
 159                             const KigDocument& doc) const
 160 {
 161   double epsilon = incr/1000;
 162   double x3 = x1 + epsilon;
 163   double mm = getDist( x1, p, doc);
 164   double mm1 = getDist( x3, p, doc);
 165   if( mm  <= mm1 ) return;
 166   else
 167   {
 168     x2 = x3;
 169     while( mm > mm1 )
 170     {
 171       x3 = x2;
 172       x1 += 500 * epsilon;
 173       mm = getDist( x1, p, doc );
 174       x2 = x1 + epsilon;
 175       mm1 = getDist( x2, p, doc );
 176     }
 177     x2=x1;
 178     x1=x3;
 179   }
 180 }
 181
 182 double LocusImp::getParam( const Coordinate& p, const KigDocument& doc ) const
 183 {
 184   // this function ( and related functions like getInterval etc. ) is
 185   // written by Franco Pasquarelli <pasqui@dmf.bs.unicatt.it>.
 186   // I ( domi ) have adapted and documented it a bit.
 187
 188   if ( cachedparam >= 0. && cachedparam <= 1. &&
 189        getPoint ( cachedparam, doc ) == p ) return cachedparam;
 190
 191   // consider the function that returns the distance for a point at
 192   // parameter x to the locus for a given parameter x.  What we do
 193   // here is look for the global minimum of this function.  We do that
 194   // by dividing the range ( [0,1] ) into N parts,  and start looking
 195   // for a local minimum from there on.  If we find one, we keep it if
 196   // it is the lowest of all the ones we've already found..
 197
 198   const int N = 60;
 199   const double incr = 1. / (double) N;
 200
 201   // xm is the best parameter we've found so far, fxm is the distance
 202   // to the locus from that point.  We start with some
 203   // pseudo-values.
 204   // (mp) note that if the distance is actually increasing in the
 205   // whole interval [0,1] this value will be returned in the end.
 206   double xm = 0.;
 207   double fxm = getDist( xm, p, doc );
 208
 209   int j = 0;
 210
 211   while( j < N )
 212   {
 213     // [x1,x2] is the range we're currently considering..
 214     double x1 = j * incr;
 215     double x2 = x1 + incr;
 216
 217     // check the range x1,x2 for the first local maximum..
 218     getInterval( x1, x2, incr, p, doc );
 219
 220     // don't consider intervals where the distance is increasing..
 221     if ( fabs( x1 - j * incr ) > 1.e-8 )
 222     {
 223       double xm1 = getParamofmin( x1, x2, p, doc);
 224       double fxm1 = getDist( xm1, p, doc );
 225       if( fxm1 < fxm )
 226       {
 227         // we found a new minimum, save it..
 228         xm=xm1;
 229         fxm=fxm1;
 230       }
 231       j = (int) ( x2 / incr );
 232     }
 233     j++;
 234   }
 235   return xm;
 236 }
 237
 238 /**
 239  * This function calculate the parameter of the point that realize the
 240  * minimum in [a,b] of the distance between the points of the locus and
 241  * the point of coordinate p, using the Fibonacci method.
 242  * This method is optimal in the sence that assigned a number of
 243  * iteration it reduce to minimum the interval that contain the
 244  * minimum of the function
 245  */
 246 double LocusImp::getParamofmin( double a, double b,
 247                                 const Coordinate& p,
 248                                 const KigDocument& doc ) const
 249 {
 250   double epsilon = 1.e-4;
 251 //  double epsilon = 1.e-8;
 252   // I compute the it number of iteration of the Fibonacci method
 253   // to obtain a error between the computed and the exact minimum
 254   // less than epsilon
 255   int it = 2;
 256   int i = 1;
 257   int jj = 1;
 258   while( ( b - a ) / (double) ( 2 * jj ) > epsilon )
 259   {
 260     int M= i + jj;
 261     i= jj;
 262     jj= M;
 263     it++;
 264   }
 265   int t[3];
 266   t[0]= jj;
 267   t[1]= i + jj;
 268   t[2]= t[1] + t[0];
 269
 270   double x = ( b - a ) / t[2];
 271   double x1 = a + t[0] * x;
 272   double x2 = a + t[1] * x;
 273   double fx1 = getDist( x1, p, doc) ;
 274   double fx2 = getDist( x2, p, doc);
 275
 276   if (fx1 < fx2)
 277     b = x2;
 278   else
 279     a = x1;
 280
 281   for( int k=1; k <= it - 2; ++k )
 282   {
 283     if ( fx1 < fx2 )
 284     {
 285       x = x1;
 286       x1 = a + x2 - x1;
 287       x2 = x;
 288       fx2 = fx1;
 289       fx1 = getDist( x1, p, doc);
 290     }
 291     else
 292     {
 293       x = x2;
 294       x2 = b - x2 + x1;
 295       x1 = x;
 296       fx1 = fx2;
 297       fx2 = getDist( x2, p, doc);
 298     }
 299     if (fx1 < fx2 )
 300       b = x2;
 301     else
 302       a = x1;
 303   }
 304   x1 = ( a + b ) / 2.;
 305   x2 = x1 + epsilon / 2.;
 306   x1 = x1 - epsilon / 2.;
 307   fx1 = getDist( x1, p, doc);
 308   fx2 = getDist( x2, p, doc);
 309   if (fx1 < fx2)
 310     b = x2;
 311   else
 312     a = x1;
 313
 314   x = fmod( ( a +b ) / 2., 1 );
 315   if( x < 0 ) x += 1.;
 316   return(x);
 317 }
 318
 319 void LocusImp::visit( ObjectImpVisitor* vtor ) const
 320 {
 321   vtor->visit( this );
 322 }
 323
 324 bool LocusImp::equals( const ObjectImp& rhs ) const
 325 {
 326   return rhs.inherits( LocusImp::stype() ) &&
 327     static_cast<const LocusImp&>( rhs ).curve()->equals( *curve() ) &&
 328     static_cast<const LocusImp&>( rhs ).hierarchy() == hierarchy();
 329 }
 330
 331 const ObjectImpType* LocusImp::stype()
 332 {
 333   static const ObjectImpType t(
 334     Parent::stype(), "locus",
 335     I18N_NOOP( "locus" ),
 336     I18N_NOOP( "Select this locus" ),
 337     I18N_NOOP( "Select locus %1" ),
 338     I18N_NOOP( "Remove a Locus" ),
 339     I18N_NOOP( "Add a Locus" ),
 340     I18N_NOOP( "Move a Locus" ),
 341     I18N_NOOP( "Attach to this locus" ),
 342     I18N_NOOP( "Show a Locus" ),
 343     I18N_NOOP( "Hide a Locus" )
 344     );
 345   return &t;
 346 }
 347
 348 const ObjectImpType* LocusImp::type() const
 349 {
 350   return LocusImp::stype();
 351 }
 352
 353 bool LocusImp::containsPoint( const Coordinate& p, const KigDocument& doc ) const
 354 {
 355   return internalContainsPoint( p, test_threshold, doc );
 356 }
 357
 358 bool LocusImp::internalContainsPoint( const Coordinate& p, double threshold, const KigDocument& doc ) const
 359 {
 360   double param = getParam( p, doc );
 361   double dist = getDist( param, p, doc );
 362   return fabs( dist ) <= threshold;
 363 }
 364
 365 bool LocusImp::isPropertyDefinedOnOrThroughThisImp( uint which ) const
 366 {
 367   return Parent::isPropertyDefinedOnOrThroughThisImp( which );
 368 }
 369
 370 Rect LocusImp::surroundingRect() const
 371 {
 372   // it's probably possible to calculate this, if it exists, but we
 373   // don't for now.
 374   return Rect::invalidRect();
 375 }