1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 /*************************************************************************
4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
6 * Copyright 2000, 2010 Oracle and/or its affiliates.
8 * OpenOffice.org - a multi-platform office productivity suite
10 * This file is part of OpenOffice.org.
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.
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).
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.
27 ************************************************************************/
29 #include "sal/config.h"
30 #include "sal/precppunit.hxx"
32 // autogenerated file with codegen.pl
34 #include "cppunit/TestAssert.h"
35 #include "cppunit/TestFixture.h"
36 #include "cppunit/extensions/HelperMacros.h"
38 #include <basegfx/matrix/b2dhommatrix.hxx>
39 #include <basegfx/curve/b2dcubicbezier.hxx>
40 #include <basegfx/curve/b2dbeziertools.hxx>
41 #include <basegfx/range/b2dpolyrange.hxx>
42 #include <basegfx/polygon/b2dpolygon.hxx>
43 #include <basegfx/polygon/b2dpolygontools.hxx>
44 #include <basegfx/polygon/b2dpolypolygontools.hxx>
45 #include <basegfx/polygon/b2dpolypolygoncutter.hxx>
46 #include <basegfx/polygon/b2dpolygonclipper.hxx>
47 #include <basegfx/polygon/b2dpolypolygon.hxx>
48 #include <basegfx/numeric/ftools.hxx>
50 #include <boost/bind.hpp>
52 using namespace ::basegfx
;
57 /// Gets a random ordinal [0,n)
58 inline double getRandomOrdinal( const ::std::size_t n
)
60 // use this one when displaying polygons in OOo, which still sucks
61 // great rocks when trying to import non-integer svg:d attributes
62 // return sal_Int64(double(n) * rand() / (RAND_MAX + 1.0));
63 return double(n
) * rand() / (RAND_MAX
+ 1.0);
66 inline bool compare(const B2DPoint
& left
, const B2DPoint
& right
)
68 return left
.getX()<right
.getX()
69 || (left
.getX()==right
.getX() && left
.getY()<right
.getY());
73 class boxclipper
: public CppUnit::TestFixture
76 B2DPolyRange aDisjunctRanges
;
77 B2DPolyRange aEqualRanges
;
78 B2DPolyRange aIntersectionN
;
79 B2DPolyRange aIntersectionE
;
80 B2DPolyRange aIntersectionS
;
81 B2DPolyRange aIntersectionW
;
82 B2DPolyRange aIntersectionNE
;
83 B2DPolyRange aIntersectionSE
;
84 B2DPolyRange aIntersectionSW
;
85 B2DPolyRange aIntersectionNW
;
86 B2DPolyRange aRingIntersection
;
87 B2DPolyRange aRingIntersection2
;
88 B2DPolyRange aRingIntersectExtraStrip
;
89 B2DPolyRange aComplexIntersections
;
90 B2DPolyRange aRandomIntersections
;
93 // initialise your test code values here.
96 B2DRange
aCenter(100, 100, -100, -100);
97 B2DRange
aOffside(800, 800, 1000, 1000);
98 B2DRange
aNorth(100, 0, -100, -200);
99 B2DRange
aSouth(100, 200, -100, 0);
100 B2DRange
aEast(0, 100, 200, -100);
101 B2DRange
aWest(-200, 100, 0, -100);
102 B2DRange
aNorthEast(0, 0, 200, -200);
103 B2DRange
aSouthEast(0, 0, 200, 200);
104 B2DRange
aSouthWest(0, 0, -200, 200);
105 B2DRange
aNorthWest(0, 0, -200, -200);
107 B2DRange
aNorth2(-150, 50, 150, 350);
108 B2DRange
aSouth2(-150, -50, 150, -350);
109 B2DRange
aEast2 (50, -150, 350, 150);
110 B2DRange
aWest2 (-50, -150,-350, 150);
112 aDisjunctRanges
.appendElement( aCenter
, ORIENTATION_NEGATIVE
);
113 aDisjunctRanges
.appendElement( aOffside
, ORIENTATION_NEGATIVE
);
115 aEqualRanges
.appendElement( aCenter
, ORIENTATION_NEGATIVE
);
116 aEqualRanges
.appendElement( aCenter
, ORIENTATION_NEGATIVE
);
118 aIntersectionN
.appendElement( aCenter
, ORIENTATION_NEGATIVE
);
119 aIntersectionN
.appendElement( aNorth
, ORIENTATION_NEGATIVE
);
121 aIntersectionE
.appendElement( aCenter
, ORIENTATION_NEGATIVE
);
122 aIntersectionE
.appendElement( aEast
, ORIENTATION_NEGATIVE
);
124 aIntersectionS
.appendElement( aCenter
, ORIENTATION_NEGATIVE
);
125 aIntersectionS
.appendElement( aSouth
, ORIENTATION_NEGATIVE
);
127 aIntersectionW
.appendElement( aCenter
, ORIENTATION_NEGATIVE
);
128 aIntersectionW
.appendElement( aWest
, ORIENTATION_NEGATIVE
);
130 aIntersectionNE
.appendElement( aCenter
, ORIENTATION_NEGATIVE
);
131 aIntersectionNE
.appendElement( aNorthEast
, ORIENTATION_NEGATIVE
);
133 aIntersectionSE
.appendElement( aCenter
, ORIENTATION_NEGATIVE
);
134 aIntersectionSE
.appendElement( aSouthEast
, ORIENTATION_NEGATIVE
);
136 aIntersectionSW
.appendElement( aCenter
, ORIENTATION_NEGATIVE
);
137 aIntersectionSW
.appendElement( aSouthWest
, ORIENTATION_NEGATIVE
);
139 aIntersectionNW
.appendElement( aCenter
, ORIENTATION_NEGATIVE
);
140 aIntersectionNW
.appendElement( aNorthWest
, ORIENTATION_NEGATIVE
);
142 aRingIntersection
.appendElement( aNorth2
, ORIENTATION_NEGATIVE
);
143 aRingIntersection
.appendElement( aEast2
, ORIENTATION_NEGATIVE
);
144 aRingIntersection
.appendElement( aSouth2
, ORIENTATION_NEGATIVE
);
146 aRingIntersection2
= aRingIntersection
;
147 aRingIntersection2
.appendElement( aWest2
, ORIENTATION_NEGATIVE
);
149 aRingIntersectExtraStrip
= aRingIntersection2
;
150 aRingIntersectExtraStrip
.appendElement( B2DRange(0, -25, 200, 25),
151 ORIENTATION_NEGATIVE
);
153 aComplexIntersections
.appendElement( aCenter
, ORIENTATION_NEGATIVE
);
154 aComplexIntersections
.appendElement( aOffside
, ORIENTATION_NEGATIVE
);
155 aComplexIntersections
.appendElement( aCenter
, ORIENTATION_NEGATIVE
);
156 aComplexIntersections
.appendElement( aNorth
, ORIENTATION_NEGATIVE
);
157 aComplexIntersections
.appendElement( aEast
, ORIENTATION_NEGATIVE
);
158 aComplexIntersections
.appendElement( aSouth
, ORIENTATION_NEGATIVE
);
159 aComplexIntersections
.appendElement( aWest
, ORIENTATION_NEGATIVE
);
160 aComplexIntersections
.appendElement( aNorthEast
, ORIENTATION_NEGATIVE
);
161 aComplexIntersections
.appendElement( aSouthEast
, ORIENTATION_NEGATIVE
);
162 aComplexIntersections
.appendElement( aSouthWest
, ORIENTATION_NEGATIVE
);
163 aComplexIntersections
.appendElement( aNorthWest
, ORIENTATION_NEGATIVE
);
165 #ifdef GENERATE_RANDOM
166 for( int i
=0; i
<800; ++i
)
168 B2DRange
aRandomRange(
169 getRandomOrdinal( 1000 ),
170 getRandomOrdinal( 1000 ),
171 getRandomOrdinal( 1000 ),
172 getRandomOrdinal( 1000 ) );
174 aRandomIntersections
.appendElement( aRandomRange
, ORIENTATION_NEGATIVE
);
177 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";
178 B2DPolyPolygon randomPoly
;
179 tools::importFromSvgD(
181 rtl::OUString::createFromAscii(randomSvg
));
182 std::for_each(randomPoly
.begin(),
185 &B2DPolyRange::appendElement
,
186 boost::ref(aRandomIntersections
),
188 &B2DPolygon::getB2DRange
,
190 ORIENTATION_NEGATIVE
,
199 B2DPolyPolygon
normalizePoly( const B2DPolyPolygon
& rPoly
)
202 for( sal_uInt32 i
=0; i
<rPoly
.count(); ++i
)
204 B2DPolygon aTmp
=rPoly
.getB2DPolygon(i
);
205 if( ORIENTATION_NEGATIVE
== tools::getOrientation(aTmp
) )
208 aTmp
=tools::removeNeutralPoints(aTmp
);
209 std::vector
<B2DPoint
> aTmp2(aTmp
.count());
210 for(sal_uInt32 j
=0; j
<aTmp
.count(); ++j
)
211 aTmp2
[j
] = aTmp
.getB2DPoint(j
);
213 std::vector
<B2DPoint
>::iterator pSmallest
=aTmp2
.end();
214 for(std::vector
<B2DPoint
>::iterator pCurr
=aTmp2
.begin(); pCurr
!=aTmp2
.end(); ++pCurr
)
216 if( pSmallest
== aTmp2
.end() || compare(*pCurr
, *pSmallest
) )
222 if( pSmallest
!= aTmp2
.end() )
223 std::rotate(aTmp2
.begin(),pSmallest
,aTmp2
.end());
226 for(std::vector
<B2DPoint
>::iterator pCurr
=aTmp2
.begin(); pCurr
!=aTmp2
.end(); ++pCurr
)
232 // boxclipper & generic clipper disagree slightly on area-less
233 // polygons (one or two points only)
234 aRes
= tools::stripNeutralPolygons(aRes
);
236 // now, sort all polygons with increasing 0th point
237 std::sort(aRes
.begin(),
242 &B2DPolygon::getB2DPoint
,
245 &B2DPolygon::getB2DPoint
,
251 void verifyPoly(const char* sName
, const char* sSvg
, const B2DPolyRange
& toTest
)
253 B2DPolyPolygon aTmp1
;
254 CPPUNIT_ASSERT_MESSAGE(sName
,
255 tools::importFromSvgD(
257 rtl::OUString::createFromAscii(sSvg
)));
259 const rtl::OUString aSvg
=
260 tools::exportToSvgD(toTest
.solveCrossovers());
261 B2DPolyPolygon aTmp2
;
262 CPPUNIT_ASSERT_MESSAGE(sName
,
263 tools::importFromSvgD(
266 CPPUNIT_ASSERT_MESSAGE(
268 normalizePoly(aTmp2
) == normalizePoly(aTmp1
));
273 const char* disjunct
="m-100-100v200h200v-200zm900 900v200h200v-200z";
274 const char* equal
="m-100-100v200h200v-200zm200 0h-200v200h200v-200z";
275 const char* intersectionN
="m-100-100v100h200v-100zm200 0v-100h-200v100 200h200v-200z";
276 const char* intersectionE
="m0-100v200h100v-200zm0 0h-100v200h100 200v-200z";
277 const char* intersectionS
="m-100 0v100h200v-100zm0-100v200 100h200v-100-200z";
278 const char* intersectionW
="m-100-100v200h100v-200zm0 0h-100v200h100 200v-200z";
279 const char* intersectionNE
="m0-100v100h100v-100zm0-100v100h-100v200h200v-100h100v-200z";
280 const char* intersectionSE
="m0 0v100h100v-100zm100 0v-100h-200v200h100v100h200v-200z";
281 const char* intersectionSW
="m-100 0v100h100v-100zm0-100v100h-100v200h200v-100h100v-200z";
282 const char* intersectionNW
="m-100-100v100h100v-100zm100 0v-100h-200v200h100v100h200v-200z";
283 const char* ringIntersection
="m50-150v100h100v-100zm0 200v100h100v-100zm100-200v-200h-300v300h200v100h-200v300h300v-200h200v-300z";
284 const char* ringIntersection2
="m-150 50v100h100v-100zm0-200v100h100v-100zm100 200v-100h100v100z"
285 "m100-200v100h100v-100zm0 200v100h100v-100zm100-200v-200h-300v200h-200v300h200v200h300v-200h200v-300z";
286 const char* ringIntersectExtraStrip
="m-150 50v100h100v-100zm0-200v100h100v-100zm100 200v-100h100v25h-50v50h50v25z"
287 "m100-200v100h100v-100zm0 200v100h100v-100zm0-75v50h150v-50z"
288 "m100-125v-200h-300v200h-200v300h200v200h300v-200h200v-300z";
289 const char* complexIntersections
="m0 0zm0 0zm0 0zm0 0v-100 100h-100 100v100-100h100zm0 0v-100 100h-100 100v100-100h100z"
290 "m100 0v-100h-100-100v100 100h100 100v-100zm0 0v-100h-100-100v100 100h100 100v-100z"
291 "m0 0v-100h-100v-100 100h-100v100h-100 100v100h100v100-100h100v-100h100z"
292 "m0-100v-100h-100-100v100h-100v100 100h100v100h100 100v-100h100v-100-100z"
293 "m100 0v-100h-200-100-100v100 200 100h100 100 200v-100-200zm600 900v200h200v-200z";
294 const char* randomIntersections
="m20-4515v393h43v-393zm34-8690v127h18v-127zm24 674v427h56v-427zm126-451v16-16z"
295 "m22 3470v260h50v-260zm55 599v167h26v-167zm-49-1831v455h136v-455z"
296 "m10 8845v19h158v-19zm54-38v25h228v-25zm156-13245v108h100v-108z"
297 "m101 14826v200h75v-200zm-205-3000v365h315v-365zm-309-1877v19h628v-19z"
298 "m549-1398v127h98v-127zm18 5351v215h111v-215zm-362-10061v152h488v-152z"
299 "m488 0v-469h-492v621h4v280h488v-432zm-378 5368v48h384v-48zm274-10182v712h119v-712z"
300 "m-424 3173v-94h-47v110h47v96h551v-112zm-105-2249v157h353v112h100v-112h205v-157z"
301 "m284 5177v203h377v-203zm337 4727v66h40v-66zm-326 6110v57h374v-57zm351-12583v39h48v-39z"
302 "m23 12583v-505h-571v576h571v-14h30v-57zm-368-2682v-8h-292v27h134v102h562v-121z"
303 "m-9-12299v320h428v-320zm364 1216v-410h-598v316h-32v110h32v96h47v280h615v-392z"
304 "m-537 11431v486h388v279h111v-279h122v-486zm112-4621v142h550v-142zm101-2719v494h450v-494z"
305 "m340 6609v33h120v-33zm-85-4349v-479h-98v479h-258v459h-165v247h189v307h384v-307h142v-105h13v-601z"
306 "m-270-3159v36h490v-36zm442 2163v7h52v-7zm-345 7158v588h403v-588zm378-1813v-93h-122v126h2v155h148v-188z"
307 "m19-5345v-259h-96v266h44v20h52v-20h10v-7zm-91-6571v-430h-428v430h-211v589h743v-589z"
308 "m101 6571v-461h-705v468h599v20h44v191h65v-218zm-89-8442v40h94v-40zm-71 10742v-43h-221v109h181v427h211v-493z"
309 "m0-4727v-189h-634v392h257v97h33v351h490v-351h29v-300zm-97 6698v-333h-315v333h-262v456h863v-456z"
310 "m-142-8556v22h429v-22zm238-56v17h208v-17zm91 7234v664h120v-664zm69 2452v-336h-567v524h419v13h201v-201z"
311 "m-42-13332v272h115v-272z";
313 verifyPoly("disjunct", disjunct
, aDisjunctRanges
);
314 verifyPoly("equal", equal
, aEqualRanges
);
315 verifyPoly("intersectionN", intersectionN
, aIntersectionN
);
316 verifyPoly("intersectionE", intersectionE
, aIntersectionE
);
317 verifyPoly("intersectionS", intersectionS
, aIntersectionS
);
318 verifyPoly("intersectionW", intersectionW
, aIntersectionW
);
319 verifyPoly("intersectionNE", intersectionNE
, aIntersectionNE
);
320 verifyPoly("intersectionSE", intersectionSE
, aIntersectionSE
);
321 verifyPoly("intersectionSW", intersectionSW
, aIntersectionSW
);
322 verifyPoly("intersectionNW", intersectionNW
, aIntersectionNW
);
323 verifyPoly("ringIntersection", ringIntersection
, aRingIntersection
);
324 verifyPoly("ringIntersection2", ringIntersection2
, aRingIntersection2
);
325 verifyPoly("ringIntersectExtraStrip", ringIntersectExtraStrip
, aRingIntersectExtraStrip
);
326 verifyPoly("complexIntersections", complexIntersections
, aComplexIntersections
);
327 verifyPoly("randomIntersections", randomIntersections
, aRandomIntersections
);
330 void dumpSvg(const char* pName
,
331 const ::basegfx::B2DPolyPolygon
& rPoly
)
333 (void)pName
; (void)rPoly
;
334 #if OSL_DEBUG_LEVEL > 2
335 fprintf(stderr
, "%s - svg:d=\"%s\"\n",
336 pName
, rtl::OUStringToOString(
337 basegfx::tools::exportToSvgD(rPoly
),
338 RTL_TEXTENCODING_UTF8
).getStr() );
342 void getPolyPolygon()
344 dumpSvg("disjunct",aDisjunctRanges
.solveCrossovers());
345 dumpSvg("equal",aEqualRanges
.solveCrossovers());
346 dumpSvg("intersectionN",aIntersectionN
.solveCrossovers());
347 dumpSvg("intersectionE",aIntersectionE
.solveCrossovers());
348 dumpSvg("intersectionS",aIntersectionS
.solveCrossovers());
349 dumpSvg("intersectionW",aIntersectionW
.solveCrossovers());
350 dumpSvg("intersectionNE",aIntersectionNE
.solveCrossovers());
351 dumpSvg("intersectionSE",aIntersectionSE
.solveCrossovers());
352 dumpSvg("intersectionSW",aIntersectionSW
.solveCrossovers());
353 dumpSvg("intersectionNW",aIntersectionNW
.solveCrossovers());
354 dumpSvg("ringIntersection",aRingIntersection
.solveCrossovers());
355 dumpSvg("ringIntersection2",aRingIntersection2
.solveCrossovers());
356 dumpSvg("aRingIntersectExtraStrip",aRingIntersectExtraStrip
.solveCrossovers());
357 dumpSvg("complexIntersections",aComplexIntersections
.solveCrossovers());
358 dumpSvg("randomIntersections",aRandomIntersections
.solveCrossovers());
360 CPPUNIT_ASSERT_MESSAGE("getPolyPolygon", true );
363 void validatePoly( const char* pName
, const B2DPolyRange
& rRange
)
365 B2DPolyPolygon genericClip
;
366 const sal_uInt32 nCount
=rRange
.count();
367 for( sal_uInt32 i
=0; i
<nCount
; ++i
)
369 B2DPolygon aRect
=tools::createPolygonFromRect(
370 rRange
.getElement(i
).head
);
371 if( rRange
.getElement(i
).tail
.head
== ORIENTATION_NEGATIVE
)
374 genericClip
.append(aRect
);
377 #if OSL_DEBUG_LEVEL > 2
378 fprintf(stderr
, "%s input - svg:d=\"%s\"\n",
379 pName
, rtl::OUStringToOString(
380 basegfx::tools::exportToSvgD(
382 RTL_TEXTENCODING_UTF8
).getStr() );
385 const B2DPolyPolygon boxClipResult
=rRange
.solveCrossovers();
386 const rtl::OUString
boxClipSvg(
387 basegfx::tools::exportToSvgD(
390 #if OSL_DEBUG_LEVEL > 2
391 fprintf(stderr
, "%s boxclipper - svg:d=\"%s\"\n",
392 pName
, rtl::OUStringToOString(
394 RTL_TEXTENCODING_UTF8
).getStr() );
397 genericClip
= tools::solveCrossovers(genericClip
);
398 const rtl::OUString
genericClipSvg(
399 basegfx::tools::exportToSvgD(
402 #if OSL_DEBUG_LEVEL > 2
403 fprintf(stderr
, "%s genclipper - svg:d=\"%s\"\n",
404 pName
, rtl::OUStringToOString(
406 RTL_TEXTENCODING_UTF8
).getStr() );
409 CPPUNIT_ASSERT_MESSAGE(pName
,
410 genericClipSvg
== boxClipSvg
);
415 validatePoly("disjunct", aDisjunctRanges
);
416 validatePoly("equal", aEqualRanges
);
417 validatePoly("intersectionN", aIntersectionN
);
418 validatePoly("intersectionE", aIntersectionE
);
419 validatePoly("intersectionS", aIntersectionS
);
420 validatePoly("intersectionW", aIntersectionW
);
421 validatePoly("intersectionNE", aIntersectionNE
);
422 validatePoly("intersectionSE", aIntersectionSE
);
423 validatePoly("intersectionSW", aIntersectionSW
);
424 validatePoly("intersectionNW", aIntersectionNW
);
425 // subtle differences on Solaris Intel, comparison not smart enough
426 // (due to floating point inaccuracies)
427 //validatePoly("ringIntersection", aRingIntersection);
428 //validatePoly("ringIntersection2", aRingIntersection2);
429 //validatePoly("ringIntersectExtraStrip", aRingIntersectExtraStrip);
430 // generic clipper buggy here, likely
431 //validatePoly("complexIntersections", aComplexIntersections);
432 //validatePoly("randomIntersections", aRandomIntersections);
435 // Change the following lines only, if you add, remove or rename
436 // member functions of the current class,
437 // because these macros are need by auto register mechanism.
439 CPPUNIT_TEST_SUITE(boxclipper
);
440 CPPUNIT_TEST(validatePoly
);
441 CPPUNIT_TEST(verifyPoly
);
442 CPPUNIT_TEST(getPolyPolygon
);
443 CPPUNIT_TEST_SUITE_END();
446 // -----------------------------------------------------------------------------
447 CPPUNIT_TEST_SUITE_REGISTRATION(basegfx2d::boxclipper
);
448 } // namespace basegfx2d
450 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */