## Triangle Trilemma

### January 18, 2013

The distance between two points p and q, from the Pythagorean Theorem, is $\sqrt{(p_x - q_x)^2 + (p_y - q_y)^2)}$, but we ignore the square root calculation and use formulas that work with the squares of the sides, which are sorted in ascending order for the area calculation. The first clause of the outer cond calculates the area of the triangle (actually, just a portion of the formula for the area, but enough to know if it is zero or positive) and determines that three points do not form a triangle if the area is zero. The second clause of the outer cond will never be satisfied, as there are no integer points in two-dimensional space that can form an equilateral triangle (there is a square root of three involved in the length of the sides, and since the square root of three is irrational, there can be no equilateral triangle). Otherwise, the output string is constructed of two pieces. The triangle is isoceles if two sides are the same or scalene otherwise. The inner cond classifies the triangle as acute, obtuse or right based on criteria found at MathWorld. Here’s the classifier:

(define (tri x y z)   (define (square x) (* x x))   (define (norm x y)     (+ (square (- (car x) (car y)))        (square (- (cadr x) (cadr y)))))   (let* ((sq-sides (sort < (list (norm x y) (norm y z) (norm x z))))          (a (car sq-sides)) (b (cadr sq-sides)) (c (caddr sq-sides)))     (cond ((zero? (- (* a c) (square (/ (+ a c (- b)) 2))))             "not a triangle")           ((= a b c) "equilateral triangle")           (else (string-append                   (if (or (= a b) (= b c)) "isoceles" "scalene")                   (cond ((and (< c (+ a b)) (< a (+ b c)) (< b (+ a c)))                           " acute triangle")                         ((or (< (+ a b) c) (< (+ b c) a) (< (+ a c) b))                           " obtuse triangle")                         (else " right triangle")))))))

You can run the program at http://programmingpraxis.codepad.org/Bbfn4bYK, where you can also see several sample calculations.

Pages: 1 2

### 10 Responses to “Triangle Trilemma”

1. […] Question is from here: […]

2. Jussi Piitulainen said

Someone posted complex-arithmetic solutions to an earlier problem where there were four points. I found that interesting. Here is an attempt to determine the three angles, in increasing order, that works by translating and rotating the triangle with complex arithmetic so that each point in turn is at the origin, one side extends to the right, and then the angle is the angle of the polar form of the remaining point.

(define (ang x y z) (abs (angle (/ (- x y) (- x z))))) ;angle at point x
(define (med a b c) (max (min a b) (min a c) (min b c))) ;median of three

(define (angles x y z) ;points as complex numbers
(let ((a (ang x y z)) (b (ang y x z)) (c (ang z y x))) ;angles
(list (min a b c) (med a b c) (max a b c)))) ;increasing angles


One could then compare the angles (all within epsilon of each other, or first two, or last two, or not), or compare the third angle to a straight angle (within epsilon, more than epsilon smaller, or larger), to arrive at the requested classifications.

3. Jussi Piitulainen said

Here’s what I used to test my code: construct various known triangles in different positions and compute their angles. The code appeared to work. The errors, where not 0, were on the order of 10 to the power -16, which is what floating point does. (Complex division was buggy in an ancient, year 2003, version of Guile; a newer Guile worked beautifully.) (I paid little attention to non-triangles. These would either crash arithmetically or produce zero or straight angles.)

;;; Expected results e<k> for <k> = 1, ..., 6
(define tau (* 2 (angle -1))) ;right angle = tau/4
(define e1 (list (/ tau 8) (/ tau 8) (/ tau 4)))
(define e2 (list (/ tau 6) (/ tau 6) (/ tau 6)))
(define e3 (list (/ tau 12) (/ tau 6) (/ tau 4)))
(define e4 (list (/ tau 8) (/ tau 6) (* tau (+ 1/12 1/8))))
(define e5 (list (/ tau 12) (/ tau 12) (/ tau 3)))
(define e6 (list (/ tau 12) (/ tau 8) (* tau (+ 1/6 1/8))))

;;; Expect (apply angles t<k>) = e<k>
(define t1 (list 0+0i 3+0i 0+3i))
(define t2 (list -1+0i 1+0i (make-rectangular 0 (sqrt 3))))
(define t3 (list -1+0i 0+0i (make-rectangular 0 (sqrt 3))))
(define t4 (list -1+0i (make-rectangular 0 (sqrt 3))
(make-rectangular (sqrt 3) 0)))
(define t5 (list (make-rectangular 0 (sqrt 3))
(make-rectangular 0 (- (sqrt 3))) -1+0i))
(define t6 (list (make-rectangular (- (sqrt 3)) -1) 0+0i 1-1i))

;;; Expect (apply angles u<k>) = (apply angles t<k>) = e<k>
(define (move u w) (lambda (x) (/ (- x u) (/ w (magnitude w)))))
(define u1 (map (move 3-i 4-i) t1))
(define u2 (map (move 3-i 4-i) t2))
(define u3 (map (move 3-i 4-i) t3))
(define u4 (map (move 3-i 4-i) t4))
(define u5 (map (move 3-i 4-i) t5))
(define u6 (map (move 3-i 4-i) t6))

;;; Expect (diff e<k> t<k>) = (list 0.0 0.0 0.0) +- small error
(define (diff e t) (map - e (apply angles t)))

4. […] Pages: 1 2 […]

5. cosmin said

A python solution:

def dist(A, B):
return (A[0] - B[0])**2 + (A[1] - B[1])**2

def dot_prod(A, B, C):
return (A[0] - B[0])*(C[0] - B[0]) + (A[1] - B[1])*(C[1] - B[1])

def cross_prod(A, B, C):
return (A[0] - B[0])*(C[1] - B[1]) + (A[1] - B[1])*(C[0] - B[0])

def classify_triangle(A, B, C):
s = sorted([cross_prod(A, B, C), cross_prod(B, C, A), cross_prod(C, A, B)])
if s[0] == 0:
return "not a triangle"
res = ""
d = sorted([dist(A, B), dist(B, C), dist(C, A)])
if d[0] == d[2]:
res = "equilateral "
elif d[0] == d[1] or d[1] == d[2]:
res = "isosceles "
else:
res = "scalene "
p = sorted([dot_prod(A, B, C), dot_prod(B, C, A), dot_prod(C, A, B)])
if p[0] < 0:
res += "obtuse "
elif p[0] == 0:
res += "right "
else:
res += "acute "
return res + "triangle"

print classify_triangle((0, 0), (0, 4), (1, 2))
print classify_triangle((1, 1), (1, 4), (3, 2))
print classify_triangle((2, 2), (2, 4), (4, 3))
print classify_triangle((3, 3), (3, 4), (5, 3))
print classify_triangle((4, 4), (4, 5), (5, 6))
print classify_triangle((5, 5), (5, 6), (6, 5))
print classify_triangle((6, 6), (6, 7), (6, 8))
print classify_triangle((7, 7), (7, 7), (7, 7))

6. cosmin said

It looks that the correct definition of the cross product has a “-” instead of a “+” in the middle:

def cross_prod(A, B, C):
return (A[0] - B[0])*(C[1] - B[1]) - (A[1] - B[1])*(C[0] - B[0])

7. jpv said

Here’s my take in Racket: Triangle Trilemma

It’s a bit longer than I expected, but I think it’s pretty solid. If anyone has any counter examples (like there were with the squares problem), I’d love to hear them.

8. Here is whole solution in Java with self explanatory doc

package in.kumarpallav.triangle;

import java.util.Arrays;
import java.util.Scanner;

/**
* The problem is to accept three points as input, determine if they form a
* triangle, and, if they do, classify it at equilateral (all three sides the
* same), isoceles (two sides the same, the other different), or scalene (all
* three sides different), and also classify it as acute (all three angles less
* than 90 degrees), obtuse (one angle greater than 90 degrees) or right (one
* angle equal 90 degrees).
*
* Following are conditions
* 1. Any three point on a plane can make a triangle if
* and only if all three are not on same line i.e. they don’t make a straight
* line
* 2. To be a equilateral triangle all three sides should mesure same, All equilateral triangle are always
* of 60 degree with each of the angle all three sides are less than 90
* 3. If two sides are of same length two it is an right angle triangle
* 4. Obviously if 1 side is greater than 90 degree it’s obtuse
* # Modularity
*
*
* @author Kumar Pallav
*
*/
public class Main {
private static String userInput=””;
private static Scanner scanner;
private static String typeOfTriangle;
public static void main (String args[]){
//Lets Print Instruction to user to enter command line input
instruction();
//Lets Take User Input from console
while(true){
try{
scanner = new Scanner(System.in);
userInput=scanner.nextLine();
//Validate user input
if(isUserInputValid(userInput.split(” “))){//This will ensure that user input are valid then only we need to proceed further
//Lets validate if the input are line forms a triangle
isTrianglePossible(userInput.split(” “));

}

}catch (Exception e){
System.out.println(“\n Something has gone wrong , we appologise”);

}

}
}
/**
* The method below will check if it is possible to make a triangle and is Yes it should proceed for
* @param userInput
*/
private static void isTrianglePossible(String coordinates[]) {
//Only case where there could be no triangle when all provided coordinates are on same plane
//i.e. either all x or y coordinates are same
double xCords[]=new double[3];
double yCords[]=new double[3];
String split[]=null;
for (int i=0;i90 degree. There can be one and only one obtuse angle , it comes as 90 degree
//certainly we have right angle triangle else we have acute angle triangle
//Step 1: Calculate all the distance
double d1,d2,d3;//All Sides of coordinates
d1=calculateDistance(xCords[0],yCords[0],xCords[1],yCords[1]);
d2=calculateDistance(xCords[0],yCords[0],xCords[2],yCords[2]);
d3=calculateDistance(xCords[1],yCords[1],xCords[2],yCords[2]);
if((xCords[0]==xCords[1])&&(xCords[1]==xCords[2])&&(xCords[0]==xCords[2])||
(yCords[0]==yCords[1])&&(yCords[1]==yCords[2])&&(yCords[0]==yCords[2])){
System.out.println(“Provided cordinates make a staight line, No triangle possible”);
}else
if(d1==0&&d2==0&&d3==0){

System.out.println(“No triangle possible,It is a point”);
}else if(d1==0||d2==0||d3==0){

System.out.println(“No triangle possible,Two coordinates are same”);
}
else if(d1==d2&&d2==d3&&d1==d3){
typeOfTriangle=”Equilateral”;
System.out.println(“Equilateral Triangle “);
}else{
//Find Largest of three provided d1, d2 and d3, the easiest is to sort so that highest one comes in beginning
if(d1==d2||d2==d3||d3==d1){
typeOfTriangle=”isosceles”;
}else{

typeOfTriangle=”scalene”;
}
double sortedDistance[]={d1,d2,d3};
Arrays.sort(sortedDistance);
//With Sorted
findAnglesAndDecide(sortedDistance);
}

}

private static void findAnglesAndDecide(double[] sortedDistance) {
//find cosine of angle largest in java
double num=(Math.pow(sortedDistance[0], 2))+(Math.pow(sortedDistance[1],2))-(Math.pow(sortedDistance[2],2));
double den=2*sortedDistance[0]*sortedDistance[1];
double cos=num/den;
//System.out.println(“Cos :”+cos);
double degree = Math.acos(cos) * 180/Math.PI;
if(degree>90){
System.out.println(typeOfTriangle+ ” obtuse triangle”);
}else if(degree==90){

System.out.println(typeOfTriangle+” right angle triangle”);
}else{
System.out.println(typeOfTriangle+” acute triangle”);
}

}
/**
*
* @param x1 :x1 cord
* @param y1 :y1 cord
* @param x2 :x2 cord
* @param y2 :y2 cord
* @return
*/
private static double calculateDistance(double x1, double y1, double x2,
double y2) {
return Math.sqrt(Math.pow((x2-x1),2)+Math.pow((y2-y1),2));
}
/**
* The code below checks the user input and validates the cordinates
* if Proper it returns true else value
* @param args
* @return
*/
public static boolean isUserInputValid(String args[]){
boolean isInputValid=true;
switch (args.length) {
case 3:
//iterate over input and find if they are in order and proper
String cords[]=null;
for(String a:args){
cords =a.split(“,”);
if(cords.length!=2){
System.out.println(“Provided cordinates are not valid”);
break;

}//If there are two coordinates per input lets verify if we they are in floating point else coordinates are not proper
else{
try{
for(String cord: cords){
validateCordinates(cord);
}
}catch(NumberFormatException nfe){
System.out.println(“Provided cordinates are not valid”);
isInputValid=false;//If number format exception happens provided inputs are not valid
break;
}
}

}
break;

default:
System.out.println(“Input provided is not valid”);
break;
}
return isInputValid;
}
/**
* @param a
* @throws NumberFormatException
*/
private static void validateCordinates(String a) throws NumberFormatException {
double d=Double.parseDouble(a);

}
/**
* instruction This will print instruction
* @author Kumar Pallav
*/
public static void instruction(){
String instruction=”****Welcome to triangle program*****\n” +
“To find the if the provided co-orodinates makes a triangle , Please enter input as ” +
“\n x,y x,y x,y \n\t where x and y are co-ordinated ” +
“\n To Quit enter exit”;
System.out.println(instruction);
}

}

9. Ali said

Hello, I am a bignner in python. I really need codes of prime and kruskal which will works on python runner. I was wondering if you could help me and send me the codes or give me precise info about these two codes. my email address is elfetop2012@yahoo.com. best wishes