1//
2// Copyright 2020 Olzhas Zhumabek <anonymous.from.applecity@gmail.com>
3//
4// Use, modification and distribution are subject to the Boost Software License,
5// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
6// http://www.boost.org/LICENSE_1_0.txt)
7//
8
9#include "core/point/test_fixture.hpp"
10
11#include <boost/gil/point.hpp>
12#include <boost/gil/extension/rasterization/line.hpp>
13
14#include <boost/core/lightweight_test.hpp>
15
16#include <algorithm>
17#include <cmath>
18#include <cstdint>
19#include <iterator>
20#include <random>
21#include <vector>
22
23namespace gil = boost::gil;
24
25using line_type = std::vector<gil::point_t>;
26
27struct endpoints
28{
29 gil::point_t start;
30 gil::point_t end;
31};
32
33endpoints create_endpoints(std::mt19937& twister,
34 std::uniform_int_distribution<std::ptrdiff_t>& distr)
35{
36 gil::point_t start{distr(twister), distr(twister)};
37 gil::point_t end{distr(twister), distr(twister)};
38 return {.start: start, .end: end};
39}
40
41line_type create_line(endpoints points)
42{
43 gil::bresenham_line_rasterizer rasterizer(points.start, points.end);
44 line_type forward_line(rasterizer.point_count());
45 rasterizer(forward_line.begin());
46 return forward_line;
47}
48
49void test_start_end(line_type const& line_points, endpoints points)
50{
51 BOOST_TEST_EQ(line_points.front(), points.start);
52 BOOST_TEST_EQ(line_points.back(), points.end);
53}
54
55// Look at TODO below
56// void test_two_way_equivalence(const line_type& forward, line_type backward)
57// {
58// std::reverse(backward.begin(), backward.end());
59// BOOST_TEST_ALL_EQ(forward.begin(), forward.end(), backward.begin(), backward.end());
60// }
61
62void test_connectivity(line_type const& line_points)
63{
64 for (std::size_t i = 1; i < line_points.size(); ++i)
65 {
66 const auto x_diff = std::abs(i: line_points[i].x - line_points[i - 1].x);
67 const auto y_diff = std::abs(i: line_points[i].y - line_points[i - 1].y);
68 BOOST_TEST_LE(x_diff, 1);
69 BOOST_TEST_LE(y_diff, 1);
70 }
71}
72
73void test_bresenham_rasterizer_follows_equation(line_type line_points)
74{
75 auto start = line_points.front();
76 auto end = line_points.back();
77
78 auto width = std::abs(i: end.x - start.x) + 1;
79 auto height = std::abs(i: end.y - start.y) + 1;
80 if (width < height)
81 {
82 std::swap(a&: width, b&: height);
83 std::transform(first: line_points.begin(), last: line_points.end(), result: line_points.begin(),
84 unary_op: [](gil::point_t p)
85 {
86 return gil::point_t{p.y, p.x};
87 });
88 // update start and end
89 start = line_points.front();
90 end = line_points.back();
91 }
92 const double sign = [start, end]()
93 {
94 auto const width_sign = end.x < start.x;
95 auto const height_sign = end.y < start.y;
96 auto const slope_sign = width_sign != height_sign;
97 return slope_sign ? -1 : 1;
98 }();
99 const double slope = static_cast<double>(height) / static_cast<double>(width);
100 const double intercept =
101 static_cast<double>(start.y) - sign * slope * static_cast<double>(start.x);
102 for (const auto& point : line_points)
103 {
104 double const expected_y = sign * slope * static_cast<double>(point.x) + intercept;
105 auto const difference =
106 std::abs(i: point.y - static_cast<std::ptrdiff_t>(std::round(x: expected_y)));
107 BOOST_TEST_LE(difference, static_cast<std::ptrdiff_t>(slope + 1));
108 }
109}
110
111int main()
112{
113 const std::ptrdiff_t size = 256;
114 for (std::size_t seed = 0; seed <= 100; ++seed)
115 {
116 std::mt19937 twister(seed);
117 std::uniform_int_distribution<std::ptrdiff_t> distr(0, size - 1);
118 const std::size_t sample_count = 100;
119 for (std::size_t sample_index = 0; sample_index < sample_count; ++sample_index)
120 {
121 auto endpoints = create_endpoints(twister, distr);
122 auto forward_line = create_line(points: endpoints);
123 test_start_end(line_points: forward_line, points: endpoints);
124 // TODO: figure out if forward/backward equivalence is possible to provide
125 // auto backward_line = create_line({endpoints.end, endpoints.start});
126 // test_two_way_equivalence(forward_line, backward_line);
127 test_connectivity(line_points: forward_line);
128 // test_connectivity(backward_line);
129 test_bresenham_rasterizer_follows_equation(line_points: forward_line);
130 // test_bresenham_rasterizer_follows_equation(backward_line);
131 }
132 }
133
134 return boost::report_errors();
135}
136

source code of boost/libs/gil/test/extension/rasterization/line.cpp