Saturday, June 18, 2011

Area of a Triangle Given Coordinates

There are at least 6 methods to determine the area of a triangle given the coordinates of the vertices.  Some of the methods apply to triangles only, and some are more generic.  We’ll find two clear winners for this problem (that are nearly the same), but also notice, that if we were given different information (such as lengths of sides instead of coordinates of vertices) it would change the winner.  I am focusing here on 2D coordinates.  Here's a picture of our triangle:

Heron’s Formula

Heron’s formula uses the lengths a, b, and c of the sides to determine the area of the triangle:


where



To use this formula, we must determine the lengths of the sides.  We use the Pythagorean theorem to do so:


 
 

This whole calculation involves 4 square roots, 9 multiplications, 1 division by 2, and 14 addition/subtractions.  This method is very expensive compared with the other methods.  However, if we were given the lengths of the sides and not the coordinates of the vertices, it would be less expensive than the alternative.  The alternative would require the use of trigonometric functions (law of cosines and law of sines) in order to determine the height to use the formula A = bh/2.  Trig functions are way more expensive (time-wise) than square roots.

Note that this method could be extended to work given 3D coordinates, since the Pythagorean theorem extends to 3D coordinates.  It would be a bit more expensive in 3D.

Coordinates Method

This method can be used with any polygon – it need not be a regular polygon (all sides and interior angles equal) or a triangle.  The only requirement is that none of the sides intersect.  The method is performed as follows:

clip_image002[10] clip_image004[6]
clip_image006[6] clip_image008 clip_image010 clip_image012
clip_image014 clip_image016 clip_image018 clip_image020
clip_image022 clip_image002[11] clip_image004[7] clip_image024



This method requires 6 multiplications, 1 division by 2, and 5 addition/subtractions – easily outperforming Heron’s formula when we’re given the coordinates.

Double Meridian Distance (DMD)

This is another generic method that applies in the same circumstances as the coordinates method.  It is always more efficient than using the method of coordinates.  In a spreadsheet is would look like this:

A B C D E F
1 x-coord y-coord delta y delta x DMD 2*A
2 Ax Ay =B3-B2 =A3-A2 =D2 =E2*C2
3 Bx By =B4-B3 =A4-A3 =E2+D2+D3 =E3*C3
4 Cy Cy =B5-B4 =A5-A4 =E3+D3+D4 =E4*C4
5 Ax Ay
6 =sum(F2:F4)/2

This method requires 3 multiplications, 1 division by 2, and 12 addition/subtractions.  Although we have way more addition subtraction, we have half the number of multiplications.  Since multiplication and division are way more expensive than addition and subtraction, this method is computationally superior to the method of coordinates.

The Usual Method (sorta)

You`re probably wondering why I haven`t just taken half the base times the height.  Okay wise guy, where`s the base?  How about the height?  Can we calculate them?  Yes, but are you sure you know how much work you’re in for?  You say, isn’t the area just


No, it’s not that simple.  The base must be the length of one of the sides.  The height must be measured perpendicularly from the chosen base to the vertex which is not on the base.  But we can find the area using this method if we follow it through to the bitter end.  Let’s do it.

First, we calculate the length of the base, which we will choose as side b above:


 
Now, we need to calculate the height, h, between point B and line AC (side b).  This will be nontrivial and slightly painful. 

We determine the equation of the line through A and C using the point-slope form:







We re-express this result as


where


 
 

At this point we use a formula for the distance between a point and a line that uses the equation of the line as expressed above:


Finally, we get to say “Area = bh/2,” and I hope you are satisfied!  We needed 2 square roots, 9 multiplication/divisions, and 11 addition/subtractions.  This method gives you the right answer, but there’s got to be a better way!

A Better Way

Let’s redraw our triangle with a fancy rectangular border:
Okay, it’s not that fancy, but it’s useful!  First, let’s calculate L, R, λ, and ρ. 



We can calculate the area of our triangle now:







I’ve skipped showing all of the simple expansion and simplification steps above because I’m getting tired of all that typing.  But here’s the vital statistics: 2 multiplications, 1 division by 2, and 5 addition/subtractions.

Cross Product Method

This method not only works in 3D, it requires 3D – sorta.  We’ll apply it to the 2D case here – we just augment our coordinates with zeros for the z-coordinates.  It goes like this:


 
 

The final score for this method is 2 multiplications, 1 division by 2, and 5 addition subtractions.  This method is the clear winner since it is tied with the previous method in 2D but is easily applied to 3D with an increase in cost.

Method Comparison Table
method square roots multiplication/division division by 2 addition/
subtraction
Heron’s Formula 4 9 1 14
Coordinates Method 0 6 1 5
DMDs 0 3 1 12
“Usual” Method 2 9 1 11
A Better Way 0 2 1 5
Cross Product 0 2 1 5

* Note:  I've put division by 2 in a separate category because division and multiplication by 2 can be implemented more efficiently on the computer than general case multiplication and division.

Monday, June 13, 2011

3D Analogue to the Trapezoid (part 1)

The other day I derived a volume formula that had exactly the result that you would expect if you were to take a guess at it - I didn't even think about it until after I had derived it.

A trapezoid is a quadrilateral (four sided figure) with (at least) one pair of parallel sides.  (If it has two pairs of parallel sides it is a parallelogram, though technically it is still also a trapezoid.)
 

The area, A, of a trapezoid is given by, A = 1/2(b1 + b2)h, where b1 and b2 are the parallel sides and h is the distance measured perpendicularly between the two parallel sides.  You can think of the formula in words as, “the area of a trapezoid is equal to the average of the lengths of the parallel sides multiplied by the perpendicular distance between them.”

Below is a shape that is similar in some respects, but it’s three dimensional.  Instead of two parallel lines, there are three parallel lines with lengths a, b, and c.  At the base of this solid shape is a triangle.  (It’s not important that the lines all come to a common base – the volume formula I came up with will work anyways.)  What is significant about the triangle B is that it is formed by lines which are all perpendicular to the vertical lines (a, b, c).  I don’t know what this shape is called; let’s call it an irregular triangular prism.

The volume, V, of the above shape is given by V = 1/3(a+b+c)B, where B is the area of the triangle formed by a plane perpendicular to the three parallel sides and a, b, and c are the lengths of the parallel sides.  You can think of this formula in words as, “the volume of an irregular triangular prism is equal to the average of the lengths of the three parallel sides multiplied by the perpendicular cross-sectional area.”

(See proof.  Or, see a different analogous shape in part 2.)

Sorta makes you wonder it there’s a four dimensional analogue…