diff options
Diffstat (limited to 'kig/objects/polygon_imp.cc')
| -rw-r--r-- | kig/objects/polygon_imp.cc | 550 |
1 files changed, 550 insertions, 0 deletions
diff --git a/kig/objects/polygon_imp.cc b/kig/objects/polygon_imp.cc new file mode 100644 index 00000000..08215bfb --- /dev/null +++ b/kig/objects/polygon_imp.cc @@ -0,0 +1,550 @@ +// Copyright (C) 2004 Pino Toscano <toscano.pino@tiscali.it> + +// This program is free software; you can redistribute it and/or +// modify it under the terms of the GNU General Public License +// as published by the Free Software Foundation; either version 2 +// of the License, or (at your option) any later version. + +// This program is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with this program; if not, write to the Free Software +// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA +// 02110-1301, USA. + +#include "polygon_imp.h" + +#include "bogus_imp.h" +#include "line_imp.h" +#include "point_imp.h" + +#include "../misc/common.h" +#include "../misc/coordinate.h" +#include "../misc/kigpainter.h" +#include "../misc/kigtransform.h" + +#include "../kig/kig_document.h" +#include "../kig/kig_view.h" + +#include <klocale.h> + +#include <cmath> + +PolygonImp::PolygonImp( uint npoints, const std::vector<Coordinate>& points, + const Coordinate& centerofmass ) + : mnpoints( npoints ), mpoints( points ), mcenterofmass( centerofmass ) +{ +// mpoints = points; +} + +PolygonImp::PolygonImp( const std::vector<Coordinate>& points ) +{ + uint npoints = points.size(); + Coordinate centerofmassn = Coordinate( 0, 0 ); + + for ( uint i = 0; i < npoints; ++i ) + { + centerofmassn += points[i]; + } + mpoints = points; + mcenterofmass = centerofmassn/npoints; + mnpoints = npoints; +} + +PolygonImp::~PolygonImp() +{ +} + +Coordinate PolygonImp::attachPoint() const +{ + return mcenterofmass; +} + +ObjectImp* PolygonImp::transform( const Transformation& t ) const +{ +/*mp: + * any projective transformation makes sense for a polygon, + * since segments transform into segments (but see below...) + * of course regular polygons will no longer be + * regular if t is not homothetic. + * for projective transformations the polygon could transform to + * an unbounded nonconnected polygon; this happens if some side + * of the polygon crosses the critical line that maps to infinity + * this can be easily checked using the getProjectiveIndicator + * function + */ +// if ( ! t.isHomothetic() ) +// return new InvalidImp(); + + if ( ! t.isAffine() ) /* in this case we need a more extensive test */ + { + double maxp = -1.0; + double minp = 1.0; + for ( uint i = 0; i < mpoints.size(); ++i ) + { + double p = t.getProjectiveIndicator( mpoints[i] ); + if ( p > maxp ) maxp = p; + if ( p < minp ) minp = p; + } + if ( maxp > 0 && minp < 0 ) return new InvalidImp; + } + std::vector<Coordinate> np; + for ( uint i = 0; i < mpoints.size(); ++i ) + { + Coordinate nc = t.apply( mpoints[i] ); + if ( !nc.valid() ) + return new InvalidImp; + np.push_back( nc ); + } + return new PolygonImp( np ); +} + +void PolygonImp::draw( KigPainter& p ) const +{ + p.drawPolygon( mpoints ); +} + +bool PolygonImp::isInPolygon( const Coordinate& p ) const +{ + // (algorithm sent to me by domi) + // We intersect with the horizontal ray from point to the right and + // count the number of intersections. That, along with some + // minor optimalisations of the intersection test.. + bool inside_flag = false; + double cx = p.x; + double cy = p.y; + + Coordinate prevpoint = mpoints.back(); + bool prevpointbelow = mpoints.back().y >= cy; + for ( uint i = 0; i < mpoints.size(); ++i ) + { + Coordinate point = mpoints[i]; + bool pointbelow = point.y >= cy; + if ( prevpointbelow != pointbelow ) + { + // possibility of intersection: points on different side from + // the X axis + //bool rightofpt = point.x >= cx; + // mp: we need to be a little bit more conservative here, in + // order to treat properly the case when the point is on the + // boundary + //if ( rightofpt == ( prevpoint.x >= cx ) ) + if ( ( point.x - cx )*(prevpoint.x - cx ) > 0 ) + { + // points on same side of Y axis -> easy to test intersection + // intersection iff one point to the right of c + if ( point.x >= cx ) + inside_flag = !inside_flag; + } + else + { + // points on different sides of Y axis -> we need to calculate + // the intersection. + // mp: we want to check if the point is on the boundary, and + // return false in such case + double num = ( point.y - cy )*( prevpoint.x - point.x ); + double den = prevpoint.y - point.y; + if ( num == den*( point.x - cx ) ) return false; + if ( num/den <= point.x - cx ) + inside_flag = !inside_flag; + } + } + prevpoint = point; + prevpointbelow = pointbelow; + } + return inside_flag; +} +#define selectpolygonwithinside 1 +#ifdef selectpolygonwithinside +bool PolygonImp::contains( const Coordinate& p, int, const KigWidget& ) const +{ + return isInPolygon( p ); +} +#else +bool PolygonImp::contains( const Coordinate& p, int width, const KigWidget& w ) const +{ + bool ret = false; + uint reduceddim = mpoints.size() - 1; + for ( uint i = 0; i < reduceddim; ++i ) + { + ret |= isOnSegment( p, mpoints[i], mpoints[i+1], w.screenInfo().normalMiss( width ) ); + } + ret |= isOnSegment( p, mpoints[reduceddim], mpoints[0], w.screenInfo().normalMiss( width ) ); + + return ret; +} +#endif + +bool PolygonImp::inRect( const Rect& r, int width, const KigWidget& w ) const +{ + bool ret = false; + uint reduceddim = mpoints.size() - 1; + for ( uint i = 0; i < reduceddim; ++i ) + { + SegmentImp* s = new SegmentImp( mpoints[i], mpoints[i+1] ); + ret |= lineInRect( r, mpoints[i], mpoints[i+1], width, s, w ); + delete s; + s = 0; + } + SegmentImp* t = new SegmentImp( mpoints[reduceddim], mpoints[0] ); + ret |= lineInRect( r, mpoints[reduceddim], mpoints[0], width, t, w ); + delete t; + t = 0; + + return ret; +} + +bool PolygonImp::valid() const +{ + return true; +} + +const uint PolygonImp::numberOfProperties() const +{ + return Parent::numberOfProperties() + 5; +} + +const QCStringList PolygonImp::propertiesInternalNames() const +{ + QCStringList l = Parent::propertiesInternalNames(); + l += "polygon-number-of-sides"; + l += "polygon-perimeter"; + l += "polygon-surface"; + l += "polygon-center-of-mass"; + l += "polygon-winding-number"; + assert( l.size() == PolygonImp::numberOfProperties() ); + return l; +} + +const QCStringList PolygonImp::properties() const +{ + QCStringList l = Parent::properties(); + l += I18N_NOOP( "Number of sides" ); + l += I18N_NOOP( "Perimeter" ); + l += I18N_NOOP( "Surface" ); + l += I18N_NOOP( "Center of Mass of the Vertices" ); + l += I18N_NOOP( "Winding Number" ); + assert( l.size() == PolygonImp::numberOfProperties() ); + return l; +} + +const ObjectImpType* PolygonImp::impRequirementForProperty( uint which ) const +{ + if ( which < Parent::numberOfProperties() ) + return Parent::impRequirementForProperty( which ); + else return PolygonImp::stype(); +} + +const char* PolygonImp::iconForProperty( uint which ) const +{ + assert( which < PolygonImp::numberOfProperties() ); + if ( which < Parent::numberOfProperties() ) + return Parent::iconForProperty( which ); + else if ( which == Parent::numberOfProperties() ) + return "en"; // number of sides + else if ( which == Parent::numberOfProperties() + 1 ) + return "circumference"; // perimeter + else if ( which == Parent::numberOfProperties() + 2 ) + return "areaCircle"; // surface + else if ( which == Parent::numberOfProperties() + 3 ) + return "point"; // center of mass + else if ( which == Parent::numberOfProperties() + 4 ) + return "w"; // winding number + else assert( false ); + return ""; +} + +ObjectImp* PolygonImp::property( uint which, const KigDocument& w ) const +{ + assert( which < PolygonImp::numberOfProperties() ); + if ( which < Parent::numberOfProperties() ) + return Parent::property( which, w ); + else if ( which == Parent::numberOfProperties() ) + { + // number of points + return new IntImp( mnpoints ); + } + else if ( which == Parent::numberOfProperties() + 1) + { + double circumference = 0.; + // circumference + for ( uint i = 0; i < mpoints.size(); ++i ) + { + uint prev = ( i + mpoints.size() - 1 ) % mpoints.size(); + circumference += ( mpoints[i] - mpoints[prev] ).length(); + } + return new DoubleImp( circumference ); + } + else if ( which == Parent::numberOfProperties() + 2) + { + int wn = windingNumber (); // not able to compute area for such polygons... + if ( wn < 0 ) wn = -wn; + if ( wn != 1 ) return new InvalidImp; + double surface2 = 0.0; + Coordinate prevpoint = mpoints.back(); + for ( uint i = 0; i < mpoints.size(); ++i ) + { + Coordinate point = mpoints[i]; + surface2 += ( point.x - prevpoint.x ) * ( point.y + prevpoint.y ); + prevpoint = point; + } + return new DoubleImp( fabs( surface2 / 2 ) ); + } + else if ( which == Parent::numberOfProperties() + 3 ) + { + return new PointImp( mcenterofmass ); + } + else if ( which == Parent::numberOfProperties() + 4 ) + { + // winding number + return new IntImp( windingNumber() ); + } + else assert( false ); + return new InvalidImp; +} + +const std::vector<Coordinate> PolygonImp::points() const +{ + std::vector<Coordinate> np; + np.reserve( mpoints.size() ); + std::copy( mpoints.begin(), mpoints.end(), std::back_inserter( np ) ); + return np; +} + +const uint PolygonImp::npoints() const +{ + return mnpoints; +} + +PolygonImp* PolygonImp::copy() const +{ + return new PolygonImp( mpoints ); +} + +void PolygonImp::visit( ObjectImpVisitor* vtor ) const +{ + vtor->visit( this ); +} + +bool PolygonImp::equals( const ObjectImp& rhs ) const +{ + return rhs.inherits( PolygonImp::stype() ) && + static_cast<const PolygonImp&>( rhs ).points() == mpoints; +} + +const ObjectImpType* PolygonImp::stype() +{ + static const ObjectImpType t( + Parent::stype(), "polygon", + I18N_NOOP( "polygon" ), + I18N_NOOP( "Select this polygon" ), + I18N_NOOP( "Select polygon %1" ), + I18N_NOOP( "Remove a Polygon" ), + I18N_NOOP( "Add a Polygon" ), + I18N_NOOP( "Move a Polygon" ), + I18N_NOOP( "Attach to this polygon" ), + I18N_NOOP( "Show a Polygon" ), + I18N_NOOP( "Hide a Polygon" ) + ); + + return &t; +} + +const ObjectImpType* PolygonImp::stype3() +{ + static const ObjectImpType t3( + PolygonImp::stype(), "triangle", + I18N_NOOP( "triangle" ), + I18N_NOOP( "Select this triangle" ), + I18N_NOOP( "Select triangle %1" ), + I18N_NOOP( "Remove a Triangle" ), + I18N_NOOP( "Add a Triangle" ), + I18N_NOOP( "Move a Triangle" ), + I18N_NOOP( "Attach to this triangle" ), + I18N_NOOP( "Show a Triangle" ), + I18N_NOOP( "Hide a Triangle" ) + ); + + return &t3; +} + +const ObjectImpType* PolygonImp::stype4() +{ + static const ObjectImpType t4( + PolygonImp::stype(), "quadrilateral", + I18N_NOOP( "quadrilateral" ), + I18N_NOOP( "Select this quadrilateral" ), + I18N_NOOP( "Select quadrilateral %1" ), + I18N_NOOP( "Remove a Quadrilateral" ), + I18N_NOOP( "Add a Quadrilateral" ), + I18N_NOOP( "Move a Quadrilateral" ), + I18N_NOOP( "Attach to this quadrilateral" ), + I18N_NOOP( "Show a Quadrilateral" ), + I18N_NOOP( "Hide a Quadrilateral" ) + ); + + return &t4; +} + +const ObjectImpType* PolygonImp::type() const +{ + uint n = mpoints.size(); + + if ( n == 3 ) return PolygonImp::stype3(); + if ( n == 4 ) return PolygonImp::stype4(); + return PolygonImp::stype(); +} + +bool PolygonImp::isPropertyDefinedOnOrThroughThisImp( uint which ) const +{ + assert( which < PolygonImp::numberOfProperties() ); + if ( which < Parent::numberOfProperties() ) + return Parent::isPropertyDefinedOnOrThroughThisImp( which ); + return false; +} + +Rect PolygonImp::surroundingRect() const +{ + Rect r( 0., 0., 0., 0. ); + for ( uint i = 0; i < mpoints.size(); ++i ) + { + r.setContains( mpoints[i] ); + } + return r; +} + +int PolygonImp::windingNumber() const +{ + /* + * this is defined as the sum of the external angles while at + * all vertices, then normalized by 2pi. The external angle + * is the angle we steer at each vertex while we walk along the + * boundary of the polygon. + * In the end we only need to count how many time we cross the (1,0) + * direction (positive x-axis) with a positive sign if we cross while + * steering left and a negative sign viceversa + */ + + int winding = 0; + uint npoints = mpoints.size(); + Coordinate prevside = mpoints[0] - mpoints[npoints-1]; + for ( uint i = 0; i < npoints; ++i ) + { + uint nexti = i + 1; + if ( nexti >= npoints ) nexti = 0; + Coordinate side = mpoints[nexti] - mpoints[i]; + double vecprod = side.x*prevside.y - side.y*prevside.x; + int steeringdir = ( vecprod > 0 ) ? 1 : -1; + if ( vecprod == 0.0 || side.y*prevside.y > 0 ) + { + prevside = side; + continue; // cannot cross the (1,0) direction + } + if ( side.y*steeringdir < 0 && prevside.y*steeringdir >= 0 ) + winding -= steeringdir; + prevside = side; + } + return winding; +} + +bool PolygonImp::isMonotoneSteering() const +{ + /* + * returns true if while walking along the boundary, + * steering is always in the same direction + */ + + uint npoints = mpoints.size(); + Coordinate prevside = mpoints[0] - mpoints[npoints-1]; + int prevsteeringdir = 0; + for ( uint i = 0; i < npoints; ++i ) + { + uint nexti = i + 1; + if ( nexti >= npoints ) nexti = 0; + Coordinate side = mpoints[nexti] - mpoints[i]; + double vecprod = side.x*prevside.y - side.y*prevside.x; + int steeringdir = ( vecprod > 0 ) ? 1 : -1; + if ( vecprod == 0.0 ) + { + prevside = side; + continue; // going straight + } + if ( prevsteeringdir*steeringdir < 0 ) return false; + prevside = side; + prevsteeringdir = steeringdir; + } + return true; +} + +bool PolygonImp::isConvex() const +{ + if ( ! isMonotoneSteering() ) return false; + int winding = windingNumber(); + if ( winding < 0 ) winding = -winding; + assert ( winding > 0 ); + return winding == 1; +} + +std::vector<Coordinate> computeConvexHull( const std::vector<Coordinate>& points ) +{ + /* + * compute the convex hull of the set of points, the resulting list + * is the vertices of the resulting polygon listed in a counter clockwise + * order. This algorithm is on order n^2, probably suboptimal, but + * we don't expect to have large values for n. + */ + + if ( points.size() < 3 ) return points; + std::vector<Coordinate> worklist = points; + std::vector<Coordinate> result; + + double ymin = worklist[0].y; + uint imin = 0; + for ( uint i = 1; i < worklist.size(); ++i ) + { + if ( worklist[i].y < ymin ) + { + ymin = worklist[i].y; + imin = i; + } + } + + // worklist[imin] is definitely on the convex hull, let's start from there + result.push_back( worklist[imin] ); + Coordinate startpoint = worklist[imin]; + Coordinate apoint = worklist[imin]; + double aangle = 0.0; + + while ( ! worklist.empty() ) + { + int besti = -1; + double anglemin = 10000.0; + for ( uint i = 0; i < worklist.size(); ++i ) + { + if ( worklist[i] == apoint ) continue; + Coordinate v = worklist[i] - apoint; + double angle = std::atan2( v.y, v.x ); + while ( angle < aangle ) angle += 2*M_PI; + if ( angle < anglemin ) + { // found a better point + besti = i; + anglemin = angle; + } + } + + if ( besti < 0 ) return result; // this happens, e.g. if all points coincide + apoint = worklist[besti]; + aangle = anglemin; + if ( apoint == startpoint ) + { + return result; + } + result.push_back( apoint ); + worklist.erase( worklist.begin() + besti, worklist.begin() + besti + 1 ); + } + assert( false ); + return result; +} |