Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://TheAlgorithms.github.io/C-Plus-Plus/d0/d01/smallest__circle_8cpp.html below:

TheAlgorithms/C++: others/smallest_circle.cpp File Reference

Loading...

Searching...

No Matches

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

#include <cmath>
#include <iostream>
#include <vector>

Go to the source code of this file.

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

See also

other implementation

Definition in file smallest_circle.cpp.

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

Returns

radius of the circle

Definition at line 87 of file smallest_circle.cpp.

87 {

88 double minR = INFINITY;

89 double R;

92

93

94

95 for (size_t i = 0; i < P.size() - 2; i++)

96

97 for (size_t j = i + 1; j < P.size(); j++)

98

(

k = j + 1;

< P.size();

++) {

100

101

102

103 C.x = -0.5 * ((P[i].y * (P[j].x * P[j].x + P[j].y * P[j].y -

P[

].x * P[

].x - P[

].y * P[

].y) +

P[j].y * (P[

].x * P[

].x + P[

].y * P[

].y -

106 P[i].x * P[i].x - P[i].y * P[i].y) +

P[

].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)) /

(P[i].x * (P[j].y - P[

].y) +

P[j].x * (P[

].y - P[i].y) +

P[

].x * (P[i].y - P[j].y)));

C.

= 0.5 * ((P[i].x * (P[j].x * P[j].x + P[j].y * P[j].y -

P[

].x * P[

].x - P[

].y * P[

].y) +

P[j].x * (P[

].x * P[

].x + P[

].y * P[

].y -

115 P[i].x * P[i].x - P[i].y * P[i].y) +

P[

].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)) /

(P[i].x * (P[j].y - P[

].y) +

P[j].x * (P[

].y - P[i].y) +

P[

].x * (P[i].y - P[j].y)));

125 continue;

126 }

127 if (R <= minR) {

128 minR = R;

129 minC = C;

130 }

131 }

132

133

134 for (size_t i = 0; i < P.size() - 1; i++)

135

136 for (size_t j = i + 1; j < P.size(); j++) {

137

138 C.x = (P[i].x + P[j].x) / 2;

C.

= (P[i].y + P[j].y) / 2;

142 continue;

143 }

144 if (R <= minR) {

145 minR = R;

146 minC = C;

147 }

148 }

std::cout << minC.x <<

<< minC.

<< std::endl;

150 return minR;

151}

double k(double x)

Another test function.

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)

int y

Point respect to x coordinate.

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] A point A [in] B point B

Returns

ditance

Definition at line 37 of file smallest_circle.cpp.

37 {

38 double dx = B.x - A.x;

dy = B.

- A.

;

40 return std::sqrt((dx * dx) + (dy * dy));

41}

Main program

Definition at line 198 of file smallest_circle.cpp.

198 {

200 std::cout << std::endl;

202 std::cout << std::endl;

204 return 0;

205}

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] P set of points to check [in] Center coordinates to centre of the circle [in] R radius of the circle

Returns

True if P lies on or within the circle

False if P lies outside the circle

Definition at line 72 of file smallest_circle.cpp.

72 {

73 for (size_t i = 0; i < P.size(); i++) {

75 return false;

76 }

77 return true;

78}

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

Definition at line 158 of file smallest_circle.cpp.

158 {

159 std::vector<Point> Pv;

Pv.push_back(

(0, 0));

Pv.push_back(

(5, 4));

Pv.push_back(

(1, 3));

Pv.push_back(

(4, 1));

Pv.push_back(

(3, -2));

std::cout <<

(Pv) << std::endl;

166}

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

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

Definition at line 173 of file smallest_circle.cpp.

173 {

174 std::vector<Point> Pv;

Pv.push_back(

(0, 0));

Pv.push_back(

(0, 2));

Pv.push_back(

(2, 2));

Pv.push_back(

(2, 0));

std::cout <<

(Pv) << std::endl;

180}

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

Todo

This test fails

Definition at line 188 of file smallest_circle.cpp.

188 {

189 std::vector<Point> Pv;

Pv.push_back(

(0.5, 1));

Pv.push_back(

(3.5, 3));

Pv.push_back(

(2.5, 0));

Pv.push_back(

(2, 1.5));

std::cout <<

(Pv) << std::endl;

195}

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] A vertex A [in] B vertex B [in] C vertex C

Returns

area of triangle

Definition at line 54 of file smallest_circle.cpp.

54 {

58 double p = (a + b + c) / 2;

59 return std::sqrt(p * (p - a) * (p - b) * (p - c));

60}

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4