/*
* 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(); }
}
