Pages

Points on a Circle Solution

/*
 *  A problem sometimes known as Moser's circle problem asks to determine the number of
 *  pieces into which a circle is divided if n points on its circumference are joined by
 *  chords with no three internally concurrent.
 *
 *                           -- http://mathworld.wolfram.com/CircleDivisionbyChords.html
 */

import java.util.Comparator;
import java.util.SortedSet;
import java.util.TreeSet;
import java.util.List;
import java.util.ArrayList;

/****************/
/* Main Program */
/****************/

/**
 * CircleDivisionByRandomChords generates random points on the circumference of a
 * circle and prints information about the points and the chords that can be formed by
 * connecting the points.
 */
public class CircleDivisionByRandomChords
{
    /**
     * 0. Process the command-line arguments.
     * 1. Generate and label an ordered list of n random points on a the circumference
     *    of a circle that has a radius r and is centered at the point (x, y).
     * 2. Generate an ordered list of all possible chords that can be formed by
     *    connecting any two of the points.
     * 3. Print the polar and Cartesian coordinates for the points in their polar
     *    coordinate ordering, which is defined as follows: a point with a smaller
     *    radius appears before a point with a significantly larger radius; if the
     *    radius values are equal or nearly equal, then a point with a smaller angle
     *    appears before a point with a significantly larger angle. Angles are values
     *    greater than or equal to 0 and less than 2 * Pi.
     * 4. Print the chords in order by chord length, shortest to longest.
     */
    public static void main(String[] args)
    {
        final int argCount = args.length;
        final int n = argCount > 0 ? Integer.parseInt(args[0]) : 0;
        final Double r = argCount > 1 ? Double.parseDouble(args[1]) : 1.0;
        final Double x = argCount > 2 ? Double.parseDouble(args[2]) : 0;
        final Double y = argCount > 3 ? Double.parseDouble(args[3]) : 0;
        final XY center = new CartesianCoords(x, y);
        
        SortedSet<PointInAPlane> points = PointsOnACircle.makeRandom(n, r, center);
        SortedSet<Chord> chords = Chords.fromPointsOnACircle(points);
        Points.printPolarCoordinates(points);
        Points.printCartesianCoordinates(points);
        Chords.printChords(chords);                        
    }
}

/*************/
/* Utilities */
/*************/

class PointsOnACircle
{
    private static XY randomCoords(Double radius, XY center)
    {
        // TO DO: Set polarCoords equal to a reference to a Polar object that represents a
        // random point on a circle that is centered on the origin.

        final Polar polarCoords = new PolarCoords(radius, 2 * Math.PI * Math.random());

        // TO DO: Set xyCoords equal to a reference to an XY object that is the Cartesian
        // equivalent of polarCoords.

        final XY xyCoords = polarCoords.toXY();

        // TO DO: Return a reference to an XY object that is the sum of xyCoords and center.

        return Coordinates.add(xyCoords, center);
    }
    private static void labelPoints(SortedSet<PointInAPlane> points)
    {
        int pointNumber = 0;
        for (PointInAPlane point : points)
            point.setLabel("p" + ++pointNumber);
    }
    public static SortedSet<PointInAPlane> makeRandom(int n, Double radius, XY center)
    {
        SortedSet<PointInAPlane> points =
            new TreeSet<PointInAPlane>(new OrderedPairOfNumbersComparator());

        while (n-- > 0)
        {
            XY xy = randomCoords(radius, center);
            points.add(new Point2D(xy.toPolar()));
        }
        labelPoints(points);
        return points;
    }
}

class Points
{
    public static void printPolarCoordinates(SortedSet<PointInAPlane> points)
    {
        System.out.println("Polar Coordinates\n");
        for (PointInAPlane point : points)
            System.out.println(point.label() + ": " + point.toPolar().toString());
    }
    public static void printCartesianCoordinates(SortedSet<PointInAPlane> points)
    {
        System.out.println("\nCartesian Coordinates\n");
        for (PointInAPlane point : points)
            System.out.println(point.label() + ": " + point.toXY().toString());
    }
}

class Chords
{
    public static SortedSet<Chord> fromPointsOnACircle(SortedSet<PointInAPlane> points)
    {
        SortedSet<Chord> chords = new TreeSet<Chord>(new LengthComparator());
        for (PointInAPlane p1 : points)
            for (PointInAPlane p2 : points)
                if (p1 != p2)
                    chords.add(new PairOfPointsOnACircle(p1, p2));
        return chords;
    }
    public static void printChords(SortedSet<Chord> chords)
    {
        System.out.println("\nChord Lengths\n");
        for (Chord chord : chords)
            System.out.println(chord.label() + ": " + chord.length());
    }
}

class Coordinates
{
    public static XY add(XY coord1, XY coord2)
    {
        return new CartesianCoords(coord1.x() + coord2.x(), coord1.y() + coord2.y());
    }
}

class Difference
{
    public static boolean isSignificant(double d1, double d2)
    {
        return Difference.isSignificant(d1, d2, 1e-14);
    }
    public static boolean isSignificant(double d1, double d2, double epsilon)
    {
        // TO DO: If the absolute value of d2 - d1 is greater than epsilon
        // then return true; otherwise, return false.

        return Math.abs(d2 - d1) > epsilon;
    }
}

/*********************/
/* Type Declarations */
/*********************/

interface HasLength
{
    public Double length();
}

interface HasLabel
{
    public String label();
}

interface IsLabelable
{
    public void setLabel(String label);
}

interface OrderedPairOfNumbers
{
    public Double first();
    public Double second();
}

interface XY extends OrderedPairOfNumbers
{
    public Double x();
    public Double y();
    public Polar toPolar();
}

interface Polar extends OrderedPairOfNumbers
{
    public Double radius();
    public Double angle();
    public XY toXY();
}

interface PointInAPlane extends XY, Polar, HasLabel, IsLabelable
{
}

interface Chord extends HasLength, HasLabel
{
}

/********************/
/* Type Definitions */
/********************/

/**
 * A comparator that can be used to sort objects of type OrderedPairOfNumbers.
 */
class OrderedPairOfNumbersComparator implements Comparator<OrderedPairOfNumbers>
{
    public int compare(OrderedPairOfNumbers pair1, OrderedPairOfNumbers pair2)
    {
        Double pair1First = pair1.first();
        Double pair2First = pair2.first();     
        int compareResult = pair1First.compareTo(pair2First);
        if (compareResult == 0 || !Difference.isSignificant(pair1First, pair2First))
        {
            Double pair1Second = pair1.second();
            Double pair2Second = pair2.second();
            compareResult = pair1Second.compareTo(pair2Second);
            if (compareResult != 0 && !Difference.isSignificant(pair1Second, pair2Second))
                compareResult = 0;
        }
        return compareResult;
    }
}

/**
 * A comparator that can be used to sort objects that implement HasLength.
 */
class LengthComparator implements Comparator<HasLength>
{
    public int compare(HasLength object1, HasLength object2)
    {
        return object1.length().compareTo(object2.length());
    }
}

/**
 * A sortable ordered pair of numbers of type Double.
 */
abstract class BasicOrderedPairOfNumbers implements OrderedPairOfNumbers
{    
    private final Double first, second;

    public BasicOrderedPairOfNumbers(Double first, Double second)
    {
        this.first = first;
        this.second = second;
    }
    public Double first() { return first; }
    public Double second() { return second; }
    public String toString()
    {
        // TO DO: Return a string of the form (a, b) where a and b are the
        // first and second coordinate values respectively.

        return "(" + first() + ", " + second() + ")";
    }
}

/**
 * An ordered pair of Cartesian coordinates.
 */
class CartesianCoords extends BasicOrderedPairOfNumbers implements XY
{
    public CartesianCoords(Double x, Double y)
    {
        // TO DO: Pass the values of x and y to the superclass's constructor method.

        super(x, y);
    }
    public Double x() { return first(); }
    public Double y() { return second(); }
    public Polar toPolar()
    {
        Double x = this.x(), y = this.y();

        // TO DO: Compute the distance between the origin (0, 0) and the point (x, y).
        // This is the radius of the corresponding polar coordinates.

        Double radius = Math.sqrt(x*x + y*y);

        // TO DO: Compute the multi-valued inverse tangent (atan2) of y and x. This is the
        // angle of the corresponding polar coordinates.

        Double angle = Math.atan2(y, x);

        return new PolarCoords(radius, angle);
    }
}

/**
 * An ordered pair of polar coordinates.
 */
class PolarCoords extends BasicOrderedPairOfNumbers implements Polar
{
    public PolarCoords(Double r, Double a)
    {
        // Call the superclass's constructor. Pass the radius value and a possibly
        // modified angle value. Note that the angle conversion must be done inline.
        // It can't be performed using statements that precede the call to the
        // superclass's constructor, because the superclass constructor call must be
        // executed first, before any other statements in this constructor method
        // are executed.
        //
        // TO DO: If a is less than 0, then use the mod (%) operator to produce a
        // value that is greater than -2 * Pi, add 2 * Pi to that value, and pass
        // the result to the superclass's constructor. If a is not less than 0, then
        // use the mod operator to produce a value that is less than 2 * Pi (and
        // greater than 0) and pass that value to the superclass's constructor.

        super(r, a < 0 ? (a % (2*Math.PI)) + (2*Math.PI) : (a % (2*Math.PI)) );
    }
    public Double radius() { return first(); }
    public Double angle() { return second(); }
    public XY toXY()
    {
        // TO DO: x-coordinate = radius * cos(angle)

        Double x = this.radius() * Math.cos(this.angle());

        // TO DO: y-coordinate = radius * sin(angle)

        Double y = this.radius() * Math.sin(this.angle());

        return new CartesianCoords(x, y);
    }
}

/**
 * A point in two-dimensional space.
 */
class Point2D extends BasicOrderedPairOfNumbers implements PointInAPlane
{
    private final XY xyCoords;
    private final Polar polarCoords;
    private String label = null;

    public Point2D(Point2D p)
    {
        super(p.first(), p.second());
        this.xyCoords = p.xyCoords;
        this.polarCoords = p.polarCoords;
    }
    public Point2D(XY xyCoords)
    {
        super(xyCoords.first(), xyCoords.second());
        this.xyCoords = xyCoords;
        this.polarCoords = xyCoords.toPolar();
    }
    public Point2D(Polar polarCoords)
    {
        super(polarCoords.first(), polarCoords.second());
        this.polarCoords = polarCoords;
        this.xyCoords = polarCoords.toXY();
    }
    public void setLabel(String label) { this.label = label; }
    public String label() { return label; }
    public Double x() { return xyCoords.x(); }
    public Double y() { return xyCoords.y(); }
    public Double radius() { return polarCoords.radius(); }
    public Double angle() { return polarCoords.angle(); }
    public XY toXY() { return xyCoords; }
    public Polar toPolar() { return polarCoords; }
}

/**
 * A line segment connecting two points on a circle.
 */
class PairOfPointsOnACircle implements Chord
{
    private final PointInAPlane p1, p2;
    private final Double length; 
    public PairOfPointsOnACircle(PointInAPlane p1, PointInAPlane p2)
    {
        this.p1 = p1;
        this.p2 = p2;
        Double dx = p2.x() - p1.x();
        Double dy = p2.y() - p1.y();

        // TO DO: Use dx, dy, and the distance formula to compute length.

        this.length = Math.sqrt(dx*dx + dy*dy);
    }
    public Double length() { return this.length; }
    public String label() { return p1.label() + "-" + p2.label(); }
    public String toString() { return this.label(); }
}