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