Randomized

Smallest Enclosing Disk

Pinterest LinkedIn Tumblr

Minimum covering circle problem is a mathematical problem of computing the smallest circle that contains all of a given set of points in the Euclidean plane.

Write a program to implement smallest enclosing circle.

source Code

package com.dsacode.Algorithm.randomized;
 
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
import java.util.Random;
 
class Circle {
 
    public final Point c;
    public final double r;
 
    public Circle(Point c, double r) {
        this.c = c;
        this.r = r;
    }
 
    public boolean contains(Point p) {
        return c.distance(p) <= r ;
    }
 
    public boolean contains(Collection < Point > ps) {
        for (Point p : ps) {
            if (!contains(p))
                return false;
        }
        return true;
    }
 
    public String toString() {
        return String.format("Circle(x=%g, y=%g, r=%g)", c.x, c.y, r);
    }
 
}
 
class Point {
 
    public final double x;
    public final double y;
 
    public Point(double x, double y) {
        this.x = x;
        this.y = y;
    }
 
    public Point subtract(Point p) {
        return new Point(x - p.x, y - p.y);
    }
 
    public double distance(Point p) {
        return Math.hypot(x - p.x, y - p.y);
    }
 
    public double cross(Point p) {
        return x * p.y - y * p.x;
    }
 
    public double norm() {
        return x * x + y * y;
    }
 
    public String toString() {
        return String.format("Point(%g, %g)", x, y);
    }
 
}
 
public class Smallestenclosingcircle {
    private static Random random = new Random();
 
    public static Circle makeCircle(List < Point > points) {
        List < Point > shuffled = new ArrayList < Point >(points);
        Collections.shuffle(shuffled, new Random());
 
        Circle c = null;
        for (int i = 0; i < shuffled.size(); i++) {
            Point p = shuffled.get(i);
            if (c == null || !c.contains(p))
                c = makeCircleOnePoint(shuffled.subList(0, i + 1), p);
        }
        return c;
    }
 
    private static Circle makeCircleOnePoint(List < Point > points, Point p) {
        Circle c = new Circle(p, 0);
        for (int i = 0; i < points.size(); i++) {
            Point q = points.get(i);
            if (!c.contains(q)) {
                if (c.r == 0)
                    c = makeDiameter(p, q);
                else
                    c = makeCircleTwoPoints(points.subList(0, i + 1), p, q);
            }
        }
        return c;
    }
 
    private static Circle makeCircleTwoPoints(List < Point > points, Point p,
            Point q) {
        Circle temp = makeDiameter(p, q);
        if (temp.contains(points))
            return temp;
 
        Circle left = null;
        Circle right = null;
        for (Point r : points) {
            Point pq = q.subtract(p);
            double cross = pq.cross(r.subtract(p));
            Circle c = makeCircumcircle(p, q, r);
            if (c == null)
                continue;
            else if (cross > 0
                    && (left == null || pq.cross(c.c.subtract(p)) > pq
                            .cross(left.c.subtract(p))))
                left = c;
            else if (cross < 0
                    && (right == null || pq.cross(c.c.subtract(p)) < pq
                            .cross(right.c.subtract(p))))
                right = c;
        }
        return right == null || left != null && left.r <= right.r ? left
                : right;
    }
 
    static Circle makeDiameter(Point a, Point b) {
        return new Circle(new Point((a.x + b.x) / 2, (a.y + b.y) / 2),
                a.distance(b) / 2);
    }
 
    static Circle makeCircumcircle(Point a, Point b, Point c) {
        double d = (a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y)) * 2;
        if (d == 0)
            return null;
        double x = (a.norm() * (b.y - c.y) + b.norm() * (c.y - a.y) + c.norm()
                * (a.y - b.y))
                / d;
        double y = (a.norm() * (c.x - b.x) + b.norm() * (a.x - c.x) + c.norm()
                * (b.x - a.x))
                / d;
        Point p = new Point(x, y);
        return new Circle(p, p.distance(a));
    }
 
    private static List < Point > makeRandomPoints(int n) {
        List < Point > result = new ArrayList < Point >();
        if (random.nextDouble() < 0.2) {
            for (int i = 0; i < n; i++)
                result.add(new Point(random.nextInt(10), random.nextInt(10)));
        } else {
            for (int i = 0; i < n; i++)
                result.add(new Point(random.nextGaussian(), random
                        .nextGaussian()));
        }
        return result;
    }
 
    private static Circle smallestEnclosingCircleNaive(List < Point > points) {
        if (points.size() == 0)
            return null;
        else if (points.size() == 1)
            return new Circle(points.get(0), 0);
 
        Circle best = null;
        for (int i = 0; i < points.size(); i++) {
            for (int j = i + 1; j < points.size(); j++) {
                Circle c = Smallestenclosingcircle.makeDiameter(points.get(i),
                        points.get(j));
                if (c.contains(points) && (best == null || c.r < best.r))
                    best = c;
            }
        }
        if (best != null)
            return best;
 
        for (int i = 0; i < points.size(); i++) {
            for (int j = i + 1; j < points.size(); j++) {
                for (int k = j + 1; k < points.size(); k++) {
                    Circle c = Smallestenclosingcircle.makeCircumcircle(
                            points.get(i), points.get(j), points.get(k));
                    if (c != null && c.contains(points)
                            && (best == null || c.r < best.r))
                        best = c;
                }
            }
        }
        if (best == null)
            throw new AssertionError();
        return best;
    }
 
    public static void main(String args[]) {
        for (int i = 0; i < 3; i++) {
            List < Point > points = makeRandomPoints(random.nextInt(30) + 1);
             
            Circle reference = smallestEnclosingCircleNaive(points);
            Circle actual = Smallestenclosingcircle.makeCircle(points);
 
            if (reference.c.x == actual.c.x)
                System.out.println("X co-ordinate equal");
            if (reference.c.y == actual.c.y)
                System.out.println("Y co-ordinate equal");
 
            if (reference.r == actual.r)
                System.out.println("Radius equal");
 
        }
 
    }
}

Output

X co-ordinate equal
Y co-ordinate equal
Radius equal
X co-ordinate equal
Radius equal
X co-ordinate equal
Radius equal

Algorithm Explanation

Make random points with x and y co-ordinates.
Make circles and two boundary points known.
Returns the smallest circle that encloses all the given points. Runs in expected O(n) time, randomized
If x co-ordinate equal, display the message ‘Y co-ordinate equal’. If Y co-ordinate equal, display the message ‘Y co-ordinate equal’
If radius equal, display the message ‘Radius equal’.

Time Complexity

Best CaseAverage CaseWorst Case
O(n)

Reference

  1. https://en.wikipedia.org/wiki/Smallest-circle_problem
  2. http://www.cs.mcgill.ca/~cs507/projects/1998/jacob/problem.html
  3. http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/CG-Applets/Center/centercli.htm
  4. http://www.cs.uu.nl/docs/vakken/ga/slides4b.pdf

Write A Comment