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