Added PolyPolygonTools, Added PolygonTool functionality, changed bool to sal_Bool

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