Version 4.2.0.1, tag libreoffice-4.2.0.1
[LibreOffice.git] / basegfx / test / boxclipper.cxx
blobddc0a803685e7fb9ffa8dc6e6c7c6bf41f797e63
1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 /*
3 * This file is part of the LibreOffice project.
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/.
9 * This file incorporates work covered by the following license notice:
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 .
20 #include <sal/types.h>
21 #include <cppunit/TestAssert.h>
22 #include <cppunit/TestFixture.h>
23 #include <cppunit/extensions/HelperMacros.h>
25 #include <basegfx/matrix/b2dhommatrix.hxx>
26 #include <basegfx/curve/b2dcubicbezier.hxx>
27 #include <basegfx/curve/b2dbeziertools.hxx>
28 #include <basegfx/range/b2dpolyrange.hxx>
29 #include <basegfx/polygon/b2dpolygon.hxx>
30 #include <basegfx/polygon/b2dpolygontools.hxx>
31 #include <basegfx/polygon/b2dpolypolygontools.hxx>
32 #include <basegfx/polygon/b2dpolypolygoncutter.hxx>
33 #include <basegfx/polygon/b2dpolygonclipper.hxx>
34 #include <basegfx/polygon/b2dpolypolygon.hxx>
35 #include <basegfx/numeric/ftools.hxx>
37 #include <boost/bind.hpp>
39 using namespace ::basegfx;
42 namespace basegfx2d
44 /// Gets a random ordinal [0,n)
45 inline double getRandomOrdinal( const ::std::size_t n )
47 // use this one when displaying polygons in OOo, which still sucks
48 // great rocks when trying to import non-integer svg:d attributes
49 // return sal_Int64(double(n) * rand() / (RAND_MAX + 1.0));
50 return double(n) * rand() / (RAND_MAX + 1.0);
53 inline bool compare(const B2DPoint& left, const B2DPoint& right)
55 return left.getX()<right.getX()
56 || (left.getX()==right.getX() && left.getY()<right.getY());
60 class boxclipper : public CppUnit::TestFixture
62 private:
63 B2DPolyRange aDisjunctRanges;
64 B2DPolyRange aEqualRanges;
65 B2DPolyRange aIntersectionN;
66 B2DPolyRange aIntersectionE;
67 B2DPolyRange aIntersectionS;
68 B2DPolyRange aIntersectionW;
69 B2DPolyRange aIntersectionNE;
70 B2DPolyRange aIntersectionSE;
71 B2DPolyRange aIntersectionSW;
72 B2DPolyRange aIntersectionNW;
73 B2DPolyRange aRingIntersection;
74 B2DPolyRange aRingIntersection2;
75 B2DPolyRange aRingIntersectExtraStrip;
76 B2DPolyRange aComplexIntersections;
77 B2DPolyRange aRandomIntersections;
79 public:
80 // initialise your test code values here.
81 void setUp()
83 B2DRange aCenter(100, 100, -100, -100);
84 B2DRange aOffside(800, 800, 1000, 1000);
85 B2DRange aNorth(100, 0, -100, -200);
86 B2DRange aSouth(100, 200, -100, 0);
87 B2DRange aEast(0, 100, 200, -100);
88 B2DRange aWest(-200, 100, 0, -100);
89 B2DRange aNorthEast(0, 0, 200, -200);
90 B2DRange aSouthEast(0, 0, 200, 200);
91 B2DRange aSouthWest(0, 0, -200, 200);
92 B2DRange aNorthWest(0, 0, -200, -200);
94 B2DRange aNorth2(-150, 50, 150, 350);
95 B2DRange aSouth2(-150, -50, 150, -350);
96 B2DRange aEast2 (50, -150, 350, 150);
97 B2DRange aWest2 (-50, -150,-350, 150);
99 aDisjunctRanges.appendElement( aCenter, ORIENTATION_NEGATIVE );
100 aDisjunctRanges.appendElement( aOffside, ORIENTATION_NEGATIVE );
102 aEqualRanges.appendElement( aCenter, ORIENTATION_NEGATIVE );
103 aEqualRanges.appendElement( aCenter, ORIENTATION_NEGATIVE );
105 aIntersectionN.appendElement( aCenter, ORIENTATION_NEGATIVE );
106 aIntersectionN.appendElement( aNorth, ORIENTATION_NEGATIVE );
108 aIntersectionE.appendElement( aCenter, ORIENTATION_NEGATIVE );
109 aIntersectionE.appendElement( aEast, ORIENTATION_NEGATIVE );
111 aIntersectionS.appendElement( aCenter, ORIENTATION_NEGATIVE );
112 aIntersectionS.appendElement( aSouth, ORIENTATION_NEGATIVE );
114 aIntersectionW.appendElement( aCenter, ORIENTATION_NEGATIVE );
115 aIntersectionW.appendElement( aWest, ORIENTATION_NEGATIVE );
117 aIntersectionNE.appendElement( aCenter, ORIENTATION_NEGATIVE );
118 aIntersectionNE.appendElement( aNorthEast, ORIENTATION_NEGATIVE );
120 aIntersectionSE.appendElement( aCenter, ORIENTATION_NEGATIVE );
121 aIntersectionSE.appendElement( aSouthEast, ORIENTATION_NEGATIVE );
123 aIntersectionSW.appendElement( aCenter, ORIENTATION_NEGATIVE );
124 aIntersectionSW.appendElement( aSouthWest, ORIENTATION_NEGATIVE );
126 aIntersectionNW.appendElement( aCenter, ORIENTATION_NEGATIVE );
127 aIntersectionNW.appendElement( aNorthWest, ORIENTATION_NEGATIVE );
129 aRingIntersection.appendElement( aNorth2, ORIENTATION_NEGATIVE );
130 aRingIntersection.appendElement( aEast2, ORIENTATION_NEGATIVE );
131 aRingIntersection.appendElement( aSouth2, ORIENTATION_NEGATIVE );
133 aRingIntersection2 = aRingIntersection;
134 aRingIntersection2.appendElement( aWest2, ORIENTATION_NEGATIVE );
136 aRingIntersectExtraStrip = aRingIntersection2;
137 aRingIntersectExtraStrip.appendElement( B2DRange(0, -25, 200, 25),
138 ORIENTATION_NEGATIVE );
140 aComplexIntersections.appendElement( aCenter, ORIENTATION_NEGATIVE );
141 aComplexIntersections.appendElement( aOffside, ORIENTATION_NEGATIVE );
142 aComplexIntersections.appendElement( aCenter, ORIENTATION_NEGATIVE );
143 aComplexIntersections.appendElement( aNorth, ORIENTATION_NEGATIVE );
144 aComplexIntersections.appendElement( aEast, ORIENTATION_NEGATIVE );
145 aComplexIntersections.appendElement( aSouth, ORIENTATION_NEGATIVE );
146 aComplexIntersections.appendElement( aWest, ORIENTATION_NEGATIVE );
147 aComplexIntersections.appendElement( aNorthEast, ORIENTATION_NEGATIVE );
148 aComplexIntersections.appendElement( aSouthEast, ORIENTATION_NEGATIVE );
149 aComplexIntersections.appendElement( aSouthWest, ORIENTATION_NEGATIVE );
150 aComplexIntersections.appendElement( aNorthWest, ORIENTATION_NEGATIVE );
152 #ifdef GENERATE_RANDOM
153 for( int i=0; i<800; ++i )
155 B2DRange aRandomRange(
156 getRandomOrdinal( 1000 ),
157 getRandomOrdinal( 1000 ),
158 getRandomOrdinal( 1000 ),
159 getRandomOrdinal( 1000 ) );
161 aRandomIntersections.appendElement( aRandomRange, ORIENTATION_NEGATIVE );
163 #else
164 const char* randomSvg="m394 783h404v57h-404zm-197-505h571v576h-571zm356-634h75v200h-75zm-40-113h403v588h-403zm93-811h111v494h-111zm-364-619h562v121h-562zm-134-8h292v27h-292zm110 356h621v486h-621zm78-386h228v25h-228zm475-345h201v201h-201zm-2-93h122v126h-122zm-417-243h567v524h-567zm-266-738h863v456h-863zm262-333h315v698h-315zm-328-826h43v393h-43zm830-219h120v664h-120zm-311-636h221v109h-221zm-500 137h628v19h-628zm681-94h211v493h-211zm-366-646h384v355h-384zm-189-199h715v247h-715zm165-459h563v601h-563zm258-479h98v606h-98zm270-517h65v218h-65zm-44-259h96v286h-96zm-599-202h705v468h-705zm216-803h450v494h-450zm-150-22h26v167h-26zm-55-599h50v260h-50zm190-278h490v387h-490zm-290-453h634v392h-634zm257 189h552v300h-552zm-151-690h136v455h-136zm12-597h488v432h-488zm501-459h48v39h-48zm-224-112h429v22h-429zm-281 102h492v621h-492zm519-158h208v17h-208zm-681-563h56v427h-56zm126-451h615v392h-615zm-47-410h598v522h-598zm-32 316h79v110h-79zm-71-129h18v127h-18zm126-993h743v589h-743zm211-430h428v750h-428zm61-554h100v220h-100zm-353-49h658v157h-658zm778-383h115v272h-115zm-249-541h119v712h-119zm203 86h94v40h-94z";
165 B2DPolyPolygon randomPoly;
166 tools::importFromSvgD(
167 randomPoly,
168 OUString::createFromAscii(randomSvg), false, 0);
169 std::for_each(randomPoly.begin(),
170 randomPoly.end(),
171 boost::bind(
172 &B2DPolyRange::appendElement,
173 boost::ref(aRandomIntersections),
174 boost::bind(
175 &B2DPolygon::getB2DRange,
176 _1),
177 ORIENTATION_NEGATIVE,
178 1));
179 #endif
182 void tearDown()
186 B2DPolyPolygon normalizePoly( const B2DPolyPolygon& rPoly )
188 B2DPolyPolygon aRes;
189 for( sal_uInt32 i=0; i<rPoly.count(); ++i )
191 B2DPolygon aTmp=rPoly.getB2DPolygon(i);
192 if( ORIENTATION_NEGATIVE == tools::getOrientation(aTmp) )
193 aTmp.flip();
195 aTmp=tools::removeNeutralPoints(aTmp);
196 std::vector<B2DPoint> aTmp2(aTmp.count());
197 for(sal_uInt32 j=0; j<aTmp.count(); ++j)
198 aTmp2[j] = aTmp.getB2DPoint(j);
200 std::vector<B2DPoint>::iterator pSmallest=aTmp2.end();
201 for(std::vector<B2DPoint>::iterator pCurr=aTmp2.begin(); pCurr!=aTmp2.end(); ++pCurr)
203 if( pSmallest == aTmp2.end() || compare(*pCurr, *pSmallest) )
205 pSmallest=pCurr;
209 if( pSmallest != aTmp2.end() )
210 std::rotate(aTmp2.begin(),pSmallest,aTmp2.end());
212 aTmp.clear();
213 for(std::vector<B2DPoint>::iterator pCurr=aTmp2.begin(); pCurr!=aTmp2.end(); ++pCurr)
214 aTmp.append(*pCurr);
216 aRes.append(aTmp);
219 // boxclipper & generic clipper disagree slightly on area-less
220 // polygons (one or two points only)
221 aRes = tools::stripNeutralPolygons(aRes);
223 // now, sort all polygons with increasing 0th point
224 std::sort(aRes.begin(),
225 aRes.end(),
226 boost::bind(
227 &compare,
228 boost::bind(
229 &B2DPolygon::getB2DPoint,
230 _1,0),
231 boost::bind(
232 &B2DPolygon::getB2DPoint,
233 _2,0)));
235 return aRes;
238 void verifyPoly(const char* sName, const char* sSvg, const B2DPolyRange& toTest)
240 B2DPolyPolygon aTmp1;
241 CPPUNIT_ASSERT_MESSAGE(sName,
242 tools::importFromSvgD(
243 aTmp1, OUString::createFromAscii(sSvg), false, 0));
245 const OUString aSvg=
246 tools::exportToSvgD(toTest.solveCrossovers(), true, true, false);
247 B2DPolyPolygon aTmp2;
248 CPPUNIT_ASSERT_MESSAGE(sName,
249 tools::importFromSvgD(
250 aTmp2, aSvg, false, 0));
252 CPPUNIT_ASSERT_MESSAGE(
253 sName,
254 normalizePoly(aTmp2) == normalizePoly(aTmp1));
257 void verifyPoly()
259 const char* disjunct="m-100-100v200h200v-200zm900 900v200h200v-200z";
260 const char* equal="m-100-100v200h200v-200zm200 0h-200v200h200v-200z";
261 const char* intersectionN="m-100-100v100h200v-100zm200 0v-100h-200v100 200h200v-200z";
262 const char* intersectionE="m0-100v200h100v-200zm0 0h-100v200h100 200v-200z";
263 const char* intersectionS="m-100 0v100h200v-100zm0-100v200 100h200v-100-200z";
264 const char* intersectionW="m-100-100v200h100v-200zm0 0h-100v200h100 200v-200z";
265 const char* intersectionNE="m0-100v100h100v-100zm0-100v100h-100v200h200v-100h100v-200z";
266 const char* intersectionSE="m0 0v100h100v-100zm100 0v-100h-200v200h100v100h200v-200z";
267 const char* intersectionSW="m-100 0v100h100v-100zm0-100v100h-100v200h200v-100h100v-200z";
268 const char* intersectionNW="m-100-100v100h100v-100zm100 0v-100h-200v200h100v100h200v-200z";
269 const char* ringIntersection="m50-150v100h100v-100zm0 200v100h100v-100zm100-200v-200h-300v300h200v100h-200v300h300v-200h200v-300z";
270 const char* ringIntersection2="m-150 50v100h100v-100zm0-200v100h100v-100zm100 200v-100h100v100z"
271 "m100-200v100h100v-100zm0 200v100h100v-100zm100-200v-200h-300v200h-200v300h200v200h300v-200h200v-300z";
272 const char* ringIntersectExtraStrip="m-150 50v100h100v-100zm0-200v100h100v-100zm100 200v-100h100v25h-50v50h50v25z"
273 "m100-200v100h100v-100zm0 200v100h100v-100zm0-75v50h150v-50z"
274 "m100-125v-200h-300v200h-200v300h200v200h300v-200h200v-300z";
275 const char* complexIntersections="m0 0zm0 0zm0 0zm0 0v-100 100h-100 100v100-100h100zm0 0v-100 100h-100 100v100-100h100z"
276 "m100 0v-100h-100-100v100 100h100 100v-100zm0 0v-100h-100-100v100 100h100 100v-100z"
277 "m0 0v-100h-100v-100 100h-100v100h-100 100v100h100v100-100h100v-100h100z"
278 "m0-100v-100h-100-100v100h-100v100 100h100v100h100 100v-100h100v-100-100z"
279 "m100 0v-100h-200-100-100v100 200 100h100 100 200v-100-200zm600 900v200h200v-200z";
280 const char* randomIntersections="m20-4515v393h43v-393zm34-8690v127h18v-127zm24 674v427h56v-427zm126-451v16-16z"
281 "m22 3470v260h50v-260zm55 599v167h26v-167zm-49-1831v455h136v-455z"
282 "m10 8845v19h158v-19zm54-38v25h228v-25zm156-13245v108h100v-108z"
283 "m101 14826v200h75v-200zm-205-3000v365h315v-365zm-309-1877v19h628v-19z"
284 "m549-1398v127h98v-127zm18 5351v215h111v-215zm-362-10061v152h488v-152z"
285 "m488 0v-469h-492v621h4v280h488v-432zm-378 5368v48h384v-48zm274-10182v712h119v-712z"
286 "m-424 3173v-94h-47v110h47v96h551v-112zm-105-2249v157h353v112h100v-112h205v-157z"
287 "m284 5177v203h377v-203zm337 4727v66h40v-66zm-326 6110v57h374v-57zm351-12583v39h48v-39z"
288 "m23 12583v-505h-571v576h571v-14h30v-57zm-368-2682v-8h-292v27h134v102h562v-121z"
289 "m-9-12299v320h428v-320zm364 1216v-410h-598v316h-32v110h32v96h47v280h615v-392z"
290 "m-537 11431v486h388v279h111v-279h122v-486zm112-4621v142h550v-142zm101-2719v494h450v-494z"
291 "m340 6609v33h120v-33zm-85-4349v-479h-98v479h-258v459h-165v247h189v307h384v-307h142v-105h13v-601z"
292 "m-270-3159v36h490v-36zm442 2163v7h52v-7zm-345 7158v588h403v-588zm378-1813v-93h-122v126h2v155h148v-188z"
293 "m19-5345v-259h-96v266h44v20h52v-20h10v-7zm-91-6571v-430h-428v430h-211v589h743v-589z"
294 "m101 6571v-461h-705v468h599v20h44v191h65v-218zm-89-8442v40h94v-40zm-71 10742v-43h-221v109h181v427h211v-493z"
295 "m0-4727v-189h-634v392h257v97h33v351h490v-351h29v-300zm-97 6698v-333h-315v333h-262v456h863v-456z"
296 "m-142-8556v22h429v-22zm238-56v17h208v-17zm91 7234v664h120v-664zm69 2452v-336h-567v524h419v13h201v-201z"
297 "m-42-13332v272h115v-272z";
299 verifyPoly("disjunct", disjunct, aDisjunctRanges);
300 verifyPoly("equal", equal, aEqualRanges);
301 verifyPoly("intersectionN", intersectionN, aIntersectionN);
302 verifyPoly("intersectionE", intersectionE, aIntersectionE);
303 verifyPoly("intersectionS", intersectionS, aIntersectionS);
304 verifyPoly("intersectionW", intersectionW, aIntersectionW);
305 verifyPoly("intersectionNE", intersectionNE, aIntersectionNE);
306 verifyPoly("intersectionSE", intersectionSE, aIntersectionSE);
307 verifyPoly("intersectionSW", intersectionSW, aIntersectionSW);
308 verifyPoly("intersectionNW", intersectionNW, aIntersectionNW);
309 verifyPoly("ringIntersection", ringIntersection, aRingIntersection);
310 verifyPoly("ringIntersection2", ringIntersection2, aRingIntersection2);
311 verifyPoly("ringIntersectExtraStrip", ringIntersectExtraStrip, aRingIntersectExtraStrip);
312 verifyPoly("complexIntersections", complexIntersections, aComplexIntersections);
313 verifyPoly("randomIntersections", randomIntersections, aRandomIntersections);
316 void dumpSvg(const char* pName,
317 const ::basegfx::B2DPolyPolygon& rPoly)
319 (void)pName; (void)rPoly;
320 #if OSL_DEBUG_LEVEL > 2
321 fprintf(stderr, "%s - svg:d=\"%s\"\n",
322 pName, OUStringToOString(
323 basegfx::tools::exportToSvgD(rPoly, , true, true, false),
324 RTL_TEXTENCODING_UTF8).getStr() );
325 #endif
328 void getPolyPolygon()
330 dumpSvg("disjunct",aDisjunctRanges.solveCrossovers());
331 dumpSvg("equal",aEqualRanges.solveCrossovers());
332 dumpSvg("intersectionN",aIntersectionN.solveCrossovers());
333 dumpSvg("intersectionE",aIntersectionE.solveCrossovers());
334 dumpSvg("intersectionS",aIntersectionS.solveCrossovers());
335 dumpSvg("intersectionW",aIntersectionW.solveCrossovers());
336 dumpSvg("intersectionNE",aIntersectionNE.solveCrossovers());
337 dumpSvg("intersectionSE",aIntersectionSE.solveCrossovers());
338 dumpSvg("intersectionSW",aIntersectionSW.solveCrossovers());
339 dumpSvg("intersectionNW",aIntersectionNW.solveCrossovers());
340 dumpSvg("ringIntersection",aRingIntersection.solveCrossovers());
341 dumpSvg("ringIntersection2",aRingIntersection2.solveCrossovers());
342 dumpSvg("aRingIntersectExtraStrip",aRingIntersectExtraStrip.solveCrossovers());
343 dumpSvg("complexIntersections",aComplexIntersections.solveCrossovers());
344 dumpSvg("randomIntersections",aRandomIntersections.solveCrossovers());
346 CPPUNIT_ASSERT_MESSAGE("getPolyPolygon", true );
349 void validatePoly( const char* pName, const B2DPolyRange& rRange )
351 B2DPolyPolygon genericClip;
352 const sal_uInt32 nCount=rRange.count();
353 for( sal_uInt32 i=0; i<nCount; ++i )
355 B2DPolygon aRect=tools::createPolygonFromRect(
356 rRange.getElement(i).head);
357 if( rRange.getElement(i).tail.head == ORIENTATION_NEGATIVE )
358 aRect.flip();
360 genericClip.append(aRect);
363 #if OSL_DEBUG_LEVEL > 2
364 fprintf(stderr, "%s input - svg:d=\"%s\"\n",
365 pName, OUStringToOString(
366 basegfx::tools::exportToSvgD(
367 genericClip, , true, true, false),
368 RTL_TEXTENCODING_UTF8).getStr() );
369 #endif
371 const B2DPolyPolygon boxClipResult=rRange.solveCrossovers();
372 const OUString boxClipSvg(
373 basegfx::tools::exportToSvgD(
374 normalizePoly(boxClipResult), true, true, false));
375 #if OSL_DEBUG_LEVEL > 2
376 fprintf(stderr, "%s boxclipper - svg:d=\"%s\"\n",
377 pName, OUStringToOString(
378 boxClipSvg,
379 RTL_TEXTENCODING_UTF8).getStr() );
380 #endif
382 genericClip = tools::solveCrossovers(genericClip);
383 const OUString genericClipSvg(
384 basegfx::tools::exportToSvgD(
385 normalizePoly(genericClip), true, true, false));
386 #if OSL_DEBUG_LEVEL > 2
387 fprintf(stderr, "%s genclipper - svg:d=\"%s\"\n",
388 pName, OUStringToOString(
389 genericClipSvg,
390 RTL_TEXTENCODING_UTF8).getStr() );
391 #endif
393 CPPUNIT_ASSERT_MESSAGE(pName,
394 genericClipSvg == boxClipSvg);
397 void validatePoly()
399 validatePoly("disjunct", aDisjunctRanges);
400 validatePoly("equal", aEqualRanges);
401 validatePoly("intersectionN", aIntersectionN);
402 validatePoly("intersectionE", aIntersectionE);
403 validatePoly("intersectionS", aIntersectionS);
404 validatePoly("intersectionW", aIntersectionW);
405 validatePoly("intersectionNE", aIntersectionNE);
406 validatePoly("intersectionSE", aIntersectionSE);
407 validatePoly("intersectionSW", aIntersectionSW);
408 validatePoly("intersectionNW", aIntersectionNW);
409 // subtle differences on Solaris Intel, comparison not smart enough
410 // (due to floating point inaccuracies)
411 //validatePoly("ringIntersection", aRingIntersection);
412 //validatePoly("ringIntersection2", aRingIntersection2);
413 //validatePoly("ringIntersectExtraStrip", aRingIntersectExtraStrip);
414 // generic clipper buggy here, likely
415 //validatePoly("complexIntersections", aComplexIntersections);
416 //validatePoly("randomIntersections", aRandomIntersections);
419 // Change the following lines only, if you add, remove or rename
420 // member functions of the current class,
421 // because these macros are need by auto register mechanism.
423 CPPUNIT_TEST_SUITE(boxclipper);
424 CPPUNIT_TEST(validatePoly);
425 CPPUNIT_TEST(verifyPoly);
426 CPPUNIT_TEST(getPolyPolygon);
427 CPPUNIT_TEST_SUITE_END();
430 // -----------------------------------------------------------------------------
431 CPPUNIT_TEST_SUITE_REGISTRATION(basegfx2d::boxclipper);
432 } // namespace basegfx2d
434 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */