LibreOffice Module basegfx (master) 1
b2dpolygontriangulator.cxx
Go to the documentation of this file.
1/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2/*
3 * This file is part of the LibreOffice project.
4 *
5 * This Source Code Form is subject to the terms of the Mozilla Public
6 * License, v. 2.0. If a copy of the MPL was not distributed with this
7 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
8 *
9 * This file incorporates work covered by the following license notice:
10 *
11 * Licensed to the Apache Software Foundation (ASF) under one or more
12 * contributor license agreements. See the NOTICE file distributed
13 * with this work for additional information regarding copyright
14 * ownership. The ASF licenses this file to you under the Apache
15 * License, Version 2.0 (the "License"); you may not use this file
16 * except in compliance with the License. You may obtain a copy of
17 * the License at http://www.apache.org/licenses/LICENSE-2.0 .
18 */
19
29
30#include <algorithm>
31
32namespace basegfx
33{
34 namespace
35 {
36 class EdgeEntry
37 {
38 EdgeEntry* mpNext;
39 B2DPoint maStart;
40 B2DPoint maEnd;
41 double mfAtan2;
42
43 public:
44 EdgeEntry(const B2DPoint& rStart, const B2DPoint& rEnd)
45 : mpNext(nullptr),
46 maStart(rStart),
47 maEnd(rEnd),
48 mfAtan2(0.0)
49 {
50 // make sure edge goes down. If horizontal, let it go to the right (left-handed).
51 bool bSwap(false);
52
53 if(::basegfx::fTools::equal(maStart.getY(), maEnd.getY()))
54 {
55 if(maStart.getX() > maEnd.getX())
56 {
57 bSwap = true;
58 }
59 }
60 else if(maStart.getY() > maEnd.getY())
61 {
62 bSwap = true;
63 }
64
65 if(bSwap)
66 {
67 maStart = rEnd;
68 maEnd = rStart;
69 }
70
71 mfAtan2 = atan2(maEnd.getY() - maStart.getY(), maEnd.getX() - maStart.getX());
72 }
73
74 bool operator<(const EdgeEntry& rComp) const
75 {
76 if(::basegfx::fTools::equal(maStart.getY(), rComp.maStart.getY()))
77 {
78 if(::basegfx::fTools::equal(maStart.getX(), rComp.maStart.getX()))
79 {
80 // same in x and y -> same start point. Sort emitting vectors from left to right.
81 return (mfAtan2 > rComp.mfAtan2);
82 }
83
84 return (maStart.getX() < rComp.maStart.getX());
85 }
86
87 return (maStart.getY() < rComp.maStart.getY());
88 }
89
90 bool operator==(const EdgeEntry& rComp) const
91 {
92 return (maStart.equal(rComp.maStart) && maEnd.equal(rComp.maEnd));
93 }
94
95 bool operator!=(const EdgeEntry& rComp) const
96 {
97 return !(*this == rComp);
98 }
99
100 const B2DPoint& getStart() const { return maStart; }
101 const B2DPoint& getEnd() const { return maEnd; }
102
103 EdgeEntry* getNext() const { return mpNext; }
104 void setNext(EdgeEntry* pNext) { mpNext = pNext; }
105 };
106
107 typedef std::vector< EdgeEntry > EdgeEntries;
108
109 class Triangulator
110 {
111 EdgeEntry* mpList;
112 EdgeEntries maStartEntries;
113 std::vector< std::unique_ptr<EdgeEntry> > maNewEdgeEntries;
115
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);
119
120 public:
121 explicit Triangulator(const B2DPolyPolygon& rCandidate);
122
123 const triangulator::B2DTriangleVector& getResult() const { return maResult; }
124 };
125
126 void Triangulator::handleClosingEdge(const B2DPoint& rStart, const B2DPoint& rEnd)
127 {
128 // create an entry, else the comparison might use the wrong edges
129 EdgeEntry aNew(rStart, rEnd);
130 EdgeEntry* pCurr = mpList;
131 EdgeEntry* pPrev = nullptr;
132
133 while(pCurr
134 && pCurr->getStart().getY() <= aNew.getStart().getY()
135 && *pCurr != aNew)
136 {
137 pPrev = pCurr;
138 pCurr = pCurr->getNext();
139 }
140
141 if(pCurr && *pCurr == aNew)
142 {
143 // found closing edge, remove
144 if(pPrev)
145 {
146 pPrev->setNext(pCurr->getNext());
147 }
148 else
149 {
150 mpList = pCurr->getNext();
151 }
152 }
153 else
154 {
155 // insert closing edge
156 EdgeEntry* pNew = new EdgeEntry(aNew);
157 maNewEdgeEntries.emplace_back(pNew);
158 pCurr = mpList;
159 pPrev = nullptr;
160
161 while(pCurr && *pCurr < *pNew)
162 {
163 pPrev = pCurr;
164 pCurr = pCurr->getNext();
165 }
166
167 if(pPrev)
168 {
169 pNew->setNext(pPrev->getNext());
170 pPrev->setNext(pNew);
171 }
172 else
173 {
174 pNew->setNext(mpList);
175 mpList = pNew;
176 }
177 }
178 }
179
180 bool Triangulator::CheckPointInTriangle(EdgeEntry* pEdgeA, EdgeEntry const * pEdgeB, const B2DPoint& rTestPoint)
181 {
182 // inside triangle or on edge?
183 if(!utils::isPointInTriangle(pEdgeA->getStart(), pEdgeA->getEnd(), pEdgeB->getEnd(), rTestPoint, true))
184 return true;
185
186 // but not on point
187 if(!rTestPoint.equal(pEdgeA->getEnd()) && !rTestPoint.equal(pEdgeB->getEnd()))
188 {
189 // found point in triangle -> split triangle inserting two edges
190 EdgeEntry* pStart = new EdgeEntry(pEdgeA->getStart(), rTestPoint);
191 EdgeEntry* pEnd = new EdgeEntry(*pStart);
192 maNewEdgeEntries.emplace_back(pStart);
193 maNewEdgeEntries.emplace_back(pEnd);
194
195 pStart->setNext(pEnd);
196 pEnd->setNext(pEdgeA->getNext());
197 pEdgeA->setNext(pStart);
198
199 return false;
200 }
201
202 return true;
203 }
204
205 void Triangulator::createTriangle(const B2DPoint& rA, const B2DPoint& rB, const B2DPoint& rC)
206 {
207 maResult.emplace_back(
208 rA,
209 rB,
210 rC);
211 }
212
213 // consume as long as there are edges
214 Triangulator::Triangulator(const B2DPolyPolygon& rCandidate)
215 : mpList(nullptr)
216 {
217 // add all available edges to the single linked local list which will be sorted
218 // by Y,X,atan2 when adding nodes
219 if(rCandidate.count())
220 {
221 for(sal_uInt32 a(0); a < rCandidate.count(); a++)
222 {
223 const B2DPolygon& aPolygonCandidate(rCandidate.getB2DPolygon(a));
224 const sal_uInt32 nCount(aPolygonCandidate.count());
225
226 if(nCount > 2)
227 {
228 B2DPoint aPrevPnt(aPolygonCandidate.getB2DPoint(nCount - 1));
229
230 for(sal_uInt32 b(0); b < nCount; b++)
231 {
232 B2DPoint aNextPnt(aPolygonCandidate.getB2DPoint(b));
233
234 if( !aPrevPnt.equal(aNextPnt) )
235 {
236 maStartEntries.emplace_back(aPrevPnt, aNextPnt);
237 }
238
239 aPrevPnt = aNextPnt;
240 }
241 }
242 }
243
244 if(!maStartEntries.empty())
245 {
246 // sort initial list
247 std::sort(maStartEntries.begin(), maStartEntries.end());
248
249 // insert to own simply linked list
250 EdgeEntries::iterator aPos(maStartEntries.begin());
251 mpList = &(*aPos++);
252 EdgeEntry* pLast = mpList;
253
254 while(aPos != maStartEntries.end())
255 {
256 EdgeEntry* pEntry = &(*aPos++);
257 pLast->setNext(pEntry);
258 pLast = pEntry;
259 }
260 }
261 }
262
263 while(mpList)
264 {
265 if(mpList->getNext() && mpList->getNext()->getStart().equal(mpList->getStart()))
266 {
267 // next candidate. There are two edges and start point is equal.
268 // Length is not zero.
269 EdgeEntry* pEdgeA = mpList;
270 EdgeEntry* pEdgeB = pEdgeA->getNext();
271
272 if( pEdgeA->getEnd().equal(pEdgeB->getEnd()) )
273 {
274 // start and end equal -> neutral triangle, delete both
275 mpList = pEdgeB->getNext();
276 }
277 else
278 {
279 const B2DVector aLeft(pEdgeA->getEnd() - pEdgeA->getStart());
280 const B2DVector aRight(pEdgeB->getEnd() - pEdgeA->getStart());
281
282 if(getOrientation(aLeft, aRight) == B2VectorOrientation::Neutral)
283 {
284 // edges are parallel and have different length -> neutral triangle,
285 // delete both edges and handle closing edge
286 mpList = pEdgeB->getNext();
287 handleClosingEdge(pEdgeA->getEnd(), pEdgeB->getEnd());
288 }
289 else
290 {
291 // not parallel, look for points inside
292 B2DRange aRange(pEdgeA->getStart(), pEdgeA->getEnd());
293 aRange.expand(pEdgeB->getEnd());
294 EdgeEntry* pTestEdge = pEdgeB->getNext();
295 bool bNoPointInTriangle(true);
296
297 // look for start point in triangle
298 while(bNoPointInTriangle && pTestEdge)
299 {
300 if(aRange.getMaxY() < pTestEdge->getStart().getY())
301 {
302 // edge is below test range and edges are sorted -> stop looking
303 break;
304 }
305 else
306 {
307 // do not look for edges with same start point, they are sorted and cannot end inside.
308 if(!pTestEdge->getStart().equal(pEdgeA->getStart()))
309 {
310 if(aRange.isInside(pTestEdge->getStart()))
311 {
312 bNoPointInTriangle = CheckPointInTriangle(pEdgeA, pEdgeB, pTestEdge->getStart());
313 }
314 }
315 }
316
317 // next candidate
318 pTestEdge = pTestEdge->getNext();
319 }
320
321 if(bNoPointInTriangle)
322 {
323 // look for end point in triangle
324 pTestEdge = pEdgeB->getNext();
325
326 while(bNoPointInTriangle && pTestEdge)
327 {
328 if(aRange.getMaxY() < pTestEdge->getStart().getY())
329 {
330 // edge is below test range and edges are sorted -> stop looking
331 break;
332 }
333 else
334 {
335 // do not look for edges with same end point, they are sorted and cannot end inside.
336 if(!pTestEdge->getEnd().equal(pEdgeA->getStart()))
337 {
338 if(aRange.isInside(pTestEdge->getEnd()))
339 {
340 bNoPointInTriangle = CheckPointInTriangle(pEdgeA, pEdgeB, pTestEdge->getEnd());
341 }
342 }
343 }
344
345 // next candidate
346 pTestEdge = pTestEdge->getNext();
347 }
348 }
349
350 if(bNoPointInTriangle)
351 {
352 // create triangle, remove edges, handle closing edge
353 mpList = pEdgeB->getNext();
354 createTriangle(pEdgeA->getStart(), pEdgeB->getEnd(), pEdgeA->getEnd());
355 handleClosingEdge(pEdgeA->getEnd(), pEdgeB->getEnd());
356 }
357 }
358 }
359 }
360 else
361 {
362 // only one entry at start point, delete it
363 mpList = mpList->getNext();
364 }
365 }
366 }
367
368 } // end of anonymous namespace
369} // end of namespace basegfx
370
372{
374 {
375 B2DTriangleVector aRetval;
376
377 // subdivide locally (triangulate does not work with beziers), remove double and neutral points
378 B2DPolygon aCandidate(rCandidate.areControlPointsUsed() ? utils::adaptiveSubdivideByAngle(rCandidate) : rCandidate);
379 aCandidate.removeDoublePoints();
380 aCandidate = utils::removeNeutralPoints(aCandidate);
381
382 if(aCandidate.count() == 2)
383 {
384 // candidate IS a triangle, just append
385 aRetval.emplace_back(
386 aCandidate.getB2DPoint(0),
387 aCandidate.getB2DPoint(1),
388 aCandidate.getB2DPoint(2));
389 }
390 else if(aCandidate.count() > 2)
391 {
392 if(utils::isConvex(aCandidate))
393 {
394 // polygon is convex, just use a triangle fan
395 utils::addTriangleFan(aCandidate, aRetval);
396 }
397 else
398 {
399 // polygon is concave.
400 const B2DPolyPolygon aCandPolyPoly(aCandidate);
401 Triangulator aTriangulator(aCandPolyPoly);
402
403 aRetval = aTriangulator.getResult();
404 }
405 }
406
407 return aRetval;
408 }
409
411 {
412 B2DTriangleVector aRetval;
413
414 // subdivide locally (triangulate does not work with beziers)
415 B2DPolyPolygon aCandidate(rCandidate.areControlPointsUsed() ? utils::adaptiveSubdivideByAngle(rCandidate) : rCandidate);
416
417 if(aCandidate.count() == 1)
418 {
419 // single polygon -> single polygon triangulation
420 const B2DPolygon& aSinglePolygon(aCandidate.getB2DPolygon(0));
421
422 aRetval = triangulate(aSinglePolygon);
423 }
424 else
425 {
426 Triangulator aTriangulator(aCandidate);
427
428 aRetval = aTriangulator.getResult();
429 }
430
431 return aRetval;
432 }
433} // end of namespace
434
435/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
EdgeEntry * mpNext
triangulator::B2DTriangleVector maResult
B2DPoint maStart
B2DPoint maEnd
EdgeEntries maStartEntries
double mfAtan2
std::vector< std::unique_ptr< EdgeEntry > > maNewEdgeEntries
EdgeEntry * mpList
B2DPolygon const & getB2DPolygon(sal_uInt32 nIndex) const
bool areControlPointsUsed() const
sal_uInt32 count() 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
int nCount
uno_Any a
::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)