I have a computer science test on Monday which will have a very
similar question to the one below. If you could please have an answer
before Sunday, I would greatly appreciate it!! I am completely new to
java and want to see the code for this so that I can study and
understand it. The question is:

Create a Triangle class that implements all of the missing code from
the template below (fill in the missing code):

public class Triangle
{
private Coordinate a, b, c;

//default constructor: should generate random Coordinates
public Triangle();

//standard constructor
public Triangle(Coordinate newA, Coordinate newB, Coordinate newC);

//accessors
public Coordinate getVertexA();
public Coordinate getVertexB();
public Coordinate getVertexC();

public double getSideA();
public double getSideB();
public double getSideC();

public double getAngleA();
public double getAngleB();
public double getAngleC();

public boolean isValid();
public boolean isScalene();
public boolean isIsosceles();
public boolean isEquilateral();

public double getPerimeter();
public double getArea();

public String toString();
public boolean equals(Object o);

public boolean contains(Coordinate t);
public Circle getCircumcircle();
public Circle getIncircle();
}

That's all for the question.

Some auxiliary classes you may want to use to help you out:

public class Coordinate
{
//state variable(s)
private double x;
private double y;

//constructor function(s)
public Coordinate();
public Coordinate(double newX, double newY);
public Coordinate (Coordinate toBeCopied);

//accessor function(s)
public double getX();
public double getY();

//utility function(s)
public double distanceTo(Coordinate target)
{
double deltaX = x - target.getX();
double deltaY = y - target.getY();
double hypotSquared = (deltaX * deltaX) + (deltaY * deltaY);
return (Math.sqrt(hypotSquared));
}

public String toString()
{return ("(" + x + "," + y + ")")}
}

public class Circle
{
private Coordinate origin;
private double radius;

public Circle();
public Circle(Coordinate newOrigin, double newRadius);
}
 
This is NOT a test question, but for practice purposes only!

---

Clarification of Question by alex1977-ga on 24 Nov 2006 08:38 PST

I need this before Sunday, if at all possible.

---

Clarification of Question by alex1977-ga on 25 Nov 2006 07:30 PST

The question has been locked for nearly 24 hours. Is somebody working on it?

---

Request for Question Clarification by leapinglizard-ga on 25 Nov 2006 08:40 PST

I have the lock now. I'm working on your question and will post my
answer by tomorrow morning.

leapinglizard

---

Clarification of Question by alex1977-ga on 25 Nov 2006 09:01 PST

Thank you, leapinglizard, I really appreciate it!

---

Clarification of Question by alex1977-ga on 26 Nov 2006 08:50 PST

Leapinglizard, 

Sorry to bother you, but do you think you'll have the answer soon? I
really need it by today!
Thanks,

alex1977-ga

Dear alex1977,


Many important properties of triangles are described on the following
page.

MathWorld: Triangle
http://mathworld.wolfram.com/Triangle.html


In order to determine whether a triangle includes a point, it is helpful
to know its signed area, which can be calculated by means of equation
17 on the following page.

MathWorld: Triangle Area
http://mathworld.wolfram.com/TriangleArea.html


The signed area of a triangle is trivially converted into its orientation,
which can then be used to decide point inclusion, as demonstrated by
the method Triangle::contains() in the following C++ code.

Carlos Moreno: Triangle.h
http://www.mochima.com/articles/cuj_geometry_article/triangle_h.html

Carlos Moreno: Triangle.cpp
http://www.mochima.com/articles/cuj_geometry_article/triangle_cpp.html


The circumcircle and incircle are commonly expressed in trilinear
coordinates, which are described on the following page. The conversion
of trilinear to Cartesian coordinates is given by equations 12 through 15.

MathWorld: Trilinear Coordinates
http://mathworld.wolfram.com/TrilinearCoordinates.html


The Cartesian coordinates thus obtained are relative to the triangle's
incenter. Hence, the incenter will always have coordinates (0.0, 0.0). The
inradius can be calculated by various formulae, such as number 2 on the
following page.

Mathworld: Inradius
http://mathworld.wolfram.com/Inradius.html


The trilinear coordinates of the circumcenter and the magnitude of the
circumradius are discussed on the following pages.

Mathworld: Circumcenter
http://mathworld.wolfram.com/Circumcenter.html

Mathworld: Circumradius
http://mathworld.wolfram.com/Circumradius.html

I have included further explanations in the comments of the Java code
below. After compiling it, you can execute this program repeatedly to
exercise the geometric functions on randomly generated triangles.

You can download the code from the following location.

Triangle.java
http://plg.uwaterloo.ca/~mlaszlo/answers/Triangle.java


Regards,

leapinglizard




import java.lang.*;
import java.util.*;
import java.io.*;


// auxiliary class to store coordinates of each vertex
class Coordinate {
    // state data for a coordinate pair (x, y)
    private double x;
    private double y;

    // construct a point with random values in the range [-10.0, +10.0]
    public Coordinate() {
        x = (Math.random() - 0.5) * 20.0;
        y = (Math.random() - 0.5) * 20.0;
    }

    // constructs a point from specified coordinate values
    public Coordinate(double newX, double newY) {
        x = newX;
        y = newY;
    }

    // copy constructor
    public Coordinate(Coordinate toBeCopied) {
        x = toBeCopied.getX();
        y = toBeCopied.getY();
    }

    // access x value
    public double getX() {
        return x;
    }

    // access y value
    public double getY() {
        return y;
    }

    // calculates distance between target and this point
    public double distanceTo(Coordinate target) {
        double deltaX = x - target.getX();
        double deltaY = y - target.getY();
        double hypotSquared = (deltaX * deltaX) + (deltaY * deltaY);
        return (Math.sqrt(hypotSquared));
    }

    // pretty-prints the coordinate pair
    public String toString() {
        return ("(" + x + ", " + y + ")");
    }
}


// auxiliary class to help with circumcircle and incircle calculations
class Circle {
    // state data for a circle of given radius centered on a given origin
    private Coordinate origin;
    private double radius;

    public Coordinate getOrigin() {
        return origin;
    }

    public double getRadius() {
        return radius;
    }

    // constructs a unit circle with a random origin
    public Circle() {
        origin = new Coordinate();
        radius = 1.0;
    }

    // copy constructor
    public Circle(Coordinate newOrigin, double newRadius) {
        origin = newOrigin;
        radius = newRadius;
    }

}
    

public class Triangle {
    // state data for a triangle with vertices a, b, c
    private Coordinate a, b, c;

    // constructs a triangle with random vertices
    public Triangle() {
        a = new Coordinate();
        b = new Coordinate();
        c = new Coordinate();
    }
    
    // constructs a triangle with the given vertices
    public Triangle(Coordinate newA, Coordinate newB, Coordinate newC) {
        a = newA;
        b = newB;
        c = newC;
    }

    // access each vertex
    public Coordinate getVertexA() {
        return a;
    }
    public Coordinate getVertexB() {
        return b;
    }
    public Coordinate getVertexC() {
        return c; 
    }

    // calculate the length of the side opposite vertex a 
    public double getSideA() {
        // get the distance between vertices b and c
        double length = b.distanceTo(c);
        return length;
    }

    // calculate the length of the side opposite vertex b
    public double getSideB() {
        // get the distance between vertices a and c
        double length = a.distanceTo(c);
        return length;
    } 
    
    // calculate the length of the side opposite vertex c
    public double getSideC() {
        // get the distance between vertices a and b
        double length = a.distanceTo(b);
        return length;
    }

    // calculate the angle at vertex a
    public double getAngleA() {
        // get the length of each side
        double as = getSideA(), bs = getSideB(), cs = getSideC();
        // apply the law of cosines
        double angle = Math.acos((bs*bs + cs*cs - as*as) / (2*bs*cs));
        return angle;
    }
    
    // calculate the angle at vertex b
    public double getAngleB() {
        // get the length of each side
        double as = getSideA(), bs = getSideB(), cs = getSideC();
        // apply the law of cosines
        double angle = Math.acos((as*as + cs*cs - bs*bs) / (2*as*cs));
        return angle;
    }

    // calculate the angle at vertex c
    public double getAngleC() {
        // get the length of each side
        double as = getSideA(), bs = getSideB(), cs = getSideC();
        // apply the law of cosines
        double angle = Math.acos((as*as + bs*bs - cs*cs) / (2*as*bs));
        return angle;
    }

    // check whether no side is longer than the other two sides put together
    public boolean isValid() {
        // get the length of each side
        double as = getSideA(), bs = getSideB(), cs = getSideC();
        if (as > (bs + cs))
            return false;
        if (bs > (as + cs))
            return false;
        if (cs > (as + bs))
            return false;
        return true;
    }

    // check whether all three sides differ in length
    public boolean isScalene() {
        // get the length of each side
        double as = getSideA(), bs = getSideB(), cs = getSideC();
        if (as == bs)
            return false;  // not scalene if two sides are equal in length
        if (as == cs)
            return false;
        if (bs == cs)
            return false;
        return true;
    }

    // check whether two sides are equal in length
    public boolean isIsosceles() {
        // get the length of each side
        double as = getSideA(), bs = getSideB(), cs = getSideC();
        if (as == bs)
            return true;  // isosceles if two sides are equal in length
        if (as == cs)
            return true;
        if (bs == cs)
            return true;
        return false;
    }

    // check whether all three sides are equal in length
    public boolean isEquilateral() {
        // get the length of each side
        double as = getSideA(), bs = getSideB(), cs = getSideC();
        if (as != bs)
            return false;  // not equilateral if two sides differ in length
        if (as != cs)
            return false;
        if (bs != cs)
            return false;
        return true;
    }

    // calculate the sum of the lengths of the sides
    public double getPerimeter() {
        // get the length of each side
        double as = getSideA(), bs = getSideB(), cs = getSideC();
        return (as + bs + cs);
    }
    
    // calculate the signed area
    double getSignedArea() {
        double signedArea = 0.5 * (a.getX() * (b.getY() - c.getY()) +
                                   b.getX() * (c.getY() - a.getY()) +
                                   c.getX() * (a.getY() - b.getY()));
        return signedArea;
    }

    // calculate the absolute area
    public double getArea() {
        return Math.abs(getSignedArea());
    }

    // determine orientation based on the signed area 
    public int getOrientation() {
        double signedArea = getSignedArea();
        if (signedArea > 0.0)
            return 1;
        if (signedArea < 0.0)
            return -1;
        return 0;
    }

    // pretty-print the coordinates inside square brackets
    public String toString() { 
        return ("["+a+",\n "+b+",\n "+c+"]");
    }

    // do the coordinates of the vertices a, b, c match up in order?
    // note that we are not checking all 6 orderings of a, b, c
    public boolean equals(Object o) {
        Triangle triangle = (Triangle) o;
        if (triangle.getVertexA() != a)
            return false;
        if (triangle.getVertexB() != b)
            return false;
        if (triangle.getVertexC() != c)
            return false;
        return true;
    }

    // check whether a given point falls inside the triangle
    public boolean contains(Coordinate p) {
        int orientation = (new Triangle(b, c, p)).getOrientation();
        if ((new Triangle(a, b, p)).getOrientation() != orientation)
            return false;
        if (orientation != (new Triangle(b, c, p)).getOrientation())
            return false;
        return true;
    }
    
    // converts trilinear coordinates to Cartesian coordinates relative
    // to the incenter; thus, the incenter has coordinates (0.0, 0.0)
    public Coordinate toCartesian(double alpha, double beta, double gamma) {
        double area = getArea();
        double as = getSideA(), bs = getSideB(), cs = getSideC();
        double r = 2 * area / (as + bs + cs);
        double k = 2 * area / (as*alpha + bs*beta + cs*gamma);
        double cosC = Math.cos(getAngleC()), sinC = Math.sin(getAngleC());
        double x = (k*beta - r + (k*alpha - r)*cosC) / sinC;
        double y = k*alpha - r;
        return new Coordinate(x, y);
    }

    // calculates the circumradius
    public Circle getCircumcircle() {
        double cosA = Math.cos(getAngleA());
        double cosB = Math.cos(getAngleB());
        double cosC = Math.cos(getAngleC());
        Coordinate center = toCartesian(cosA, cosB, cosC);
        double as = getSideA(), bs = getSideB(), cs = getSideC();
        double s = 0.5 * (as + bs + cs);
        double radius = (as * bs * cs) / (4 * Math.sqrt(
            s * (as + bs - s) * (as + cs - s) * (bs + cs - s)));
        return new Circle(center, radius);
    }

    // calculates the inradius
    public Circle getIncircle() {
        Coordinate center = toCartesian(1.0, 1.0, 1.0);
        double as = getSideA(), bs = getSideB(), cs = getSideC();
        double semiperimeter = 0.5 * (as + bs + cs);
        double radius = getArea() / semiperimeter;
        return new Circle(center, radius);
    }


    // randomly generate a triangle and test various functions
    public static void main(String[] argv) {
        // make a new triangle and print its vertex coordinates
        Triangle triangle = new Triangle();
        System.out.println(triangle);

        // is it equal to a copy of itself?
        Coordinate av = triangle.getVertexA();
        Coordinate bv = triangle.getVertexB();
        Coordinate cv = triangle.getVertexC();
        Triangle other_triangle = new Triangle(av, bv, cv);
        if (triangle.equals(other_triangle))
            System.out.println("-- is equal to "+other_triangle);
        else
            System.out.println("-- is not equal to "+other_triangle);

        // is it equal to another random triangle?
        other_triangle = new Triangle();
        if (triangle.equals(other_triangle))
            System.out.println("-- is equal to "+other_triangle);
        else
            System.out.println("-- is not equal to "+other_triangle);

        // calculate the absolute area
        System.out.println("-- area = "+triangle.getArea());

        // does a random point fall inside it?
        Coordinate p = new Coordinate();
        if (triangle.contains(p))
            System.out.println("-- includes the point "+p);
        else
            System.out.println("-- does not include the point "+p);

        // calculate the circumradius
        Circle circle = triangle.getCircumcircle();
        System.out.println("-- circumradius is "+circle.getRadius());

        // calculate the inradius
        circle = triangle.getIncircle();
        System.out.println("-- inradius is "+circle.getRadius());
    }
}

---

Request for Answer Clarification by alex1977-ga on 28 Nov 2006 13:57 PST

I was just wondering if you could please clarify the process of what
you're doing with the circumcircle, incircle, and public boolean
contains(Coordinate p) calculations. Thanks again for answering the
question!

---

Clarification of Answer by leapinglizard-ga on 29 Nov 2006 09:38 PST

Thank you for the tip. I hope your test went well!

The circumcircle and incircle calculations are direct implementations
of formulae I found on MathWorld. The circumcenter, for example, is
expressed as

  cos A : cos B : cos C

in trilinear coordinates, which are described on the following page.

MathWorld: Trilinear Coordinates
http://mathworld.wolfram.com/TrilinearCoordinates.html

Equations 12 and 13 on that page give the conversion from trilinear to
Cartesian coordinates. Several formulae for the circumradius are then
given on the following page.

MathWorld: Circumradius
http://mathworld.wolfram.com/Circumradius.html

There are analogous definitions for the incenter and inradius.

To implement the contains() method, I read Carlos Moreno's C++ code
and translated it into Java, which was very straightforward given the
close similarity between the languages.

Carlos Moreno: triangle.h
http://www.mochima.com/articles/cuj_geometry_article/triangle_h.html

Carlos Moreno: triangle.cpp
http://www.mochima.com/articles/cuj_geometry_article/triangle_cpp.html

Moreno's contains() function calls turn(), which is just a wrapper for
orientation(), which is trivially derived from signed_area().


leapinglizard

Thank you, leapinglizard, your answer was excellent! I'm sorry it took
a while to give you this rating; I've been very sick the last couple
of days! Thanks again!

alex1977

alex1977,

Here's an alternate method for implementing your "public boolean
contains(Coordinate t)" that you might find easier to understand (I
don't know, I didn't make an effort to understand leapinglizard's).


The code below follows the following principle:


              a
             / \    . d
            /   \   
           /     \   
        b /_______\ c

If Coordinate d is outside of the triangle, then at least one of the
angles formed with Coordinate d (and two of the Coordinates of the
Triangle) will be larger than it should be. In other words, in the
above picture, because Coordinate d is outside of the Triangle, angle
B-A-D will be larger than B-A-C, and as you can see, angle B-C-D is
larger than B-C-A also.

              a
             / \
            /   \
           / . d \
        b /_______\ c

If Coordinate d is inside the Triangle, all angles made with
Coordinate d will be less than their respective angles. Observe (we
test all 6 cases):

1) Angle A-C-D is less than A-C-B
2) angle A-D-B is less than A-C-B
3) angle B-C-D is less than angle B-C-A
4) angle B-A-D is less than angle B-A-C
5) angle C-A-D is less than angle C-A-B
6) angle C-B-D is less than angle C-B-A

And here's the code I used:

// gets the angle at the first vertex between the second two vertices
public double getAngle(Coordinate vertexA, Coordinate vertexB, Coordinate vertexC)
{
	// store the lengths of the sides to make it easier to read
	double lengthB = getLength(vertexA, vertexB);
	double lengthC = getLength(vertexA, vertexC);
	double lengthA = getLength(vertexB, vertexC);
		
	// return the angle
	return ((180 / PI) * Math.acos((Math.pow(lengthB, 2) +
Math.pow(lengthC, 2) - Math.pow(lengthA, 2)) / (2 * lengthB *
lengthC)));
}

/* we'll test this by comparing the angles between the
* points: if a point is outside the triangle, it will
* create an angle with a vertex wider than it should be
*/
public boolean contains(Coordinate t)
{
	if(getAngleA() < getAngle(a, b, t) || getAngleA() < getAngle(a, c, t))
	{
		return false;
	}
		
	if(getAngleB() < getAngle(b, a, t) || getAngleB() < getAngle(b, c, t))
	{
		return false;
	}
		
	if(getAngleC() < getAngle(c, a, t) || getAngleC() < getAngle(c, b, t))
	{
		return false;
	}
		
	return true;
}

Best regards,

Sean

Sorry, I made a mistake:

2) angle A-D-B is less than A-C-B

should be

2) angle A-B-D is less than A-B-C