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