An interesting concept I came across recently in an introductory geometry book is barycentric coordinates. The fundamental idea is defining the location of a point by its relationship to the points of a triangle. (Well, technically you can use any polygon, but we will keep things simple.)
So, each of the vertices of the triangle (A, B, and C) are given a sort of weight or pull factor. These three numbers uniquely represent the position of P. The theorem goes
If A, B, C are three non-collinear points, any vector P may be expressed in terms of the vectors A, B, C thus:
P = xA + yB +zC, where x + y + z = 1Geometry: A Comprehensive Course, Dan Pedoe
If P is pulled all the way over to vertex A, then the coordinates become (1, 0, 0). Likewise at B it is (0, 1, 0) and for C it is (0, 0, 1). Another coordinate inside the triangle would be (⅓, ⅓, ⅓). If the point moves outside the triangle, some of those coordinates become negative.
Of course, instead of boring old vectors, you can use… complex numbers!
From the formula, it is obvious how to start with some barycentric coordinates, add a triangle, and find the point. Here is some Racket code:
(define (barycentric->complex x y z A B C) (+ (* x A) (* y B) (* z C)))
Note, that you can use any triangle you want with the same barycentric coordinates. This could allow you to stretch the graph of some set of coordinates in various ways.
But, how do you convert in the other direction, having a point and a triangle, and wanting the barycentric coordinates? This is a little more complicated. Fortunately, it happens that the factor for each of the vertices is equal to the proportional area of the triangle opposite that vertex. So, looking at this diagram again
x = [BCP] / [ABC], y = [CAP] / [ABC], z = [ABP] / [ABC]
where [BCP] is the area of triangle BCP, etc.
Now, a tricky part here is that the areas must be signed areas, or the formula doesn’t necessarily work correctly. Signed area means that you have to be consistent in assigning a negative or positive value to the area of the triangle, depending on the orientation of the vertices. So, if you happen to plug in the vertices in a counter-clockwise direction, you get a negative area, and in a clockwise direction, you get a positive area. Thankfully, there is an elegant formula for determining this, which I will represent by this Racket function
(define (orientation Z1 Z2 Z3) (let* ([rise1 (- (imag-part Z2) (imag-part Z1))] [rise2 (- (imag-part Z3) (imag-part Z2))] [run1 (- (real-part Z2) (real-part Z1))] [run2 (- (real-part Z3) (real-part Z2))] [diff (- (* rise1 run2) (* rise2 run1))]) (if (< diff 0) 'ccw (if (> diff 0) 'cw 'col))))
The function returns ‘ccw for counter-clockwise, ‘cw for clockwise, and ‘col for collinear (i.e., the points are on a straight line, which is not relevant in this application).
This allows us to have a signed-area function, using the common formula for determining the area of a triangle from just the length of the sides. We get the length of the sides by subtracting the complex numbers from each other and pulling the magnitudes of the resulting complex numbers.
(define (signed-area A B C) (let* ([a (magnitude (- C B))] [b (magnitude (- A C))] [c (magnitude (- A B))] [s (* (+ a b c) 0.5)] [area (sqrt (* s (- s a) (- s b) (- s c)))] [orient (orientation A B C)]) (if (eq? orient 'ccw) (* -1 area) area)))
And finally we determine x, y, and z:
(define (complex->barycentric A B C P) (let ([ABC (signed-area A B C)]) (list (/ (signed-area B C P) ABC) (/ (signed-area C A P) ABC) (/ (signed-area A B P) ABC))))
See, simple as Pi! Heh, heh.
firstname.lastname@example.org> (complex->barycentric 0 6 2+2i 2+i)
'(0.33333333333333376 0.16666666666666657 0.5000000000000009)
email@example.com> (barycentric->complex 0.33333333333333376 0.16666666666666657 0.5000000000000009 0 6 2+2i)
So, you can see it works, though there is some very small inaccuracy introduced by the approximations that occur during the conversion operations.
I hope to explore, in future posts, some interesting applications of barycentric coordinates.