diff options
Diffstat (limited to 'basegfx/source/polygon/b2dpolygontools.cxx')
-rw-r--r-- | basegfx/source/polygon/b2dpolygontools.cxx | 422 |
1 files changed, 394 insertions, 28 deletions
diff --git a/basegfx/source/polygon/b2dpolygontools.cxx b/basegfx/source/polygon/b2dpolygontools.cxx index 0c1136ca5553..c5b56dd72e31 100644 --- a/basegfx/source/polygon/b2dpolygontools.cxx +++ b/basegfx/source/polygon/b2dpolygontools.cxx @@ -2,9 +2,9 @@ * * $RCSfile: b2dpolygontools.cxx,v $ * - * $Revision: 1.2 $ + * $Revision: 1.3 $ * - * last change: $Author: aw $ $Date: 2003-10-31 10:13:58 $ + * last change: $Author: aw $ $Date: 2003-11-05 12:25:54 $ * * The Contents of this file are made available subject to the terms of * either of the following licenses @@ -67,8 +67,12 @@ #include <basegfx/polygon/b2dpolygon.hxx> #endif -#ifndef _BGFX_CURVE_B2DCUBICBEZIER_HXX -#include <basegfx/curve/b2dcubicbezier.hxx> +#ifndef _BGFX_NUMERIC_FTOOLS_HXX +#include <basegfx/numeric/ftools.hxx> +#endif + +#ifndef _BGFX_RANGE_B2DRANGE_HXX +#include <basegfx/range/b2drange.hxx> #endif ////////////////////////////////////////////////////////////////////////////// @@ -84,53 +88,415 @@ namespace basegfx { while(rCandidate.count() > 1L) { - bool bFirstLastPointEqual( - rCandidate.getB2DPoint(0L) == rCandidate.getB2DPoint(rCandidate.count() - 1L)); + sal_Bool bFirstLastPointEqual(rCandidate.getB2DPoint(0L).equal(rCandidate.getB2DPoint(rCandidate.count() - 1L))); if(bFirstLastPointEqual) { - rCandidate.setClosed(true); + rCandidate.setClosed(sal_True); rCandidate.remove(rCandidate.count() - 1L); } } } - // Checks if one of the control vectors is used - bool isEdgeBezier(const polygon::B2DPolygon& rPolygon, sal_uInt32 nEdgeIndex) + // Get index of outmost point (e.g. biggest X and biggest Y) + sal_uInt32 getIndexOfOutmostPoint(const polygon::B2DPolygon& rCandidate) + { + sal_uInt32 nRetval(0L); + + if(rCandidate.count()) + { + ::basegfx::point::B2DPoint aOutmostPoint(rCandidate.getB2DPoint(0L)); + + for(sal_uInt32 a(1L); a < rCandidate.count(); a++) + { + ::basegfx::point::B2DPoint rPoint(rCandidate.getB2DPoint(a)); + + if(::basegfx::numeric::fTools::more(rPoint.getX(), aOutmostPoint.getX())) + { + nRetval = a; + aOutmostPoint = rPoint; + } + else + { + if(::basegfx::numeric::fTools::more(rPoint.getY(), aOutmostPoint.getY())) + { + nRetval = a; + aOutmostPoint = rPoint; + } + } + } + } + + return nRetval; + } + + // Get successor and predecessor indices. Returning the same index means there + // is none. Same for successor. + sal_uInt32 getIndexOfPredecessor(sal_uInt32 nIndex, const polygon::B2DPolygon& rCandidate) + { + if(nIndex) + { + return nIndex - 1L; + } + else if(rCandidate.count()) + { + return rCandidate.count() - 1L; + } + else + { + return nIndex; + } + } + + sal_uInt32 getIndexOfSuccessor(sal_uInt32 nIndex, const polygon::B2DPolygon& rCandidate) + { + if(nIndex + 1L < rCandidate.count()) + { + return nIndex + 1L; + } + else + { + return 0L; + } + } + + sal_uInt32 getIndexOfDifferentPredecessor(sal_uInt32 nIndex, const polygon::B2DPolygon& rCandidate) + { + if(rCandidate.count() > 1) + { + sal_uInt32 nNewIndex = getIndexOfPredecessor(nIndex, rCandidate); + ::basegfx::point::B2DPoint aPoint(rCandidate.getB2DPoint(nIndex)); + + while(nNewIndex != nIndex + && aPoint.equal(rCandidate.getB2DPoint(nNewIndex))) + { + nNewIndex = getIndexOfPredecessor(nNewIndex, rCandidate); + } + } + + return nIndex; + } + + sal_uInt32 getIndexOfDifferentSuccessor(sal_uInt32 nIndex, const polygon::B2DPolygon& rCandidate) { - if(rPolygon.areControlPointsUsed()) + if(rCandidate.count() > 1) { - DBG_ASSERT(nEdgeIndex < rPolygon.count(), "EdgeIndex out of range (!)"); + sal_uInt32 nNewIndex = getIndexOfSuccessor(nIndex, rCandidate); + ::basegfx::point::B2DPoint aPoint(rCandidate.getB2DPoint(nIndex)); + + while(nNewIndex != nIndex + && aPoint.equal(rCandidate.getB2DPoint(nNewIndex))) + { + nNewIndex = getIndexOfSuccessor(nNewIndex, rCandidate); + } + } - if(!rPolygon.getControlPointA(nEdgeIndex).equalZero()) - return true; + return nIndex; + } + + ::basegfx::vector::B2DVectorOrientation getOrientation(const ::basegfx::polygon::B2DPolygon& rCandidate) + { + ::basegfx::vector::B2DVectorOrientation eRetval(::basegfx::vector::ORIENTATION_NEUTRAL); - if(!rPolygon.getControlPointB(nEdgeIndex).equalZero()) - return true; + if(rCandidate.count() > 2) + { + sal_uInt32 nIndex = getIndexOfOutmostPoint(rCandidate); + eRetval = getPointOrientation(rCandidate, nIndex); } - return false; + return eRetval; } - bool isEdgeTrivialBezier(const polygon::B2DPolygon& rPolygon, sal_uInt32 nEdgeIndex) + sal_Bool isInside(const ::basegfx::polygon::B2DPolygon& rCandidate, const ::basegfx::point::B2DPoint& rPoint) { - if(rPolygon.areControlPointsUsed()) + sal_Bool bRetval(sal_False); + const sal_uInt32 nPointCount(rCandidate.count()); + + for(sal_uInt32 a(0L); a < nPointCount; a++) { - DBG_ASSERT(nEdgeIndex < rPolygon.count(), "EdgeIndex out of range (!)"); - const sal_uInt32 nEndIndex((nEdgeIndex + 1L) % rPolygon.count()); + const basegfx::point::B2DPoint aCurrentPoint(rCandidate.getB2DPoint(a)); + const basegfx::point::B2DPoint aPreviousPoint(rCandidate.getB2DPoint((!a) ? nPointCount - 1L : a - 1L)); - curve::B2DCubicBezier aCubicBezier( - rPolygon.getB2DPoint(nEdgeIndex), - rPolygon.getControlPointA(nEdgeIndex), - rPolygon.getControlPointB(nEdgeIndex), - rPolygon.getB2DPoint(nEndIndex)); + // cross-over in Y? + const sal_Bool bCompYA(::basegfx::numeric::fTools::more(aPreviousPoint.getY(), rPoint.getY())); + const sal_Bool bCompYB(::basegfx::numeric::fTools::more(aCurrentPoint.getY(), rPoint.getY())); - aCubicBezier.testAndSolveTrivialBezier(); + if(bCompYA != bCompYB) + { + const sal_Bool bCompXA(::basegfx::numeric::fTools::more(aPreviousPoint.getX(), rPoint.getX())); + const sal_Bool bCompXB(::basegfx::numeric::fTools::more(aCurrentPoint.getX(), rPoint.getX())); + + if(bCompXA == bCompXB) + { + if(bCompXA) + { + bRetval = !bRetval; + } + } + else + { + const double fCompare = + aCurrentPoint.getX() - (aCurrentPoint.getY() - rPoint.getY()) * + (aPreviousPoint.getX() - aCurrentPoint.getX()) / + (aPreviousPoint.getY() - aCurrentPoint.getY()); + + if(::basegfx::numeric::fTools::more(fCompare, rPoint.getX())) + { + bRetval = !bRetval; + } + } + } + } + + return bRetval; + } + + sal_Bool isInside(const ::basegfx::polygon::B2DPolygon& rCandidate, const ::basegfx::polygon::B2DPolygon& rPolygon) + { + const sal_uInt32 nPointCount(rPolygon.count()); - return !aCubicBezier.isBezier(); + for(sal_uInt32 a(0L); a < nPointCount; a++) + { + const ::basegfx::point::B2DPoint aTestPoint(rPolygon.getB2DPoint(a)); + + if(!isInside(rCandidate, aTestPoint)) + { + return sal_False; + } + } + + return sal_True; + } + + ::basegfx::range::B2DRange getRange(const ::basegfx::polygon::B2DPolygon& rCandidate) + { + ::basegfx::range::B2DRange aRetval; + const sal_uInt32 nPointCount(rCandidate.count()); + + for(sal_uInt32 a(0L); a < nPointCount; a++) + { + const ::basegfx::point::B2DPoint aTestPoint(rCandidate.getB2DPoint(a)); + aRetval.expand(aTestPoint); + } + + return aRetval; + } + + double getArea(const ::basegfx::polygon::B2DPolygon& rCandidate) + { + double fRetval(0.0); + const sal_uInt32 nPointCount(rCandidate.count()); + + if(nPointCount > 2) + { + for(sal_uInt32 a(0L); a < nPointCount; a++) + { + const basegfx::point::B2DPoint aPreviousPoint(rCandidate.getB2DPoint((!a) ? nPointCount - 1L : a - 1L)); + const basegfx::point::B2DPoint aCurrentPoint(rCandidate.getB2DPoint(a)); + + fRetval += aPreviousPoint.getX() * aCurrentPoint.getY(); + fRetval -= aPreviousPoint.getY() * aCurrentPoint.getX(); + } + + fRetval /= 2.0; + + const double fZero(0.0); + + if(::basegfx::numeric::fTools::less(fRetval, fZero)) + { + fRetval = -fRetval; + } + } + + return fRetval; + } + + double getEdgeLength(const ::basegfx::polygon::B2DPolygon& rCandidate, sal_uInt32 nIndex) + { + double fRetval(0.0); + const sal_uInt32 nPointCount(rCandidate.count()); + + if(nIndex < nPointCount) + { + if(rCandidate.isClosed() || nIndex + 1 != nPointCount) + { + const sal_uInt32 nNextIndex(nIndex + 1 == nPointCount ? 0L : nIndex + 1L); + const basegfx::point::B2DPoint aCurrentPoint(rCandidate.getB2DPoint(nIndex)); + const basegfx::point::B2DPoint aNextPoint(rCandidate.getB2DPoint(nNextIndex)); + const basegfx::vector::B2DVector aVector(aNextPoint - aCurrentPoint); + fRetval = aVector.getLength(); + } + } + + return fRetval; + } + + double getLength(const ::basegfx::polygon::B2DPolygon& rCandidate) + { + // This method may also be implemented using a loop over getEdgeLength, but + // since this would cause a lot of sqare roots to be solved it is much better + // to sum up the quadrats first and then use a singe suare root (if necessary) + double fRetval(0.0); + const sal_uInt32 nPointCount(rCandidate.count()); + const sal_uInt32 nLoopCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1L); + + for(sal_uInt32 a(0L); a < nLoopCount; a++) + { + const sal_uInt32 nNextIndex(a + 1 == nPointCount ? 0L : a + 1L); + const basegfx::point::B2DPoint aCurrentPoint(rCandidate.getB2DPoint(a)); + const basegfx::point::B2DPoint aNextPoint(rCandidate.getB2DPoint(nNextIndex)); + const basegfx::vector::B2DVector aVector(aNextPoint - aCurrentPoint); + fRetval += aVector.scalar(aVector); + } + + if(!::basegfx::numeric::fTools::equalZero(fRetval)) + { + const double fOne(1.0); + + if(!::basegfx::numeric::fTools::equal(fOne, fRetval)) + { + fRetval = sqrt(fRetval); + } + } + + return fRetval; + } + + ::basegfx::point::B2DPoint getPositionAbsolute(const ::basegfx::polygon::B2DPolygon& rCandidate, double fDistance, double fLength) + { + ::basegfx::point::B2DPoint aRetval; + const sal_uInt32 nPointCount(rCandidate.count()); + + if(nPointCount > 1L) + { + sal_uInt32 nIndex(0L); + sal_Bool bIndexDone(sal_False); + const double fZero(0.0); + double fEdgeLength(fZero); + + // get length if not given + if(::basegfx::numeric::fTools::equalZero(fLength)) + { + fLength = getLength(rCandidate); + } + + // handle fDistance < 0.0 + if(::basegfx::numeric::fTools::less(fDistance, fZero)) + { + if(rCandidate.isClosed()) + { + // if fDistance < 0.0 increment with multiple of fLength + sal_uInt32 nCount(sal_uInt32(-fDistance / fLength)); + fDistance += double(nCount + 1L) * fLength; + } + else + { + // crop to polygon start + fDistance = fZero; + bIndexDone = sal_True; + } + } + + // handle fDistance >= fLength + if(::basegfx::numeric::fTools::moreOrEqual(fDistance, fLength)) + { + if(rCandidate.isClosed()) + { + // if fDistance >= fLength decrement with multiple of fLength + sal_uInt32 nCount(sal_uInt32(fDistance / fLength)); + fDistance -= (double)(nCount) * fLength; + } + else + { + // crop to polygon end + fDistance = fZero; + nIndex = nPointCount - 1L; + bIndexDone = sal_True; + } + } + + // look for correct index. fDistance is now [0.0 .. fLength[ + if(!bIndexDone) + { + do + { + // get length of next edge + fEdgeLength = getEdgeLength(rCandidate, nIndex); + + if(::basegfx::numeric::fTools::moreOrEqual(fDistance, fEdgeLength)) + { + // go to next edge + fDistance -= fEdgeLength; + nIndex++; + } + else + { + // it's on this edge, stop + bIndexDone = sal_True; + } + } while (!bIndexDone); + } + + // get the point using nIndex + aRetval = rCandidate.getB2DPoint(nIndex); + + // if fDistance != 0.0, move that length on the edge. The edge + // length is in fEdgeLength. + if(!::basegfx::numeric::fTools::equalZero(fDistance)) + { + sal_uInt32 nNextIndex(getIndexOfSuccessor(nIndex, rCandidate)); + const ::basegfx::point::B2DPoint aNextPoint(rCandidate.getB2DPoint(nNextIndex)); + double fRelative(fZero); + + if(!::basegfx::numeric::fTools::equalZero(fEdgeLength)) + { + fRelative = fDistance / fEdgeLength; + } + + // add calculated average value to the return value + aRetval += ::basegfx::tuple::average(aRetval, aNextPoint, fRelative); + } + } + + return aRetval; + } + + ::basegfx::point::B2DPoint getPositionRelative(const ::basegfx::polygon::B2DPolygon& rCandidate, double fDistance, double fLength) + { + // get length if not given + if(::basegfx::numeric::fTools::equalZero(fLength)) + { + fLength = getLength(rCandidate); + } + + // multiply fDistance with real length to get absolute position and + // use getPositionAbsolute + return getPositionAbsolute(rCandidate, fDistance * fLength, fLength); + } + + ::basegfx::vector::B2DVectorOrientation getPointOrientation(const ::basegfx::polygon::B2DPolygon& rCandidate, sal_uInt32 nIndex) + { + ::basegfx::vector::B2DVectorOrientation eRetval(::basegfx::vector::ORIENTATION_NEUTRAL); + + if(rCandidate.count() > 2) + { + sal_uInt32 nIndPrev = getIndexOfDifferentPredecessor(nIndex, rCandidate); + + if(nIndPrev != nIndex) + { + sal_uInt32 nIndNext = getIndexOfDifferentSuccessor(nIndex, rCandidate); + + if(nIndNext != nIndex && nIndNext != nIndPrev) + { + ::basegfx::point::B2DPoint aPoint(rCandidate.getB2DPoint(nIndex)); + ::basegfx::vector::B2DVector aVecPrev(rCandidate.getB2DPoint(nIndPrev) - aPoint); + ::basegfx::vector::B2DVector aVecNext(rCandidate.getB2DPoint(nIndNext) - aPoint); + eRetval = ::basegfx::vector::getOrientation(aVecPrev, aVecNext); + } + } } - return true; + return eRetval; } } // end of namespace tools } // end of namespace polygon |