GCC Code Coverage Report

Line	Branch	Exec	Source
1			/** @file
2			* @brief Conic section clipping with respect to a rectangle
3			*//*
4			* Authors:
5			* Marco Cecchetti <mrcekets at gmail>
6			*
7			* Copyright 2009 authors
8			*
9			* This library is free software; you can redistribute it and/or
10			* modify it either under the terms of the GNU Lesser General Public
11			* License version 2.1 as published by the Free Software Foundation
12			* (the "LGPL") or, at your option, under the terms of the Mozilla
13			* Public License Version 1.1 (the "MPL"). If you do not alter this
14			* notice, a recipient may use your version of this file under either
15			* the MPL or the LGPL.
16			*
17			* You should have received a copy of the LGPL along with this library
18			* in the file COPYING-LGPL-2.1; if not, write to the Free Software
19			* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20			* You should have received a copy of the MPL along with this library
21			* in the file COPYING-MPL-1.1
22			*
23			* The contents of this file are subject to the Mozilla Public License
24			* Version 1.1 (the "License"); you may not use this file except in
25			* compliance with the License. You may obtain a copy of the License at
26			* http://www.mozilla.org/MPL/
27			*
28			* This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
29			* OF ANY KIND, either express or implied. See the LGPL or the MPL for
30			* the specific language governing rights and limitations.
31			*/
32
33			#ifndef LIB2GEOM_SEEN_CONIC_SECTION_CLIPPER_IMPL_H
34			#define LIB2GEOM_SEEN_CONIC_SECTION_CLIPPER_IMPL_H
35
36
37			#include <2geom/conicsec.h>
38			#include <2geom/line.h>
39
40			#include <list>
41			#include <map>
42
43
44
45			#ifdef CLIP_WITH_CAIRO_SUPPORT
46			#include <2geom/toys/path-cairo.h>
47			#define CLIPPER_CLASS clipper_cr
48			#else
49			#define CLIPPER_CLASS clipper
50			#endif
51
52			//#define CLIPDBG
53
54			#ifdef CLIPDBG
55			#include <2geom/toys/path-cairo.h>
56			#define DBGINFO(msg) \
57			std::cerr << msg << std::endl;
58			#define DBGPRINT(msg, var) \
59			std::cerr << msg << var << std::endl;
60			#define DBGPRINTIF(cond, msg, var) \
61			if (cond) \
62			std::cerr << msg << var << std::endl;
63
64			#define DBGPRINT2(msg1, var1, msg2, var2) \
65			std::cerr << msg1 << var1 << msg2 << var2 << std::endl;
66
67			#define DBGPRINTCOLL(msg, coll) \
68			if (coll.size() != 0) \
69			std::cerr << msg << ":\n"; \
70			for (size_t i = 0; i < coll.size(); ++i) \
71			{ \
72			std::cerr << i << ": " << coll[i] << "\n"; \
73			}
74
75			#else
76			#define DBGINFO(msg)
77			#define DBGPRINT(msg, var)
78			#define DBGPRINTIF(cond, msg, var)
79			#define DBGPRINT2(msg1, var1, msg2, var2)
80			#define DBGPRINTCOLL(msg, coll)
81			#endif
82
83
84
85
86			namespace Geom
87			{
88
89			class CLIPPER_CLASS
90			{
91
92			public:
93
94			#ifdef CLIP_WITH_CAIRO_SUPPORT
95			clipper_cr (cairo_t* _cr, const xAx & _cs, const Rect & _R)
96			: cr(_cr), cs(_cs), R(_R)
97			{
98			DBGPRINT ("CLIP: right side: ", R.right())
99			DBGPRINT ("CLIP: top side: ", R.top())
100			DBGPRINT ("CLIP: left side: ", R.left())
101			DBGPRINT ("CLIP: bottom side: ", R.bottom())
102			}
103			#else
104		✗	clipper (const xAx & _cs, const Rect & _R)
105		✗	: cs(_cs), R(_R)
106			{
107		✗	}
108			#endif
109
110			bool clip (std::vector<RatQuad> & arcs);
111
112			bool found_any_isolated_point() const
113			{
114			return ( !single_points.empty() );
115			}
116
117			const std::vector<Point> & isolated_points() const
118			{
119			return single_points;
120			}
121
122
123			private:
124			bool intersect (std::vector<Point> & crossing_points) const;
125
126			bool are_paired (Point & M, const Point & P1, const Point & P2) const;
127			void pairing (std::vector<Point> & paired_points,
128			std::vector<Point> & inner_points,
129			const std::vector<Point> & crossing_points);
130
131			Point find_inner_point_by_bisector_line (const Point & P,
132			const Point & Q) const;
133			Point find_inner_point (const Point & P, const Point & Q) const;
134
135			std::list<Point>::iterator split (std::list<Point> & points,
136			std::list<Point>::iterator sp,
137			std::list<Point>::iterator fp) const;
138			void rsplit (std::list<Point> & points,
139			std::list<Point>::iterator sp,
140			std::list<Point>::iterator fp,
141			size_t k) const;
142
143			void rsplit (std::list<Point> & points,
144			std::list<Point>::iterator sp,
145			std::list<Point>::iterator fp,
146			double length) const;
147
148			private:
149			#ifdef CLIP_WITH_CAIRO_SUPPORT
150			cairo_t* cr;
151			#endif
152			const xAx & cs;
153			const Rect & R;
154			std::vector<Point> single_points;
155			};
156
157
158
159
160			/*
161			* Given two point "P", "Q" on the conic section the method computes
162			* a third point inner to the arc with end-point "P", "Q".
163			* The new point is found by intersecting the conic with the bisector line
164			* of the PQ line segment.
165			*/
166			inline
167		✗	Point CLIPPER_CLASS::find_inner_point_by_bisector_line (const Point & P,
168			const Point & Q) const
169			{
170			DBGPRINT ("CLIP: find_inner_point_by_bisector_line: P = ", P)
171			DBGPRINT ("CLIP: find_inner_point_by_bisector_line: Q = ", Q)
172		✗	Line bl = make_bisector_line (LineSegment (P, Q));
173		✗	std::vector<double> rts = cs.roots (bl);
174			//DBGPRINT ("CLIP: find_inner_point: rts.size = ", rts.size())
175			double t;
176		✗	if (rts.size() == 0)
177			{
178		✗	THROW_LOGICALERROR ("clipper::find_inner_point_by_bisector_line: "
179			"no conic-bisector line intersection point");
180			}
181		✗	if (rts.size() == 2)
182			{
183			// we suppose that the searched point is the nearest
184			// to the line segment PQ
185		✗	t = (std::fabs(rts[0]) < std::fabs(rts[1])) ? rts[0] : rts[1];
186			}
187			else
188			{
189		✗	t = rts[0];
190			}
191		✗	return bl.pointAt (t);
192		✗	}
193
194
195			/*
196			* Given two point "P", "Q" on the conic section the method computes
197			* a third point inner to the arc with end-point "P", "Q".
198			* The new point is found by intersecting the conic with the line
199			* passing through the middle point of the PQ line segment and
200			* the intersection point of the tangent lines at points P and Q.
201			*/
202			inline
203		✗	Point CLIPPER_CLASS::find_inner_point (const Point & P, const Point & Q) const
204			{
205
206		✗	Line l1 = cs.tangent (P);
207		✗	Line l2 = cs.tangent (Q);
208		✗	Line l;
209			// in case we fail to find a crossing point we fall back to the bisector
210			// method
211			try
212			{
213		✗	OptCrossing oc = intersection(l1, l2);
214		✗	if (!oc)
215			{
216		✗	return find_inner_point_by_bisector_line (P, Q);
217			}
218		✗	l.setPoints (l1.pointAt (oc->ta), middle_point (P, Q));
219			}
220		✗	catch (Geom::InfiniteSolutions const &e)
221			{
222		✗	return find_inner_point_by_bisector_line (P, Q);
223		✗	}
224
225		✗	std::vector<double> rts = cs.roots (l);
226			double t;
227		✗	if (rts.size() == 0)
228			{
229		✗	return find_inner_point_by_bisector_line (P, Q);
230			}
231			// the line "l" origin is set to the tangent crossing point so in case
232			// we find two intersection points only the nearest belongs to the given arc
233			// pay attention: in case we are dealing with an hyperbola (remember that
234			// end points are on the same branch, because they are paired) the tangent
235			// crossing point belongs to the angle delimited by hyperbola asymptotes
236			// and containing the given hyperbola branch, so the previous statement is
237			// still true
238		✗	if (rts.size() == 2)
239			{
240		✗	t = (std::fabs(rts[0]) < std::fabs(rts[1])) ? rts[0] : rts[1];
241			}
242			else
243			{
244		✗	t = rts[0];
245			}
246		✗	return l.pointAt (t);
247		✗	}
248
249
250			/*
251			* Given a list of points on the conic section, and given two consecutive
252			* points belonging to the list and passed by two list iterators, the method
253			* finds a new point that is inner to the conic arc which has the two passed
254			* points as initial and final point. This new point is inserted into the list
255			* between the two passed points and an iterator pointing to the new point
256			* is returned.
257			*/
258			inline
259		✗	std::list<Point>::iterator CLIPPER_CLASS::split (std::list<Point> & points,
260			std::list<Point>::iterator sp,
261			std::list<Point>::iterator fp) const
262			{
263		✗	Point new_point = find_inner_point (*sp, *fp);
264		✗	std::list<Point>::iterator ip = points.insert (fp, new_point);
265			//std::cerr << "CLIP: split: [" << *sp << ", " << *ip << ", "
266			// << *fp << "]" << std::endl;
267		✗	return ip;
268			}
269
270
271			/*
272			* Given a list of points on the conic section, and given two consecutive
273			* points belonging to the list and passed by two list iterators, the method
274			* recursively finds new points that are inner to the conic arc which has
275			* the two passed points as initial and final point. The recursion stop after
276			* "k" recursive calls. These new points are inserted into the list between
277			* the two passed points, and in the order we cross them going from
278			* the initial to the final arc point.
279			*/
280			inline
281		✗	void CLIPPER_CLASS::rsplit (std::list<Point> & points,
282			std::list<Point>::iterator sp,
283			std::list<Point>::iterator fp,
284			size_t k) const
285			{
286		✗	if (k == 0)
287			{
288			//DBGINFO("CLIP: split: no further split")
289		✗	return;
290			}
291
292		✗	std::list<Point>::iterator ip = split (points, sp, fp);
293		✗	--k;
294		✗	rsplit (points, sp, ip, k);
295		✗	rsplit (points, ip, fp, k);
296			}
297
298
299			/*
300			* Given a list of points on the conic section, and given two consecutive
301			* points belonging to the list and passed by two list iterators, the method
302			* recursively finds new points that are inner to the conic arc which has
303			* the two passed points as initial and final point. The recursion stop when
304			* the max distance between the new computed inner point and the two passed
305			* arc end-points is less then the value specified by the "length" parameter.
306			* These new points are inserted into the list between the two passed points,
307			* and in the order we cross them going from the initial to the final arc point.
308			*/
309			inline
310		✗	void CLIPPER_CLASS::rsplit (std::list<Point> & points,
311			std::list<Point>::iterator sp,
312			std::list<Point>::iterator fp,
313			double length) const
314			{
315		✗	std::list<Point>::iterator ip = split (points, sp, fp);
316		✗	double d1 = distance (*sp, *ip);
317		✗	double d2 = distance (*ip, *fp);
318		✗	double mdist = std::max (d1, d2);
319
320		✗	if (mdist < length)
321			{
322			//DBGINFO("CLIP: split: no further split")
323		✗	return;
324			}
325
326			// they have to be called both to keep the number of points in the list
327			// in the form 2k+1 where k are the sub-arcs the initial arc is split in.
328		✗	rsplit (points, sp, ip, length);
329		✗	rsplit (points, ip, fp, length);
330			}
331
332
333			} // end namespace Geom
334
335			#endif // LIB2GEOM_SEEN_CONIC_SECTION_CLIPPER_IMPL_H
336
337			/*
338			Local Variables:
339			mode:c++
340			c-file-style:"stroustrup"
341			c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
342			indent-tabs-mode:nil
343			fill-column:99
344			End:
345			*/
346			// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :
347