GCC Code Coverage Report

Line	Branch	Exec	Source
1			/**
2			* \brief Various geometrical calculations.
3			*/
4
5			#include <2geom/geom.h>
6			#include <2geom/point.h>
7			#include <algorithm>
8			#include <optional>
9			#include <2geom/rect.h>
10
11			using std::swap;
12
13			namespace Geom {
14
15			enum IntersectorKind {
16			intersects = 0,
17			parallel,
18			coincident,
19			no_intersection
20			};
21
22			/**
23			* Finds the intersection of the two (infinite) lines
24			* defined by the points p such that dot(n0, p) == d0 and dot(n1, p) == d1.
25			*
26			* If the two lines intersect, then \a result becomes their point of
27			* intersection; otherwise, \a result remains unchanged.
28			*
29			* This function finds the intersection of the two lines (infinite)
30			* defined by n0.X = d0 and x1.X = d1. The algorithm is as follows:
31			* To compute the intersection point use kramer's rule:
32			* \verbatim
33			* convert lines to form
34			* ax + by = c
35			* dx + ey = f
36			*
37			* (
38			* e.g. a = (x2 - x1), b = (y2 - y1), c = (x2 - x1)*x1 + (y2 - y1)*y1
39			* )
40			*
41			* In our case we use:
42			* a = n0.x d = n1.x
43			* b = n0.y e = n1.y
44			* c = d0 f = d1
45			*
46			* so:
47			*
48			* adx + bdy = cd
49			* adx + aey = af
50			*
51			* bdy - aey = cd - af
52			* (bd - ae)y = cd - af
53			*
54			* y = (cd - af)/(bd - ae)
55			*
56			* repeat for x and you get:
57			*
58			* x = (fb - ce)/(bd - ae) \endverbatim
59			*
60			* If the denominator (bd-ae) is 0 then the lines are parallel, if the
61			* numerators are 0 then the lines coincide.
62			*
63			* \todo Why not use existing but outcommented code below
64			* (HAVE_NEW_INTERSECTOR_CODE)?
65			*/
66			IntersectorKind
67		✗	line_intersection(Geom::Point const &n0, double const d0,
68			Geom::Point const &n1, double const d1,
69			Geom::Point &result)
70			{
71		✗	double denominator = dot(Geom::rot90(n0), n1);
72		✗	double X = n1[Geom::Y] * d0 -
73		✗	n0[Geom::Y] * d1;
74			/* X = (-d1, d0) dot (n0[Y], n1[Y]) */
75
76		✗	if (denominator == 0) {
77		✗	if ( X == 0 ) {
78		✗	return coincident;
79			} else {
80		✗	return parallel;
81			}
82			}
83
84		✗	double Y = n0[Geom::X] * d1 -
85		✗	n1[Geom::X] * d0;
86
87		✗	result = Geom::Point(X, Y) / denominator;
88
89		✗	return intersects;
90			}
91
92
93
94			/* ccw exists as a building block */
95			int
96		✗	intersector_ccw(const Geom::Point& p0, const Geom::Point& p1,
97			const Geom::Point& p2)
98			/* Determine which way a set of three points winds. */
99			{
100		✗	Geom::Point d1 = p1 - p0;
101		✗	Geom::Point d2 = p2 - p0;
102			/* compare slopes but avoid division operation */
103		✗	double c = dot(Geom::rot90(d1), d2);
104		✗	if(c > 0)
105		✗	return +1; // ccw - do these match def'n in header?
106		✗	if(c < 0)
107		✗	return -1; // cw
108
109			/* Colinear [or NaN]. Decide the order. */
110		✗	if ( ( d1[0] * d2[0] < 0 ) ||
111		✗	( d1[1] * d2[1] < 0 ) ) {
112		✗	return -1; // p2 < p0 < p1
113		✗	} else if ( dot(d1,d1) < dot(d2,d2) ) {
114		✗	return +1; // p0 <= p1 < p2
115			} else {
116		✗	return 0; // p0 <= p2 <= p1
117			}
118			}
119
120			/** Determine whether the line segment from p00 to p01 intersects the
121			infinite line passing through p10 and p11. This doesn't find the
122			point of intersection, use the line_intersect function above,
123			or the segment_intersection interface below.
124
125			\pre neither segment is zero-length; i.e. p00 != p01 and p10 != p11.
126			*/
127			bool
128		✗	line_segment_intersectp(Geom::Point const &p00, Geom::Point const &p01,
129			Geom::Point const &p10, Geom::Point const &p11)
130			{
131		✗	if(p00 == p01) return false;
132		✗	if(p10 == p11) return false;
133
134		✗	return ((intersector_ccw(p00, p01, p10) * intersector_ccw(p00, p01, p11)) <= 0 );
135			}
136
137
138			/** Determine whether two line segments intersect. This doesn't find
139			the point of intersection, use the line_intersect function above,
140			or the segment_intersection interface below.
141
142			\pre neither segment is zero-length; i.e. p00 != p01 and p10 != p11.
143			*/
144			bool
145		✗	segment_intersectp(Geom::Point const &p00, Geom::Point const &p01,
146			Geom::Point const &p10, Geom::Point const &p11)
147			{
148		✗	if(p00 == p01) return false;
149		✗	if(p10 == p11) return false;
150
151			/* true iff ( (the p1 segment straddles the p0 infinite line)
152			* and (the p0 segment straddles the p1 infinite line) ). */
153		✗	return (line_segment_intersectp(p00, p01, p10, p11) &&
154		✗	line_segment_intersectp(p10, p11, p00, p01));
155			}
156
157			/** Determine whether \& where a line segments intersects an (infinite) line.
158
159			If there is no intersection, then \a result remains unchanged.
160
161			\pre neither segment is zero-length; i.e. p00 != p01 and p10 != p11.
162			**/
163			IntersectorKind
164		✗	line_segment_intersect(Geom::Point const &p00, Geom::Point const &p01,
165			Geom::Point const &p10, Geom::Point const &p11,
166			Geom::Point &result)
167			{
168		✗	if(line_segment_intersectp(p00, p01, p10, p11)) {
169		✗	Geom::Point n0 = (p01 - p00).ccw();
170		✗	double d0 = dot(n0,p00);
171
172		✗	Geom::Point n1 = (p11 - p10).ccw();
173		✗	double d1 = dot(n1,p10);
174		✗	return line_intersection(n0, d0, n1, d1, result);
175			} else {
176		✗	return no_intersection;
177			}
178			}
179
180
181			/** Determine whether \& where two line segments intersect.
182
183			If the two segments don't intersect, then \a result remains unchanged.
184
185			\pre neither segment is zero-length; i.e. p00 != p01 and p10 != p11.
186			**/
187			IntersectorKind
188		✗	segment_intersect(Geom::Point const &p00, Geom::Point const &p01,
189			Geom::Point const &p10, Geom::Point const &p11,
190			Geom::Point &result)
191			{
192		✗	if(segment_intersectp(p00, p01, p10, p11)) {
193		✗	Geom::Point n0 = (p01 - p00).ccw();
194		✗	double d0 = dot(n0,p00);
195
196		✗	Geom::Point n1 = (p11 - p10).ccw();
197		✗	double d1 = dot(n1,p10);
198		✗	return line_intersection(n0, d0, n1, d1, result);
199			} else {
200		✗	return no_intersection;
201			}
202			}
203
204			/** Determine whether \& where two line segments intersect.
205
206			If the two segments don't intersect, then \a result remains unchanged.
207
208			\pre neither segment is zero-length; i.e. p00 != p01 and p10 != p11.
209			**/
210			IntersectorKind
211		✗	line_twopoint_intersect(Geom::Point const &p00, Geom::Point const &p01,
212			Geom::Point const &p10, Geom::Point const &p11,
213			Geom::Point &result)
214			{
215		✗	Geom::Point n0 = (p01 - p00).ccw();
216		✗	double d0 = dot(n0,p00);
217
218		✗	Geom::Point n1 = (p11 - p10).ccw();
219		✗	double d1 = dot(n1,p10);
220		✗	return line_intersection(n0, d0, n1, d1, result);
221			}
222
223			// this is used to compare points for std::sort below
224			static bool
225		✗	is_less(Point const &A, Point const &B)
226			{
227		✗	if (A[X] < B[X]) {
228		✗	return true;
229		✗	} else if (A[X] == B[X] && A[Y] < B[Y]) {
230		✗	return true;
231			} else {
232		✗	return false;
233			}
234			}
235
236			// TODO: this can doubtlessly be improved
237			static void
238		✗	eliminate_duplicates_p(std::vector<Point> &pts)
239			{
240		✗	unsigned int size = pts.size();
241
242		✗	if (size < 2)
243		✗	return;
244
245		✗	if (size == 2) {
246		✗	if (pts[0] == pts[1]) {
247		✗	pts.pop_back();
248			}
249			} else {
250		✗	std::sort(pts.begin(), pts.end(), &is_less);
251		✗	if (size == 3) {
252		✗	if (pts[0] == pts[1]) {
253		✗	pts.erase(pts.begin());
254		✗	} else if (pts[1] == pts[2]) {
255		✗	pts.pop_back();
256			}
257			} else {
258			// we have size == 4
259		✗	if (pts[2] == pts[3]) {
260		✗	pts.pop_back();
261			}
262		✗	if (pts[0] == pts[1]) {
263		✗	pts.erase(pts.begin());
264			}
265			}
266			}
267			}
268
269			/** Determine whether \& where an (infinite) line intersects a rectangle.
270			*
271			* \a c0, \a c1 are diagonal corners of the rectangle and
272			* \a p1, \a p1 are distinct points on the line
273			*
274			* \return A list (possibly empty) of points of intersection. If two such points (say \a r0 and \a
275			* r1) then it is guaranteed that the order of \a r0, \a r1 along the line is the same as the that
276			* of \a c0, \a c1 (i.e., the vectors \a r1 - \a r0 and \a p1 - \a p0 point into the same
277			* direction).
278			*/
279			std::vector<Geom::Point>
280		✗	rect_line_intersect(Geom::Point const &c0, Geom::Point const &c1,
281			Geom::Point const &p0, Geom::Point const &p1)
282			{
283			using namespace Geom;
284
285		✗	std::vector<Point> results;
286
287		✗	Point A(c0);
288		✗	Point C(c1);
289
290		✗	Point B(A[X], C[Y]);
291		✗	Point D(C[X], A[Y]);
292
293		✗	Point res;
294
295		✗	if (line_segment_intersect(p0, p1, A, B, res) == intersects) {
296		✗	results.push_back(res);
297			}
298		✗	if (line_segment_intersect(p0, p1, B, C, res) == intersects) {
299		✗	results.push_back(res);
300			}
301		✗	if (line_segment_intersect(p0, p1, C, D, res) == intersects) {
302		✗	results.push_back(res);
303			}
304		✗	if (line_segment_intersect(p0, p1, D, A, res) == intersects) {
305		✗	results.push_back(res);
306			}
307
308		✗	eliminate_duplicates_p(results);
309
310		✗	if (results.size() == 2) {
311			// sort the results so that the order is the same as that of p0 and p1
312		✗	Point dir1 (results[1] - results[0]);
313		✗	Point dir2 (p1 - p0);
314		✗	if (dot(dir1, dir2) < 0) {
315		✗	swap(results[0], results[1]);
316			}
317			}
318
319		✗	return results;
320		✗	}
321
322			/** Determine whether \& where an (infinite) line intersects a rectangle.
323			*
324			* \a c0, \a c1 are diagonal corners of the rectangle and
325			* \a p1, \a p1 are distinct points on the line
326			*
327			* \return A list (possibly empty) of points of intersection. If two such points (say \a r0 and \a
328			* r1) then it is guaranteed that the order of \a r0, \a r1 along the line is the same as the that
329			* of \a c0, \a c1 (i.e., the vectors \a r1 - \a r0 and \a p1 - \a p0 point into the same
330			* direction).
331			*/
332			std::optional<LineSegment>
333		✗	rect_line_intersect(Geom::Rect &r,
334			Geom::LineSegment ls)
335			{
336		✗	std::vector<Point> results;
337
338		✗	results = rect_line_intersect(r.min(), r.max(), ls[0], ls[1]);
339		✗	if(results.size() == 2) {
340		✗	return LineSegment(results[0], results[1]);
341			}
342		✗	return std::optional<LineSegment>();
343		✗	}
344
345			std::optional<LineSegment>
346		✗	rect_line_intersect(Geom::Rect &r,
347			Geom::Line l)
348			{
349		✗	return rect_line_intersect(r, l.segment(0, 1));
350			}
351
352			/**
353			* polyCentroid: Calculates the centroid (xCentroid, yCentroid) and area of a polygon, given its
354			* vertices (x[0], y[0]) ... (x[n-1], y[n-1]). It is assumed that the contour is closed, i.e., that
355			* the vertex following (x[n-1], y[n-1]) is (x[0], y[0]). The algebraic sign of the area is
356			* positive for counterclockwise ordering of vertices in x-y plane; otherwise negative.
357
358			* Returned values:
359			0 for normal execution;
360			1 if the polygon is degenerate (number of vertices < 3);
361			2 if area = 0 (and the centroid is undefined).
362
363			* for now we require the path to be a polyline and assume it is closed.
364			**/
365
366		✗	int centroid(std::vector<Geom::Point> const &p, Geom::Point& centroid, double &area) {
367		✗	const unsigned n = p.size();
368		✗	if (n < 3)
369		✗	return 1;
370		✗	Geom::Point centroid_tmp(0,0);
371		✗	double atmp = 0;
372		✗	for (unsigned i = n-1, j = 0; j < n; i = j, j++) {
373		✗	const double ai = cross(p[j], p[i]);
374		✗	atmp += ai;
375		✗	centroid_tmp += (p[j] + p[i])*ai; // first moment.
376			}
377		✗	area = atmp / 2;
378		✗	if (atmp != 0) {
379		✗	centroid = centroid_tmp / (3 * atmp);
380		✗	return 0;
381			}
382		✗	return 2;
383			}
384
385			}
386
387			/*
388			Local Variables:
389			mode:c++
390			c-file-style:"stroustrup"
391			c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
392			indent-tabs-mode:nil
393			fill-column:99
394			End:
395			*/
396			// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :
397