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:

Go to the source code of this file.

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

Definition in file smallest_circle.cpp.

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]

P

vector of points

Returns

radius of the circle

Definition at line 87 of file smallest_circle.cpp.

                                         {
    double minR = INFINITY;
    double R;
    Point C;
    Point minC;
 
    /* This code is invalid and does not give correct result for TEST 3 */
    // for each point in the list
    for (size_t i = 0; i < P.size() - 2; i++)
        // for every subsequent point in the list
        for (size_t j = i + 1; j < P.size(); j++)
            // for every subsequent point in the list
            for (size_t k = j + 1; k < P.size(); k++) {
                // here, we now have picked three points from the given set of
                // points that we can use
                // viz., P[i], P[j] and P[k]
                C.x = -0.5 * ((P[i].y * (P[j].x * P[j].x + P[j].y * P[j].y -
                                         P[k].x * P[k].x - P[k].y * P[k].y) +
                               P[j].y * (P[k].x * P[k].x + P[k].y * P[k].y -
                                         P[i].x * P[i].x - P[i].y * P[i].y) +
                               P[k].y * (P[i].x * P[i].x + P[i].y * P[i].y -
                                         P[j].x * P[j].x - P[j].y * P[j].y)) /
                              (P[i].x * (P[j].y - P[k].y) +
                               P[j].x * (P[k].y - P[i].y) +
                               P[k].x * (P[i].y - P[j].y)));
                C.y = 0.5 * ((P[i].x * (P[j].x * P[j].x + P[j].y * P[j].y -
                                        P[k].x * P[k].x - P[k].y * P[k].y) +
                              P[j].x * (P[k].x * P[k].x + P[k].y * P[k].y -
                                        P[i].x * P[i].x - P[i].y * P[i].y) +
                              P[k].x * (P[i].x * P[i].x + P[i].y * P[i].y -
                                        P[j].x * P[j].x - P[j].y * P[j].y)) /
                             (P[i].x * (P[j].y - P[k].y) +
                              P[j].x * (P[k].y - P[i].y) +
                              P[k].x * (P[i].y - P[j].y)));
                R = (LenghtLine(P[i], P[j]) * LenghtLine(P[j], P[k]) *
                     LenghtLine(P[k], P[i])) /
                    (4 * TriangleArea(P[i], P[j], P[k]));
                if (!PointInCircle(P, C, R)) {
                    continue;
                }
                if (R <= minR) {
                    minR = R;
                    minC = C;
                }
            }
 
    // for each point in the list
    for (size_t i = 0; i < P.size() - 1; i++)
        // for every subsequent point in the list
        for (size_t j = i + 1; j < P.size(); j++) {
            // check for diameterically opposite points
            C.x = (P[i].x + P[j].x) / 2;
            C.y = (P[i].y + P[j].y) / 2;
            R = LenghtLine(C, P[i]);
            if (!PointInCircle(P, C, R)) {
                continue;
            }
            if (R <= minR) {
                minR = R;
                minC = C;
            }
        }
    std::cout << minC.x << " " << minC.y << std::endl;
    return minR;
}

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

Returns

ditance

Definition at line 37 of file smallest_circle.cpp.

                                                  {
    double dx = B.x - A.x;
    double dy = B.y - A.y;
    return std::sqrt((dx * dx) + (dy * dy));
}

main()

int main

(

void

)

Main program

Definition at line 198 of file smallest_circle.cpp.

           {
    test();
    std::cout << std::endl;
    test2();
    std::cout << std::endl;
    test3();
    return 0;
}

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

                                                                             {
    for (size_t i = 0; i < P.size(); i++) {
        if (LenghtLine(P[i], Center) > R)
            return false;
    }
    return true;
}

test()

void test

(

)

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.

            {
    std::vector<Point> Pv;
    Pv.push_back(Point(0, 0));
    Pv.push_back(Point(5, 4));
    Pv.push_back(Point(1, 3));
    Pv.push_back(Point(4, 1));
    Pv.push_back(Point(3, -2));
    std::cout << circle(Pv) << std::endl;
}

test2()

void test2

(

)

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.

             {
    std::vector<Point> Pv;
    Pv.push_back(Point(0, 0));
    Pv.push_back(Point(0, 2));
    Pv.push_back(Point(2, 2));
    Pv.push_back(Point(2, 0));
    std::cout << circle(Pv) << std::endl;
}

test3()

void test3

(

)

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.

             {
    std::vector<Point> Pv;
    Pv.push_back(Point(0.5, 1));
    Pv.push_back(Point(3.5, 3));
    Pv.push_back(Point(2.5, 0));
    Pv.push_back(Point(2, 1.5));
    std::cout << circle(Pv) << std::endl;
}

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

Returns

area of triangle

Definition at line 54 of file smallest_circle.cpp.

                                                                    {
    double a = LenghtLine(A, B);
    double b = LenghtLine(B, C);
    double c = LenghtLine(C, A);
    double p = (a + b + c) / 2;
    return std::sqrt(p * (p - a) * (p - b) * (p - c));
}