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