44 EdgeEntry(
const B2DPoint& rStart,
const B2DPoint& rEnd)
53 if(::basegfx::fTools::equal(
maStart.getY(),
maEnd.getY()))
74 bool operator<(
const EdgeEntry& rComp)
const
76 if(::basegfx::fTools::equal(
maStart.getY(), rComp.maStart.getY()))
78 if(::basegfx::fTools::equal(
maStart.getX(), rComp.maStart.getX()))
81 return (
mfAtan2 > rComp.mfAtan2);
84 return (
maStart.getX() < rComp.maStart.getX());
87 return (
maStart.getY() < rComp.maStart.getY());
92 return (
maStart.equal(rComp.maStart) &&
maEnd.equal(rComp.maEnd));
97 return !(*
this == rComp);
100 const B2DPoint& getStart()
const {
return maStart; }
101 const B2DPoint& getEnd()
const {
return maEnd; }
103 EdgeEntry* getNext()
const {
return mpNext; }
104 void setNext(EdgeEntry* pNext) {
mpNext = pNext; }
107 typedef std::vector< EdgeEntry > EdgeEntries;
116 void handleClosingEdge(
const B2DPoint& rStart,
const B2DPoint& rEnd);
117 bool CheckPointInTriangle(EdgeEntry* pEdgeA, EdgeEntry
const * pEdgeB,
const B2DPoint& rTestPoint);
118 void createTriangle(
const B2DPoint& rA,
const B2DPoint& rB,
const B2DPoint& rC);
121 explicit Triangulator(
const B2DPolyPolygon& rCandidate);
126 void Triangulator::handleClosingEdge(
const B2DPoint& rStart,
const B2DPoint& rEnd)
129 EdgeEntry aNew(rStart, rEnd);
130 EdgeEntry* pCurr =
mpList;
131 EdgeEntry* pPrev =
nullptr;
134 && pCurr->getStart().getY() <= aNew.getStart().getY()
138 pCurr = pCurr->getNext();
141 if(pCurr && *pCurr == aNew)
146 pPrev->setNext(pCurr->getNext());
150 mpList = pCurr->getNext();
156 EdgeEntry* pNew =
new EdgeEntry(aNew);
161 while(pCurr && *pCurr < *pNew)
164 pCurr = pCurr->getNext();
169 pNew->setNext(pPrev->getNext());
170 pPrev->setNext(pNew);
180 bool Triangulator::CheckPointInTriangle(EdgeEntry* pEdgeA, EdgeEntry
const * pEdgeB,
const B2DPoint& rTestPoint)
187 if(!rTestPoint.equal(pEdgeA->getEnd()) && !rTestPoint.equal(pEdgeB->getEnd()))
190 EdgeEntry* pStart =
new EdgeEntry(pEdgeA->getStart(), rTestPoint);
191 EdgeEntry* pEnd =
new EdgeEntry(*pStart);
195 pStart->setNext(pEnd);
196 pEnd->setNext(pEdgeA->getNext());
197 pEdgeA->setNext(pStart);
205 void Triangulator::createTriangle(
const B2DPoint& rA,
const B2DPoint& rB,
const B2DPoint& rC)
214 Triangulator::Triangulator(
const B2DPolyPolygon& rCandidate)
219 if(rCandidate.count())
221 for(sal_uInt32
a(0);
a < rCandidate.count();
a++)
223 const B2DPolygon& aPolygonCandidate(rCandidate.getB2DPolygon(a));
224 const sal_uInt32
nCount(aPolygonCandidate.count());
228 B2DPoint aPrevPnt(aPolygonCandidate.getB2DPoint(nCount - 1));
230 for(sal_uInt32 b(0); b <
nCount; b++)
232 B2DPoint aNextPnt(aPolygonCandidate.getB2DPoint(b));
234 if( !aPrevPnt.equal(aNextPnt) )
252 EdgeEntry* pLast =
mpList;
256 EdgeEntry* pEntry = &(*aPos++);
257 pLast->setNext(pEntry);
269 EdgeEntry* pEdgeA =
mpList;
270 EdgeEntry* pEdgeB = pEdgeA->getNext();
272 if( pEdgeA->getEnd().equal(pEdgeB->getEnd()) )
275 mpList = pEdgeB->getNext();
279 const B2DVector aLeft(pEdgeA->getEnd() - pEdgeA->getStart());
280 const B2DVector aRight(pEdgeB->getEnd() - pEdgeA->getStart());
286 mpList = pEdgeB->getNext();
287 handleClosingEdge(pEdgeA->getEnd(), pEdgeB->getEnd());
292 B2DRange aRange(pEdgeA->getStart(), pEdgeA->getEnd());
293 aRange.expand(pEdgeB->getEnd());
294 EdgeEntry* pTestEdge = pEdgeB->getNext();
295 bool bNoPointInTriangle(
true);
298 while(bNoPointInTriangle && pTestEdge)
300 if(aRange.getMaxY() < pTestEdge->getStart().getY())
308 if(!pTestEdge->getStart().equal(pEdgeA->getStart()))
310 if(aRange.isInside(pTestEdge->getStart()))
312 bNoPointInTriangle = CheckPointInTriangle(pEdgeA, pEdgeB, pTestEdge->getStart());
318 pTestEdge = pTestEdge->getNext();
321 if(bNoPointInTriangle)
324 pTestEdge = pEdgeB->getNext();
326 while(bNoPointInTriangle && pTestEdge)
328 if(aRange.getMaxY() < pTestEdge->getStart().getY())
336 if(!pTestEdge->getEnd().equal(pEdgeA->getStart()))
338 if(aRange.isInside(pTestEdge->getEnd()))
340 bNoPointInTriangle = CheckPointInTriangle(pEdgeA, pEdgeB, pTestEdge->getEnd());
346 pTestEdge = pTestEdge->getNext();
350 if(bNoPointInTriangle)
353 mpList = pEdgeB->getNext();
354 createTriangle(pEdgeA->getStart(), pEdgeB->getEnd(), pEdgeA->getEnd());
355 handleClosingEdge(pEdgeA->getEnd(), pEdgeB->getEnd());
382 if(aCandidate.
count() == 2)
385 aRetval.emplace_back(
390 else if(aCandidate.
count() > 2)
401 Triangulator aTriangulator(aCandPolyPoly);
403 aRetval = aTriangulator.getResult();
417 if(aCandidate.
count() == 1)
426 Triangulator aTriangulator(aCandidate);
428 aRetval = aTriangulator.getResult();
triangulator::B2DTriangleVector maResult
EdgeEntries maStartEntries
std::vector< std::unique_ptr< EdgeEntry > > maNewEdgeEntries
B2DPolygon const & getB2DPolygon(sal_uInt32 nIndex) const
bool areControlPointsUsed() const
basegfx::B2DPoint const & getB2DPoint(sal_uInt32 nIndex) const
Coordinate interface.
bool areControlPointsUsed() const
ControlPoint checks.
void removeDoublePoints()
remove double points, at the begin/end and follow-ups, too
sal_uInt32 count() const
member count
::std::vector< B2DTriangle > B2DTriangleVector
B2DTriangleVector triangulate(const B2DPolygon &rCandidate)
B2DPolygon removeNeutralPoints(const B2DPolygon &rCandidate)
void addTriangleFan(const B2DPolygon &rCandidate, triangulator::B2DTriangleVector &rTarget)
B2VectorOrientation getOrientation(const B2DPolygon &rCandidate)
B2DPolygon adaptiveSubdivideByAngle(const B2DPolygon &rCandidate, double fAngleBound)
bool isConvex(const B2DPolygon &rCandidate)
bool isPointInTriangle(const B2DPoint &rA, const B2DPoint &rB, const B2DPoint &rC, const B2DPoint &rCandidate, bool bWithBorder)
bool operator<(const wwFont &r1, const wwFont &r2)
bool operator!=(const XclExpString &rLeft, const XclExpString &rRight)
bool operator==(const XclFontData &rLeft, const XclFontData &rRight)