Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
Loading...
Searching...
No Matches
Classes | Functions
smallest_circle.cpp File Reference

Get centre and radius of the smallest circle that circumscribes given set of points. More...

#include <cmath>
#include <iostream>
#include <vector>
Include dependency graph for smallest_circle.cpp:

Classes

struct  Point
 

Functions

double LenghtLine (const Point &A, const Point &B)
 
double TriangleArea (const Point &A, const Point &B, const Point &C)
 
bool PointInCircle (const std::vector< Point > &P, const Point &Center, double R)
 
double circle (const std::vector< Point > &P)
 
void test ()
 
void test2 ()
 
void test3 ()
 
int main ()
 

Detailed Description

Get centre and radius of the smallest circle that circumscribes given set of points.

See also
other implementation

Function Documentation

◆ circle()

double circle ( const std::vector< Point > & P)

Find the centre and radius of a circle enclosing a set of points.
The function returns the radius of the circle and prints the coordinated of the centre of the circle.

Parameters
[in]Pvector of points
Returns
radius of the circle
87 {
88 double minR = INFINITY;
89 double R;
90 Point C;
91 Point minC;
92
93 /* This code is invalid and does not give correct result for TEST 3 */
94 // for each point in the list
95 for (size_t i = 0; i < P.size() - 2; i++)
96 // for every subsequent point in the list
97 for (size_t j = i + 1; j < P.size(); j++)
98 // for every subsequent point in the list
99 for (size_t k = j + 1; k < P.size(); k++) {
100 // here, we now have picked three points from the given set of
101 // points that we can use
102 // viz., P[i], P[j] and P[k]
103 C.x = -0.5 * ((P[i].y * (P[j].x * P[j].x + P[j].y * P[j].y -
104 P[k].x * P[k].x - P[k].y * P[k].y) +
105 P[j].y * (P[k].x * P[k].x + P[k].y * P[k].y -
106 P[i].x * P[i].x - P[i].y * P[i].y) +
107 P[k].y * (P[i].x * P[i].x + P[i].y * P[i].y -
108 P[j].x * P[j].x - P[j].y * P[j].y)) /
109 (P[i].x * (P[j].y - P[k].y) +
110 P[j].x * (P[k].y - P[i].y) +
111 P[k].x * (P[i].y - P[j].y)));
112 C.y = 0.5 * ((P[i].x * (P[j].x * P[j].x + P[j].y * P[j].y -
113 P[k].x * P[k].x - P[k].y * P[k].y) +
114 P[j].x * (P[k].x * P[k].x + P[k].y * P[k].y -
115 P[i].x * P[i].x - P[i].y * P[i].y) +
116 P[k].x * (P[i].x * P[i].x + P[i].y * P[i].y -
117 P[j].x * P[j].x - P[j].y * P[j].y)) /
118 (P[i].x * (P[j].y - P[k].y) +
119 P[j].x * (P[k].y - P[i].y) +
120 P[k].x * (P[i].y - P[j].y)));
121 R = (LenghtLine(P[i], P[j]) * LenghtLine(P[j], P[k]) *
122 LenghtLine(P[k], P[i])) /
123 (4 * TriangleArea(P[i], P[j], P[k]));
124 if (!PointInCircle(P, C, R)) {
125 continue;
126 }
127 if (R <= minR) {
128 minR = R;
129 minC = C;
130 }
131 }
132
133 // for each point in the list
134 for (size_t i = 0; i < P.size() - 1; i++)
135 // for every subsequent point in the list
136 for (size_t j = i + 1; j < P.size(); j++) {
137 // check for diameterically opposite points
138 C.x = (P[i].x + P[j].x) / 2;
139 C.y = (P[i].y + P[j].y) / 2;
140 R = LenghtLine(C, P[i]);
141 if (!PointInCircle(P, C, R)) {
142 continue;
143 }
144 if (R <= minR) {
145 minR = R;
146 minC = C;
147 }
148 }
149 std::cout << minC.x << " " << minC.y << std::endl;
150 return minR;
151}
numerical_methods::simpson_method::k
double k(double x)
Another test function.
Definition composite_simpson_rule.cpp:117
std::endl
T endl(T... args)
std::vector::size
T size(T... args)
LenghtLine
double LenghtLine(const Point &A, const Point &B)
Definition smallest_circle.cpp:37
TriangleArea
double TriangleArea(const Point &A, const Point &B, const Point &C)
Definition smallest_circle.cpp:54
PointInCircle
bool PointInCircle(const std::vector< Point > &P, const Point &Center, double R)
Definition smallest_circle.cpp:72
Point
Definition line_segment_intersection.cpp:12
Point::y
int y
Point respect to x coordinate.
Definition line_segment_intersection.cpp:14
Here is the call graph for this function:

◆ LenghtLine()

double LenghtLine ( const Point & A,
const Point & B )

Compute the Euclidian distance between two points \(A\equiv(x_1,y_1)\) and \(B\equiv(x_2,y_2)\) using the formula:

\[d=\sqrt{\left(x_1-x_2\right)^2+\left(y_1-y_2\right)^2}\]

Parameters
[in]Apoint A
[in]Bpoint B
Returns
ditance
37 {
38 double dx = B.x - A.x;
39 double dy = B.y - A.y;
40 return std::sqrt((dx * dx) + (dy * dy));
41}
std::sqrt
T sqrt(T... args)
Here is the call graph for this function:

◆ main()

int main ( void )

Main program

198 {
199 test();
200 std::cout << std::endl;
201 test2();
202 std::cout << std::endl;
203 test3();
204 return 0;
205}
test2
void test2()
Definition smallest_circle.cpp:173
test3
void test3()
Definition smallest_circle.cpp:188
test
void test()
Definition smallest_circle.cpp:158
Here is the call graph for this function:

◆ PointInCircle()

bool PointInCircle ( const std::vector< Point > & P,
const Point & Center,
double R )

Check if a set of points lie within given circle. This is true if the distance of all the points from the centre of the circle is less than the radius of the circle

Parameters
[in]Pset of points to check
[in]Centercoordinates to centre of the circle
[in]Rradius of the circle
Returns
True if P lies on or within the circle
False if P lies outside the circle
72 {
73 for (size_t i = 0; i < P.size(); i++) {
74 if (LenghtLine(P[i], Center) > R)
75 return false;
76 }
77 return true;
78}
Here is the call graph for this function:

◆ test()

void test ( )

Test case: result should be:
Circle with
radius 3.318493136080724
centre at (3.0454545454545454, 1.3181818181818181)

158 {
159 std::vector<Point> Pv;
160 Pv.push_back(Point(0, 0));
161 Pv.push_back(Point(5, 4));
162 Pv.push_back(Point(1, 3));
163 Pv.push_back(Point(4, 1));
164 Pv.push_back(Point(3, -2));
165 std::cout << circle(Pv) << std::endl;
166}
std::vector::push_back
T push_back(T... args)
circle
double circle(const std::vector< Point > &P)
Definition smallest_circle.cpp:87
Here is the call graph for this function:

◆ test2()

void test2 ( )

Test case: result should be:
Circle with
radius 1.4142135623730951
centre at (1.0, 1.0)

173 {
174 std::vector<Point> Pv;
175 Pv.push_back(Point(0, 0));
176 Pv.push_back(Point(0, 2));
177 Pv.push_back(Point(2, 2));
178 Pv.push_back(Point(2, 0));
179 std::cout << circle(Pv) << std::endl;
180}
Here is the call graph for this function:

◆ test3()

void test3 ( )

Test case: result should be:
Circle with
radius 1.821078397711709
centre at (2.142857142857143, 1.7857142857142856)

Todo
This test fails
188 {
189 std::vector<Point> Pv;
190 Pv.push_back(Point(0.5, 1));
191 Pv.push_back(Point(3.5, 3));
192 Pv.push_back(Point(2.5, 0));
193 Pv.push_back(Point(2, 1.5));
194 std::cout << circle(Pv) << std::endl;
195}
Here is the call graph for this function:

◆ TriangleArea()

double TriangleArea ( const Point & A,
const Point & B,
const Point & C )

Compute the area of triangle formed by three points using Heron's formula. If the lengths of the sides of the triangle are \(a,\,b,\,c\) and \(s=\displaystyle\frac{a+b+c}{2}\) is the semi-perimeter then the area is given by

\[A=\sqrt{s(s-a)(s-b)(s-c)}\]

Parameters
[in]Avertex A
[in]Bvertex B
[in]Cvertex C
Returns
area of triangle
54 {
55 double a = LenghtLine(A, B);
56 double b = LenghtLine(B, C);
57 double c = LenghtLine(C, A);
58 double p = (a + b + c) / 2;
59 return std::sqrt(p * (p - a) * (p - b) * (p - c));
60}
Here is the call graph for this function: