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#ifndef BOOST_GIL_EXTENSION_RASTERIZATION_CIRCLE_HPP
9#define BOOST_GIL_EXTENSION_RASTERIZATION_CIRCLE_HPP
10
11#include <boost/gil/detail/math.hpp>
12#include <boost/gil/extension/rasterization/apply_rasterizer.hpp>
13#include <boost/gil/point.hpp>
14
15#include <cmath>
16#include <cstddef>
17#include <vector>
18
19namespace boost { namespace gil {
20
21struct circle_rasterizer_t{};
22
23/// \defgroup CircleRasterization
24/// \ingroup Rasterization
25/// \brief Circle rasterization algorithms
26///
27/// The main problems are connectivity and equation following. Circle can be easily moved
28/// to new offset, and rotation has no effect on it (not recommended to do rotation).
29
30/// \ingroup CircleRasterization
31/// \brief Rasterize trigonometric circle according to radius by sine and radius by cosine
32///
33/// This rasterizer is the one used that is used in standard Hough circle transform in
34/// the books. It is also quite expensive to compute.
35/// WARNING: the product of this rasterizer does not follow circle equation, even though it
36/// produces quite round like shapes.
37struct trigonometric_circle_rasterizer
38{
39 using type = circle_rasterizer_t;
40
41 /// \brief Creates a trigonometric circle rasterizer
42 /// \param center_point - Point containing positive integer x co-ordinate and y co-ordinate of the
43 /// center respectively.
44 /// \param circle_radius - Radius of the circle
45 trigonometric_circle_rasterizer(point_t center_point, std::ptrdiff_t circle_radius)
46 : center(center_point), radius(circle_radius)
47 {}
48
49 /// \brief Calculates minimum angle step that is distinguishable when walking on circle
50 ///
51 /// It is important to not have disconnected circle and to not compute unnecessarily,
52 /// thus the result of this function is used when rendering.
53 double minimum_angle_step() const noexcept
54 {
55 const auto diameter = radius * 2 - 1;
56 return std::atan2(y: 1.0, x: diameter);
57 }
58
59 /// \brief Calculate the amount of points that rasterizer will output
60 std::ptrdiff_t point_count() const noexcept
61 {
62 return 8 * static_cast<std::ptrdiff_t>(
63 std::round(x: detail::pi / 4 / minimum_angle_step()) + 1);
64 }
65
66 /// \brief perform rasterization and output into d_first
67 template <typename OutputIterator>
68 void operator()(OutputIterator d_first) const
69 {
70 const double minimum_angle_step = std::atan2(y: 1.0, x: radius);
71 auto translate_mirror_points = [this, &d_first](point_t p) {
72 *d_first++ = point_t{center.x + p.x, center.y + p.y};
73 *d_first++ = point_t{center.x + p.x, center.y - p.y};
74 *d_first++ = point_t{center.x - p.x, center.y + p.y};
75 *d_first++ = point_t{center.x - p.x, center.y - p.y};
76 *d_first++ = point_t{center.x + p.y, center.y + p.x};
77 *d_first++ = point_t{center.x + p.y, center.y - p.x};
78 *d_first++ = point_t{center.x - p.y, center.y + p.x};
79 *d_first++ = point_t{center.x - p.y, center.y - p.x};
80 };
81 const std::ptrdiff_t iteration_count = point_count() / 8;
82 double angle = 0;
83 // do note that + 1 was done inside count estimation, thus <= is not needed, only <
84 for (std::ptrdiff_t i = 0; i < iteration_count; ++i, angle += minimum_angle_step)
85 {
86 std::ptrdiff_t x = static_cast<std::ptrdiff_t>(std::round(x: radius * std::cos(x: angle)));
87 std::ptrdiff_t y = static_cast<std::ptrdiff_t>(std::round(x: radius * std::sin(x: angle)));
88 translate_mirror_points({x, y});
89 }
90 }
91
92 point_t center;
93 std::ptrdiff_t radius;
94};
95
96/// \ingroup CircleRasterization
97/// \brief Perform circle rasterization according to Midpoint algorithm
98///
99/// This algorithm givess reasonable output and is cheap to compute.
100/// reference:
101/// https://en.wikipedia.org/wiki/Midpoint_circle_algorithm
102struct midpoint_circle_rasterizer
103{
104 using type = circle_rasterizer_t;
105
106 /// \brief Creates a midpoint circle rasterizer
107 /// \param center_point - Point containing positive integer x co-ordinate and y co-ordinate of the
108 /// center respectively.
109 /// \param circle_radius - Radius of the circle
110 midpoint_circle_rasterizer(point_t center_point, std::ptrdiff_t circle_radius)
111 : center(center_point), radius(circle_radius)
112 {}
113
114 /// \brief Calculate the amount of points that rasterizer will output
115 std::ptrdiff_t point_count() const noexcept
116 {
117 // the reason for pulling 8 out is so that when the expression radius * cos(45 degrees)
118 // is used, it would yield the same result as here
119 // + 1 at the end is because the point at radius itself is computed as well
120 return 8 * static_cast<std::ptrdiff_t>(
121 std::round(x: radius * std::cos(x: boost::gil::detail::pi / 4)) + 1);
122 }
123
124 /// \brief perform rasterization and output into d_first
125 template <typename OutputIterator>
126 void operator()(OutputIterator d_first) const
127 {
128 auto translate_mirror_points = [this, &d_first](point_t p) {
129 *d_first++ = point_t{center.x + p.x, center.y + p.y};
130 *d_first++ = point_t{center.x + p.x, center.y - p.y};
131 *d_first++ = point_t{center.x - p.x, center.y + p.y};
132 *d_first++ = point_t{center.x - p.x, center.y - p.y};
133 *d_first++ = point_t{center.x + p.y, center.y + p.x};
134 *d_first++ = point_t{center.x + p.y, center.y - p.x};
135 *d_first++ = point_t{center.x - p.y, center.y + p.x};
136 *d_first++ = point_t{center.x - p.y, center.y - p.x};
137 };
138 std::ptrdiff_t iteration_distance = point_count() / 8;
139 std::ptrdiff_t y_current = radius;
140 std::ptrdiff_t r_squared = radius * radius;
141 translate_mirror_points({0, y_current});
142 for (std::ptrdiff_t x = 1; x < iteration_distance; ++x)
143 {
144 std::ptrdiff_t midpoint = x * x + y_current * y_current - y_current - r_squared;
145 if (midpoint > 0)
146 {
147 --y_current;
148 }
149 translate_mirror_points({x, y_current});
150 }
151 }
152
153 point_t center;
154 std::ptrdiff_t radius;
155};
156
157namespace detail {
158
159template <typename View, typename Rasterizer, typename Pixel>
160struct apply_rasterizer_op<View, Rasterizer, Pixel, circle_rasterizer_t>
161{
162 void operator()(
163 View const& view, Rasterizer const& rasterizer, Pixel const& pixel)
164 {
165 std::vector<point_t> trajectory(rasterizer.point_count());
166 rasterizer(std::begin(cont&: trajectory));
167
168 for (auto const& point : trajectory)
169 {
170 view(point) = pixel;
171 }
172 }
173};
174
175} //namespace detail
176
177}} // namespace boost::gil
178
179#endif
180

source code of boost/libs/gil/include/boost/gil/extension/rasterization/circle.hpp