GCC Code Coverage Report

Line	Branch	Exec	Source
1			/* Conic section clipping with respect to a rectangle
2			*
3			* Authors:
4			* Marco Cecchetti <mrcekets at gmail>
5			*
6			* Copyright 2009 authors
7			*
8			* This library is free software; you can redistribute it and/or
9			* modify it either under the terms of the GNU Lesser General Public
10			* License version 2.1 as published by the Free Software Foundation
11			* (the "LGPL") or, at your option, under the terms of the Mozilla
12			* Public License Version 1.1 (the "MPL"). If you do not alter this
13			* notice, a recipient may use your version of this file under either
14			* the MPL or the LGPL.
15			*
16			* You should have received a copy of the LGPL along with this library
17			* in the file COPYING-LGPL-2.1; if not, write to the Free Software
18			* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
19			* You should have received a copy of the MPL along with this library
20			* in the file COPYING-MPL-1.1
21			*
22			* The contents of this file are subject to the Mozilla Public License
23			* Version 1.1 (the "License"); you may not use this file except in
24			* compliance with the License. You may obtain a copy of the License at
25			* http://www.mozilla.org/MPL/
26			*
27			* This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
28			* OF ANY KIND, either express or implied. See the LGPL or the MPL for
29			* the specific language governing rights and limitations.
30			*/
31
32			#include <optional>
33
34			#ifndef CLIP_WITH_CAIRO_SUPPORT
35			#include <2geom/conic_section_clipper.h>
36			#endif
37
38			namespace Geom
39			{
40
41			/*
42			* Find rectangle-conic crossing points. They are returned in the
43			* "crossing_points" parameter.
44			* The method returns true if the conic section intersects at least one
45			* of the four lines passing through rectangle edges, else it returns false.
46			*/
47		✗	bool CLIPPER_CLASS::intersect (std::vector<Point> & crossing_points) const
48			{
49		✗	crossing_points.clear();
50
51		✗	std::vector<double> rts;
52		✗	std::vector<Point> cpts;
53			// rectangle corners
54			enum {TOP_LEFT, TOP_RIGHT, BOTTOM_RIGHT, BOTTOM_LEFT};
55
56		✗	bool no_crossing = true;
57
58			// right edge
59		✗	cs.roots (rts, R.right(), X);
60		✗	if (!rts.empty())
61			{
62		✗	no_crossing = false;
63			DBGPRINT ("CLIP: right: rts[0] = ", rts[0])
64			DBGPRINTIF ((rts.size() == 2), "CLIP: right: rts[1] = ", rts[1])
65
66		✗	Point corner1 = R.corner(TOP_RIGHT);
67		✗	Point corner2 = R.corner(BOTTOM_RIGHT);
68
69		✗	for (double rt : rts)
70			{
71		✗	if (rt < R.top() || rt > R.bottom()) continue;
72		✗	Point P (R.right(), rt);
73		✗	if (are_near (P, corner1))
74		✗	P = corner1;
75		✗	else if (are_near (P, corner2))
76		✗	P = corner2;
77
78		✗	cpts.push_back (P);
79			}
80		✗	if (cpts.size() == 2 && are_near (cpts[0], cpts[1]))
81			{
82		✗	cpts[0] = middle_point (cpts[0], cpts[1]);
83		✗	cpts.pop_back();
84			}
85			}
86
87			// top edge
88		✗	cs.roots (rts, R.top(), Y);
89		✗	if (!rts.empty())
90			{
91		✗	no_crossing = false;
92			DBGPRINT ("CLIP: top: rts[0] = ", rts[0])
93			DBGPRINTIF ((rts.size() == 2), "CLIP: top: rts[1] = ", rts[1])
94
95		✗	Point corner1 = R.corner(TOP_RIGHT);
96		✗	Point corner2 = R.corner(TOP_LEFT);
97
98		✗	for (double rt : rts)
99			{
100		✗	if (rt < R.left() || rt > R.right()) continue;
101		✗	Point P (rt, R.top());
102		✗	if (are_near (P, corner1))
103		✗	P = corner1;
104		✗	else if (are_near (P, corner2))
105		✗	P = corner2;
106
107		✗	cpts.push_back (P);
108			}
109		✗	if (cpts.size() == 2 && are_near (cpts[0], cpts[1]))
110			{
111		✗	cpts[0] = middle_point (cpts[0], cpts[1]);
112		✗	cpts.pop_back();
113			}
114			}
115
116			// left edge
117		✗	cs.roots (rts, R.left(), X);
118		✗	if (!rts.empty())
119			{
120		✗	no_crossing = false;
121			DBGPRINT ("CLIP: left: rts[0] = ", rts[0])
122			DBGPRINTIF ((rts.size() == 2), "CLIP: left: rts[1] = ", rts[1])
123
124		✗	Point corner1 = R.corner(TOP_LEFT);
125		✗	Point corner2 = R.corner(BOTTOM_LEFT);
126
127		✗	for (double rt : rts)
128			{
129		✗	if (rt < R.top() || rt > R.bottom()) continue;
130		✗	Point P (R.left(), rt);
131		✗	if (are_near (P, corner1))
132		✗	P = corner1;
133		✗	else if (are_near (P, corner2))
134		✗	P = corner2;
135
136		✗	cpts.push_back (P);
137			}
138		✗	if (cpts.size() == 2 && are_near (cpts[0], cpts[1]))
139			{
140		✗	cpts[0] = middle_point (cpts[0], cpts[1]);
141		✗	cpts.pop_back();
142			}
143			}
144
145			// bottom edge
146		✗	cs.roots (rts, R.bottom(), Y);
147		✗	if (!rts.empty())
148			{
149		✗	no_crossing = false;
150			DBGPRINT ("CLIP: bottom: rts[0] = ", rts[0])
151			DBGPRINTIF ((rts.size() == 2), "CLIP: bottom: rts[1] = ", rts[1])
152
153		✗	Point corner1 = R.corner(BOTTOM_RIGHT);
154		✗	Point corner2 = R.corner(BOTTOM_LEFT);
155
156		✗	for (double rt : rts)
157			{
158		✗	if (rt < R.left() || rt > R.right()) continue;
159		✗	Point P (rt, R.bottom());
160		✗	if (are_near (P, corner1))
161		✗	P = corner1;
162		✗	else if (are_near (P, corner2))
163		✗	P = corner2;
164
165		✗	cpts.push_back (P);
166			}
167		✗	if (cpts.size() == 2 && are_near (cpts[0], cpts[1]))
168			{
169		✗	cpts[0] = middle_point (cpts[0], cpts[1]);
170		✗	cpts.pop_back();
171			}
172			}
173
174			DBGPRINT ("CLIP: intersect: crossing_points.size (with duplicates) = ",
175			cpts.size())
176
177			// remove duplicates
178		✗	std::sort (cpts.begin(), cpts.end(), Point::LexLess<X>());
179		✗	cpts.erase (std::unique (cpts.begin(), cpts.end()), cpts.end());
180
181
182			// Order crossing points on the rectangle edge clockwise, so two consecutive
183			// crossing points would be the end points of a conic arc all inside or all
184			// outside the rectangle.
185		✗	std::map<double, size_t> cp_angles;
186		✗	for (size_t i = 0; i < cpts.size(); ++i)
187			{
188		✗	cp_angles.insert (std::make_pair (cs.angle_at (cpts[i]), i));
189			}
190
191		✗	std::map<double, size_t>::const_iterator pos;
192		✗	for (pos = cp_angles.begin(); pos != cp_angles.end(); ++pos)
193			{
194		✗	crossing_points.push_back (cpts[pos->second]);
195			}
196
197			DBGPRINT ("CLIP: intersect: crossing_points.size = ", crossing_points.size())
198			DBGPRINTCOLL ("CLIP: intersect: crossing_points:", crossing_points)
199
200		✗	return no_crossing;
201		✗	} // end function intersect
202
203
204
205			inline
206		✗	double signed_triangle_area (Point const& p1, Point const& p2, Point const& p3)
207			{
208		✗	return (cross(p2, p3) - cross(p1, p3) + cross(p1, p2));
209			}
210
211
212			/*
213			* Test if two crossing points are the end points of a conic arc inner to the
214			* rectangle. In such a case the method returns true, else it returns false.
215			* Moreover by the parameter "M" it returns a point inner to the conic arc
216			* with the given end-points.
217			*
218			*/
219		✗	bool CLIPPER_CLASS::are_paired (Point& M, const Point & P1, const Point & P2) const
220			{
221			using std::swap;
222
223			/*
224			* we looks for the points on the conic whose tangent is parallel to the
225			* arc chord P1P2, they will be extrema of the conic arc P1P2 wrt the
226			* direction orthogonal to the chord
227			*/
228		✗	Point dir = P2 - P1;
229			DBGPRINT ("CLIP: are_paired: first point: ", P1)
230			DBGPRINT ("CLIP: are_paired: second point: ", P2)
231
232		✗	double grad0 = 2 * cs.coeff(0) * dir[0] + cs.coeff(1) * dir[1];
233		✗	double grad1 = cs.coeff(1) * dir[0] + 2 * cs.coeff(2) * dir[1];
234		✗	double grad2 = cs.coeff(3) * dir[0] + cs.coeff(4) * dir[1];
235
236
237			/*
238			* such points are found intersecating the conic section with the line
239			* orthogonal to "grad": the derivative wrt the "dir" direction
240			*/
241		✗	Line gl (grad0, grad1, grad2);
242		✗	std::vector<double> rts;
243		✗	rts = cs.roots (gl);
244			DBGPRINT ("CLIP: are_paired: extrema: rts.size() = ", rts.size())
245
246
247
248		✗	std::vector<Point> extrema;
249		✗	for (double rt : rts)
250			{
251		✗	extrema.push_back (gl.pointAt (rt));
252			}
253
254		✗	if (extrema.size() == 2)
255			{
256			// in case we are dealing with an hyperbola we could have two extrema
257			// on the same side wrt the line passing through P1 and P2, but
258			// only the nearer extremum is on the arc P1P2
259		✗	double side0 = signed_triangle_area (P1, extrema[0], P2);
260		✗	double side1 = signed_triangle_area (P1, extrema[1], P2);
261
262		✗	if (sgn(side0) == sgn(side1))
263			{
264		✗	if (std::fabs(side0) > std::fabs(side1)) {
265		✗	swap(extrema[0], extrema[1]);
266			}
267		✗	extrema.pop_back();
268			}
269			}
270
271		✗	std::vector<Point> inner_points;
272		✗	for (auto & i : extrema)
273			{
274		✗	if (!R.contains (i)) continue;
275			// in case we are dealing with an ellipse tangent to two orthogonal
276			// rectangle edges we could have two extrema on opposite sides wrt the
277			// line passing through P1P2 and both inner the rectangle; anyway, since
278			// we order the crossing points clockwise we have only one extremum
279			// that follows such an ordering wrt P1 and P2;
280			// remark: the other arc will be selected when we test for the arc P2P1.
281		✗	double P1angle = cs.angle_at (P1);
282		✗	double P2angle = cs.angle_at (P2);
283		✗	double Qangle = cs.angle_at (i);
284		✗	if (P1angle < P2angle && !(P1angle <= Qangle && Qangle <= P2angle))
285		✗	continue;
286		✗	if (P1angle > P2angle && !(P1angle <= Qangle || Qangle <= P2angle))
287		✗	continue;
288
289		✗	inner_points.push_back (i);
290			}
291
292		✗	if (inner_points.size() > 1)
293			{
294		✗	THROW_LOGICALERROR ("conic section clipper: "
295			"more than one extremum found");
296			}
297		✗	else if (inner_points.size() == 1)
298			{
299		✗	M = inner_points.front();
300		✗	return true;
301			}
302
303		✗	return false;
304		✗	}
305
306
307			/*
308			* Pair the points contained in the "crossing_points" vector; the paired points
309			* are put in the paired_points vector so that given a point with an even index
310			* and the next one they are the end points of a conic arc that is inner to the
311			* rectangle. In the "inner_points" are returned points that are inner to the
312			* arc, where the inner point with index k is related to the arc with end
313			* points with indexes 2k, 2k+1. In case there are unpaired points the are put
314			* in to the "single_points" vector.
315			*/
316		✗	void CLIPPER_CLASS::pairing (std::vector<Point> & paired_points,
317			std::vector<Point> & inner_points,
318			const std::vector<Point> & crossing_points)
319			{
320		✗	paired_points.clear();
321		✗	paired_points.reserve (crossing_points.size());
322
323		✗	inner_points.clear();
324		✗	inner_points.reserve (crossing_points.size() / 2);
325
326		✗	single_points.clear();
327
328			// to keep trace of which crossing points have been paired
329		✗	std::vector<bool> paired (crossing_points.size(), false);
330
331		✗	Point M;
332
333			// by the way we have ordered crossing points we need to test one point wrt
334			// the next point only, for pairing; moreover the last point need to be
335			// tested wrt the first point; pay attention: one point can be paired both
336			// with the previous and the next one: this is not an error, think of
337			// crossing points that are tangent to the rectangle edge (and inner);
338		✗	for (size_t i = 0; i < crossing_points.size(); ++i)
339			{
340			// we need to test the last point wrt the first one
341		✗	size_t j = (i == 0) ? (crossing_points.size() - 1) : (i-1);
342		✗	if (are_paired (M, crossing_points[j], crossing_points[i]))
343			{
344			#ifdef CLIP_WITH_CAIRO_SUPPORT
345			cairo_set_source_rgba(cr, 0.1, 0.1, 0.8, 1.0);
346			draw_line_seg (cr, crossing_points[j], crossing_points[i]);
347			draw_handle (cr, crossing_points[j]);
348			draw_handle (cr, crossing_points[i]);
349			draw_handle (cr, M);
350			cairo_stroke (cr);
351			#endif
352		✗	paired[j] = paired[i] = true;
353		✗	paired_points.push_back (crossing_points[j]);
354		✗	paired_points.push_back (crossing_points[i]);
355		✗	inner_points.push_back (M);
356			}
357			}
358
359			// some point are not paired with any point, e.g. a crossing point tangent
360			// to a rectangle edge but with the conic arc outside the rectangle
361		✗	for (size_t i = 0; i < paired.size(); ++i)
362			{
363		✗	if (!paired[i])
364		✗	single_points.push_back (crossing_points[i]);
365			}
366			DBGPRINTCOLL ("single_points", single_points)
367
368		✗	}
369
370
371			/*
372			* This method clip the section conic wrt the rectangle and returns the inner
373			* conic arcs as a vector of RatQuad objects by the "arcs" parameter.
374			*/
375		✗	bool CLIPPER_CLASS::clip (std::vector<RatQuad> & arcs)
376			{
377			using std::swap;
378
379		✗	arcs.clear();
380		✗	std::vector<Point> crossing_points;
381		✗	std::vector<Point> paired_points;
382		✗	std::vector<Point> inner_points;
383
384		✗	Line l1, l2;
385		✗	if (cs.decompose (l1, l2))
386			{
387		✗	bool inner_empty = true;
388
389			DBGINFO ("CLIP: degenerate section conic")
390
391		✗	std::optional<LineSegment> ls1 = Geom::clip (l1, R);
392		✗	if (ls1)
393			{
394		✗	if (ls1->isDegenerate())
395			{
396		✗	single_points.push_back (ls1->initialPoint());
397			}
398			else
399			{
400		✗	Point M = middle_point (*ls1);
401		✗	arcs.emplace_back(ls1->initialPoint(), M, ls1->finalPoint(), 1);
402		✗	inner_empty = false;
403			}
404			}
405
406		✗	std::optional<LineSegment> ls2 = Geom::clip (l2, R);
407		✗	if (ls2)
408			{
409		✗	if (ls2->isDegenerate())
410			{
411		✗	single_points.push_back (ls2->initialPoint());
412			}
413			else
414			{
415		✗	Point M = middle_point (*ls2);
416		✗	arcs.emplace_back(ls2->initialPoint(), M, ls2->finalPoint(), 1);
417		✗	inner_empty = false;
418			}
419			}
420
421		✗	return !inner_empty;
422		✗	}
423
424
425		✗	bool no_crossing = intersect (crossing_points);
426
427			// if the only crossing point is a rectangle corner than the section conic
428			// is all outside the rectangle
429		✗	if (crossing_points.size() == 1)
430			{
431		✗	for (size_t i = 0; i < 4; ++i)
432			{
433		✗	if (crossing_points[0] == R.corner(i))
434			{
435		✗	single_points.push_back (R.corner(i));
436		✗	return false;
437			}
438			}
439			}
440
441			// if the conic does not cross any line passing through a rectangle edge or
442			// it is tangent to only one edge then it is an ellipse
443		✗	if (no_crossing
444		✗	|| (crossing_points.size() == 1 && single_points.empty()))
445			{
446			// if the ellipse centre is inside the rectangle
447			// then so it is the ellipse
448		✗	std::optional<Point> c = cs.centre();
449		✗	if (c && R.contains (*c))
450			{
451			DBGPRINT ("CLIP: ellipse with centre", *c)
452			// we set paired and inner points by finding the ellipse
453			// intersection with its axes; this choice let us having a more
454			// accurate RatQuad parametric arc
455		✗	paired_points.resize(4);
456		✗	std::vector<double> rts;
457		✗	double angle = cs.axis_angle();
458		✗	Line axis1 (*c, angle);
459		✗	rts = cs.roots (axis1);
460		✗	if (rts[0] > rts[1]) swap (rts[0], rts[1]);
461		✗	paired_points[0] = axis1.pointAt (rts[0]);
462		✗	paired_points[1] = axis1.pointAt (rts[1]);
463		✗	paired_points[2] = paired_points[1];
464		✗	paired_points[3] = paired_points[0];
465		✗	Line axis2 (*c, angle + M_PI/2);
466		✗	rts = cs.roots (axis2);
467		✗	if (rts[0] > rts[1]) swap (rts[0], rts[1]);
468		✗	inner_points.push_back (axis2.pointAt (rts[0]));
469		✗	inner_points.push_back (axis2.pointAt (rts[1]));
470		✗	}
471		✗	else if (crossing_points.size() == 1)
472			{
473			// so we have a tangent crossing point but the ellipse is outside
474			// the rectangle
475		✗	single_points.push_back (crossing_points[0]);
476			}
477			}
478			else
479			{
480			// in case the conic section intersects any of the four lines passing
481			// through the rectangle edges but it does not cross any rectangle edge
482			// then the conic is all outer of the rectangle
483		✗	if (crossing_points.empty()) return false;
484			// else we need to pair crossing points, and to find an arc inner point
485			// in order to generate a RatQuad object
486		✗	pairing (paired_points, inner_points, crossing_points);
487			}
488
489
490			// we split arcs until the end-point distance is less than a given value,
491			// in this way the RatQuad parametrization is enough accurate
492		✗	std::list<Point> points;
493		✗	std::list<Point>::iterator sp, ip, fp;
494		✗	for (size_t i = 0, j = 0; i < paired_points.size(); i += 2, ++j)
495			{
496			//DBGPRINT ("CLIP: clip: P = ", paired_points[i])
497			//DBGPRINT ("CLIP: clip: M = ", inner_points[j])
498			//DBGPRINT ("CLIP: clip: Q = ", paired_points[i+1])
499
500			// in case inner point and end points are near is better not split
501			// the conic arc further or we could get a degenerate RatQuad object
502		✗	if (are_near (paired_points[i], inner_points[j], 1e-4)
503		✗	&& are_near (paired_points[i+1], inner_points[j], 1e-4))
504			{
505		✗	arcs.push_back (cs.toRatQuad (paired_points[i],
506		✗	inner_points[j],
507		✗	paired_points[i+1]));
508		✗	continue;
509			}
510
511			// populate the list
512		✗	points.push_back(paired_points[i]);
513		✗	points.push_back(inner_points[j]);
514		✗	points.push_back(paired_points[i+1]);
515
516			// an initial unconditioned splitting
517		✗	sp = points.begin();
518		✗	ip = sp; ++ip;
519		✗	fp = ip; ++fp;
520		✗	rsplit (points, sp, ip, size_t(1u));
521		✗	rsplit (points, ip, fp, size_t(1u));
522
523			// length conditioned split
524		✗	sp = points.begin();
525		✗	fp = sp; ++fp;
526		✗	while (fp != points.end())
527			{
528		✗	rsplit (points, sp, fp, 100.0);
529		✗	sp = fp;
530		✗	++fp;
531			}
532
533		✗	sp = points.begin();
534		✗	ip = sp; ++ip;
535		✗	fp = ip; ++fp;
536			//DBGPRINT ("CLIP: points ", j)
537			//DBGPRINT ("CLIP: points.size = ", points.size())
538		✗	while (ip != points.end())
539			{
540			#ifdef CLIP_WITH_CAIRO_SUPPORT
541			cairo_set_source_rgba(cr, 0.1, 0.1, 0.8, 1.0);
542			draw_handle (cr, *sp);
543			draw_handle (cr, *ip);
544			cairo_stroke (cr);
545			#endif
546			//std::cerr << "CLIP: arc: [" << *sp << ", " << *ip << ", "
547			// << *fp << "]" << std::endl;
548		✗	arcs.push_back (cs.toRatQuad (*sp, *ip, *fp));
549		✗	sp = fp;
550		✗	ip = sp; ++ip;
551		✗	fp = ip; ++fp;
552			}
553		✗	points.clear();
554			}
555			DBGPRINT ("CLIP: arcs.size() = ", arcs.size())
556		✗	return (arcs.size() != 0);
557		✗	} // end method clip
558
559
560			} // end namespace geom
561
562
563
564
565			/*
566			Local Variables:
567			mode:c++
568			c-file-style:"stroustrup"
569			c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
570			indent-tabs-mode:nil
571			fill-column:99
572			End:
573			*/
574			// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :
575