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