Inkscape
Vector Graphics Editor
Loading...
Searching...
No Matches
line-test.cpp
Go to the documentation of this file.
1/*
5 * Authors:
6 * Krzysztof Kosiński <tweenk.pl@gmail.com>
7 *
8 * Copyright 2015 Authors
9 *
10 * This library is free software; you can redistribute it and/or
11 * modify it either under the terms of the GNU Lesser General Public
12 * License version 2.1 as published by the Free Software Foundation
13 * (the "LGPL") or, at your option, under the terms of the Mozilla
14 * Public License Version 1.1 (the "MPL"). If you do not alter this
15 * notice, a recipient may use your version of this file under either
16 * the MPL or the LGPL.
17 *
18 * You should have received a copy of the LGPL along with this library
19 * in the file COPYING-LGPL-2.1; if not, write to the Free Software
20 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
21 * You should have received a copy of the MPL along with this library
22 * in the file COPYING-MPL-1.1
23 *
24 * The contents of this file are subject to the Mozilla Public License
25 * Version 1.1 (the "License"); you may not use this file except in
26 * compliance with the License. You may obtain a copy of the License at
27 * http://www.mozilla.org/MPL/
28 *
29 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
30 * OF ANY KIND, either express or implied. See the LGPL or the MPL for
31 * the specific language governing rights and limitations.
32 */
33
34#include "testing.h"
35#include <iostream>
36#include <glib.h>
37
38#include <2geom/line.h>
39#include <2geom/affine.h>
40
41using namespace Geom;
42
43TEST(LineTest, VectorAndVersor) {
44 Line a(Point(10, 10), Point(-10, 20));
45 Line b(Point(10, 10), Point(15, 15));
46 EXPECT_EQ(a.vector(), Point(-20, 10));
47 EXPECT_EQ(b.vector(), Point(5, 5));
48 EXPECT_EQ(a.versor(), a.vector().normalized());
49 EXPECT_EQ(b.versor(), b.vector().normalized());
50}
51
52TEST(LineTest, AngleBisector) {
53 Point o(0,0), a(1,1), b(3,0), c(-4, 0);
54 Point d(0.5231, 0.75223);
55
56 // normal
57 Line ab1 = make_angle_bisector_line(a + d, o + d, b + d);
58 Line ab2 = make_angle_bisector_line(a - d, o - d, b - d);
59 EXPECT_FLOAT_EQ(ab1.angle(), Angle::from_degrees(22.5));
60 EXPECT_FLOAT_EQ(ab2.angle(), Angle::from_degrees(22.5));
61
62 // half angle
63 Line bc1 = make_angle_bisector_line(b + d, o + d, c + d);
64 Line bc2 = make_angle_bisector_line(b - d, o - d, c - d);
65 EXPECT_FLOAT_EQ(bc1.angle(), Angle::from_degrees(90));
66 EXPECT_FLOAT_EQ(bc2.angle(), Angle::from_degrees(90));
67
68 // zero angle
69 Line aa1 = make_angle_bisector_line(a + d, o + d, a + d);
70 Line aa2 = make_angle_bisector_line(a - d, o - d, a - d);
71 EXPECT_FLOAT_EQ(aa1.angle(), Angle::from_degrees(45));
72 EXPECT_FLOAT_EQ(aa2.angle(), Angle::from_degrees(45));
73}
74
75TEST(LineTest, Equality) {
76 Line a(Point(0,0), Point(2,2));
77 Line b(Point(2,2), Point(5,5));
78
79 EXPECT_EQ(a, a);
80 EXPECT_EQ(b, b);
81 EXPECT_EQ(a, b);
82}
83
84TEST(LineTest, Reflection) {
85 Line a(Point(10, 0), Point(15,5));
86 Point pa(10,5), ra(15,0);
87
88 Line b(Point(1,-2), Point(2,0));
89 Point pb(5,1), rb(1,3);
90 Affine reflecta = a.reflection(), reflectb = b.reflection();
91
92 Point testra = pa * reflecta;
93 Point testrb = pb * reflectb;
94
95 constexpr Coord eps{1e-12};
96 EXPECT_near(testra[X], ra[X], eps);
97 EXPECT_near(testra[Y], ra[Y], eps);
98 EXPECT_near(testrb[X], rb[X], eps);
99 EXPECT_near(testrb[Y], rb[Y], eps);
100}
101
102TEST(LineTest, RotationToZero) {
103 Line a(Point(-5,23), Point(15,27));
104 Affine mx = a.rotationToZero(X);
105 Affine my = a.rotationToZero(Y);
106
107 for (unsigned i = 0; i <= 12; ++i) {
108 double t = -1 + 0.25 * i;
109 Point p = a.pointAt(t);
110 Point rx = p * mx;
111 Point ry = p * my;
112 //std::cout << rx[X] << " " << ry[Y] << std::endl;
113 // unfortunately this is precise only to about 1e-14
114 EXPECT_NEAR(rx[X], 0, 1e-14);
115 EXPECT_NEAR(ry[Y], 0, 1e-14);
116 }
117}
118
119TEST(LineTest, Coefficients) {
120 std::vector<Line> lines;
121 lines.emplace_back(Point(1e3,1e3), Point(1,1));
122 //the case below will never work without normalizing the line
123 //lines.emplace_back(Point(1e5,1e5), Point(1e-15,0));
124 lines.emplace_back(Point(1e5,1e5), Point(1e5,-1e5));
125 lines.emplace_back(Point(-3,10), Point(3,10));
126 lines.emplace_back(Point(250,333), Point(-72,121));
127
128 for (auto & line : lines) {
129 Coord a, b, c, A, B, C;
130 line.coefficients(a, b, c);
131 /*std::cout << format_coord_nice(a) << " "
132 << format_coord_nice(b) << " "
133 << format_coord_nice(c) << std::endl;*/
134 Line k(a, b, c);
135 //std::cout << k.initialPoint() << " " << k.finalPoint() << std::endl;
136 k.coefficients(A, B, C);
137 /*std::cout << format_coord_nice(A) << " "
138 << format_coord_nice(B) << " "
139 << format_coord_nice(C) << std::endl;*/
140 EXPECT_DOUBLE_EQ(a, A);
141 EXPECT_DOUBLE_EQ(b, B);
142 EXPECT_DOUBLE_EQ(c, C);
143
144 for (unsigned j = 0; j <= 10; ++j) {
145 double t = j / 10.;
146 Point p = line.pointAt(t);
147 /*std::cout << t << " " << p << " "
148 << A*p[X] + B*p[Y] + C << " "
149 << A*(p[X]-1) + B*(p[Y]+1) + C << std::endl;*/
150 EXPECT_near(A*p[X] + B*p[Y] + C, 0., 2e-11);
151 EXPECT_not_near(A*(p[X]-1) + B*(p[Y]+1) + C, 0., 1e-6);
152 }
153 }
154}
155
156TEST(LineTest, Intersection) {
157 Line a(Point(0,3), Point(1,2));
158 Line b(Point(0,-3), Point(1,-2));
159 LineSegment lsa(Point(0,3), Point(1,2));
160 LineSegment lsb(Point(0,-3), Point(1,-2));
161 LineSegment lsc(Point(3,1), Point(3, -1));
162
163 std::vector<ShapeIntersection> r1, r2, r3;
164
165 r1 = a.intersect(b);
166 ASSERT_EQ(r1.size(), 1u);
167 EXPECT_EQ(r1[0].point(), Point(3,0));
168 EXPECT_intersections_valid(a, b, r1, 1e-15);
169
170 r2 = a.intersect(lsc);
171 ASSERT_EQ(r2.size(), 1u);
172 EXPECT_EQ(r2[0].point(), Point(3,0));
173 EXPECT_intersections_valid(a, lsc, r2, 1e-15);
174
175 r3 = b.intersect(lsc);
176 ASSERT_EQ(r3.size(), 1u);
177 EXPECT_EQ(r3[0].point(), Point(3,0));
178 EXPECT_intersections_valid(a, lsc, r3, 1e-15);
179
180 EXPECT_TRUE(lsa.intersect(lsb).empty());
181 EXPECT_TRUE(lsa.intersect(lsc).empty());
182 EXPECT_TRUE(lsb.intersect(lsc).empty());
183 EXPECT_TRUE(a.intersect(lsb).empty());
184 EXPECT_TRUE(b.intersect(lsa).empty());
185}
186
187#define RAND10 g_random_double_range(-10.0, 10.0)
188
192TEST(LineTest, CoincidingIntersect)
193{
194 auto const eps = 1e-14;
195 auto const check_endpoint_intersections = [=](LineSegment const &s1, LineSegment const &s2) {
196 auto xings = s1.intersect(s2, eps);
197 ASSERT_EQ(xings.size(), 2);
198 EXPECT_TRUE(are_near(xings[0], s1.initialPoint()));
199 EXPECT_TRUE(are_near(xings[1], s1.finalPoint()));
200 EXPECT_intersections_valid(s1, s2, xings, eps);
201 };
202
203 // This fails on 6f7dfdc0317362bf294fed54ad06d14ac14ad809
204 check_endpoint_intersections(LineSegment(Point{1, 0}, Point{0, 0}),
205 LineSegment(Point{0, 0}, Point{1, 0}));
206
207 g_random_set_seed(0x13370AFA);
208 for (size_t _ = 0; _ < 10'000; _++) {
209 auto const a = Point(RAND10, RAND10);
210 auto const b = Point(RAND10, RAND10);
211 auto const ab = LineSegment(a, b);
212 auto const ba = LineSegment(b, a);
213 check_endpoint_intersections(ab, ab);
214 check_endpoint_intersections(ba, ba);
215 check_endpoint_intersections(ab, ba);
216 }
217}
218
223TEST(LineTest, OverlappingIntersect)
224{
225 g_random_set_seed(0xCAFECAFE);
226 // Suppose the segments are [A, B] and [C, D].
227 // Case 1: A=C, B halfway between A and D
228 for (size_t _ = 0; _ < 10'000; _++)
229 {
230 auto const a = Point(RAND10, RAND10);
231 auto const d = Point(RAND10, RAND10);
232 auto const b = middle_point(a, d);
233 auto const ab = LineSegment(a, b);
234 auto const cd = LineSegment(a, d);
235 auto xings = ab.intersect(cd);
236 ASSERT_FALSE(xings.empty());
237 EXPECT_TRUE(are_near(xings[0], ab.initialPoint()));
238 EXPECT_intersections_valid(ab, cd, xings, 1e-12);
239 }
240
241 // Case 2: AB wholly contained inside CD
242 for (size_t _ = 0; _ < 10'000; _++)
243 {
244 auto const c = Point(RAND10, RAND10);
245 auto const d = Point(RAND10, RAND10);
246 auto const a = lerp(0.25, c, d);
247 auto const b = lerp(0.75, c, d);
248 auto const ab = LineSegment(a, b);
249 auto const cd = LineSegment(a, d);
250 auto xings = ab.intersect(cd);
251 ASSERT_FALSE(xings.empty());
252 EXPECT_TRUE(are_near(xings[0], ab.initialPoint()));
253 EXPECT_intersections_valid(ab, cd, xings, 1e-12);
254 }
255}
256
260TEST(LineTest, AlmostIntersect)
261{
262 for (double eps : {1e-12, 1e-11, 1e-10, 1e-9, 1e-8, 1e-7, 1e-6, 1e-3, 1.0}) {
263 auto const vertical = LineSegment(Point(0.0, 0.5 * eps), Point(0.0, 1.0));
264 auto const horizontal = LineSegment(Point(0.5 * eps, 0.0), Point(1.0, 0.0));
265 auto const butt = LineSegment(Point(0.0, -0.49 * eps), Point(0.0, -1.0));
266 auto const too_far = LineSegment(Point(0.0, -0.51 * eps), Point(0.0, -1.0));
267 auto xings = vertical.intersect(horizontal, eps);
268 ASSERT_FALSE(xings.empty());
269 EXPECT_intersections_valid(vertical, horizontal, xings, eps);
270 xings = vertical.intersect(butt, eps);
271 ASSERT_FALSE(xings.empty());
272 EXPECT_intersections_valid(vertical, butt, xings, eps);
273 xings = vertical.intersect(too_far, eps);
274 ASSERT_TRUE(xings.empty());
275 }
276}
277
279TEST(LineTest, FuzzyOverlap)
280{
281 auto const ab = LineSegment(Point(0, 0), Point(0, 20));
282 auto const cd = LineSegment(Point(0, 10), Point(0, 30));
283 auto xings = ab.intersect(cd, 4); // extra large eps
284 ASSERT_EQ(xings.size(), 2);
285 EXPECT_DOUBLE_EQ(xings[0].point()[1], 10);
286 EXPECT_DOUBLE_EQ(xings[0].first, 0.5);
287 EXPECT_DOUBLE_EQ(xings[0].second, 0.0);
288 EXPECT_DOUBLE_EQ(xings[1].point()[1], 20);
289 EXPECT_DOUBLE_EQ(xings[1].first, 1.0);
290 EXPECT_DOUBLE_EQ(xings[1].second, 0.5);
291}
292
295TEST(LineTest, FuzzyEndToEnd)
296{
297 auto const ab = LineSegment(Point(0, 0), Point(0, 10));
298 auto const cd = LineSegment(Point(0, 10), Point(0, 30));
299 auto xings = ab.intersect(cd, 4); // extra large eps
300 ASSERT_EQ(xings.size(), 1);
301 EXPECT_DOUBLE_EQ(xings[0].point()[1], 10);
302 EXPECT_DOUBLE_EQ(xings[0].first, 1.0);
303 EXPECT_DOUBLE_EQ(xings[0].second, 0.0);
304}
305
309TEST(LineTest, AlmostTouch)
310{
311 auto const ab = LineSegment(Point(0, 0), Point(0, 99));
312 auto const cd = LineSegment(Point(0, 101), Point(0, 200));
313 auto xings = ab.intersect(cd, 12); // extra large eps
314 ASSERT_EQ(xings.size(), 1);
315 auto &x = xings[0];
316 EXPECT_DOUBLE_EQ(x.point()[X], 0);
317 EXPECT_DOUBLE_EQ(x.point()[Y], 100);
318 EXPECT_DOUBLE_EQ(x.first, 1.0);
319 EXPECT_DOUBLE_EQ(x.second, 0.0);
320}
321
326TEST(LineTest, TBone)
327{
328 auto const horizontal = LineSegment(Point(-1, 1), Point(1, 1));
329 g_random_set_seed(0x01234567);
330
331 for (int exponent = -2; exponent > -13; exponent--) {
332 double const eps = std::pow(10, exponent);
333 for (size_t _ = 0; _ < 10'000; _++) {
334 auto const distance = g_random_double_range(0.0, 2.0 * eps);
335 size_t const expected_crossing_count = (size_t)(distance <= eps);
336 auto const xings = horizontal.intersect(LineSegment(Point(0, 0), Point(0, 1.0 - distance)), eps);
337 ASSERT_EQ(xings.size(), expected_crossing_count);
338 if (expected_crossing_count) {
339 auto const &x = xings[0];
340 EXPECT_DOUBLE_EQ(x.point()[X], 0.0);
341 EXPECT_DOUBLE_EQ(x.point()[Y], 1.0 - (0.5 * distance));
342 EXPECT_DOUBLE_EQ(x.first, 0.5);
343 EXPECT_DOUBLE_EQ(x.second, 1.0);
344 }
345 }
346 }
347}
348
352TEST(LineTest, PushOff)
353{
354 auto const seg = LineSegment(Point(0, 0), Point(5, 3));
355 auto const normal = (seg.finalPoint() - seg.initialPoint()).cw().normalized();
356 g_random_set_seed(0xB787A350);
357
358 for (int exponent = 1; exponent > -13; exponent--) {
359 double const eps = std::pow(10, exponent);
360 for (size_t _ = 0; _ < 10'000; _++) {
361 auto const pushoff_distance = g_random_double_range(0.0, 2.0 * eps);
362 std::unique_ptr<LineSegment> pushed_off{
363 dynamic_cast<LineSegment *>(
364 seg.transformed(
365 Geom::Translate(pushoff_distance * normal)
366 )
367 ) };
368 auto const xings = seg.intersect(*pushed_off, eps);
369 bool const too_far = pushoff_distance > eps;
370 EXPECT_EQ(xings.empty(), too_far);
371 for (auto const &x : xings) {
372 EXPECT_TRUE(are_near(x.first, 0.0, eps) or are_near(x.first, 1.0, eps));
373 EXPECT_TRUE(are_near(x.second, 0.0, eps) or are_near(x.second, 1.0, eps));
374 }
375 }
376 }
377}
378
379/*
380 Local Variables:
381 mode:c++
382 c-file-style:"stroustrup"
383 c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
384 indent-tabs-mode:nil
385 fill-column:99
386 End:
387*/
388// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :
affine.h
3x3 affine transformation matrix.
Geom::Affine
3x3 matrix representing an affine transformation.
Definition affine.h:70
Geom::Angle::from_degrees
static Angle from_degrees(Coord d)
Create an angle from its measure in degrees.
Definition angle.h:136
Geom::BezierCurveN::intersect
std::vector< CurveIntersection > intersect(Curve const &other, Coord eps=EPSILON) const override
Compute intersections with another curve.
Definition bezier-curve.h:286
Geom::BezierCurve::finalPoint
Point finalPoint() const override
Retrieve the end of the curve.
Definition bezier-curve.h:106
Geom::BezierCurve::initialPoint
Point initialPoint() const override
Retrieve the start of the curve.
Definition bezier-curve.h:105
Geom::Intersection
Intersection between two shapes.
Definition intersection.h:48
Geom::Line
Infinite line on a plane.
Definition line.h:53
Geom::Line::coefficients
std::vector< double > coefficients() const
Get the coefficients of the line equation as a vector.
Definition line.cpp:120
Geom::Line::rotationToZero
Affine rotationToZero(Dim2 d) const
Compute an affine which transforms all points on the line to zero X or Y coordinate.
Definition line.h:350
Geom::Line::reflection
Affine reflection() const
Compute an affine matrix representing a reflection about the line.
Definition line.h:332
Geom::Line::vector
Point vector() const
Get the line's raw direction vector.
Definition line.h:132
Geom::Line::intersect
std::vector< ShapeIntersection > intersect(Line const &other) const
Definition line.cpp:253
Geom::Line::angle
Coord angle() const
Angle the line makes with the X axis, in mathematical convention.
Definition line.h:137
Geom::Line::pointAt
Point pointAt(Coord t) const
Definition line.h:231
Geom::Line::versor
Point versor() const
Get the line's normalized direction vector.
Definition line.h:135
Geom::Point
Two-dimensional point that doubles as a vector.
Definition point.h:66
Geom::Point::normalized
Point normalized() const
Definition point.h:121
Geom::Translate
Translation by a vector.
Definition transforms.h:115
c
double c[8][4]
Definition cylinder3d.cpp:40
Geom::LineSegment
BezierCurveN< 1 > LineSegment
Line segment.
Definition bezier-curve.h:310
Geom::lerp
constexpr Coord lerp(Coord t, Coord a, Coord b)
Numerically stable linear interpolation.
Definition coord.h:97
Geom::Coord
double Coord
Floating point type used to store coordinates.
Definition coord.h:76
Geom::Y
@ Y
Definition coord.h:48
Geom::X
@ X
Definition coord.h:48
line.h
Infinite straight line.
Geom
Various utility functions.
Definition affine.h:22
Geom::distance
Angle distance(Angle const &a, Angle const &b)
Definition angle.h:163
Geom::TEST
TEST(AffineTest, Equality)
Definition affine-test.cpp:40
Geom::make_angle_bisector_line
Line make_angle_bisector_line(Point const &A, Point const &O, Point const &B)
Definition line.h:504
Geom::are_near
bool are_near(Affine const &a1, Affine const &a2, Coord eps=EPSILON)
Geom::middle_point
Point middle_point(LineSegment const &_segment)
Definition bezier-curve.h:344