Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
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 }
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 }
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 }
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  {
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 }
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  {
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  {
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:
test3
void test3()
Definition: smallest_circle.cpp:188
test2
void test2()
Definition: smallest_circle.cpp:173
std::vector
STL class.
std::vector::size
T size(T... args)
std::sqrt
T sqrt(T... args)
std::vector::push_back
T push_back(T... args)
Point::y
int y
Point respect to x coordinate.
Definition: line_segment_intersection.cpp:14
std::cout
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
circle
double circle(const std::vector< Point > &P)
Definition: smallest_circle.cpp:87
std::endl
T endl(T... args)
test
void test()
Definition: smallest_circle.cpp:158
Point
Definition: line_segment_intersection.cpp:12
PointInCircle
bool PointInCircle(const std::vector< Point > &P, const Point &Center, double R)
Definition: smallest_circle.cpp:72