Monday, 19 November 2012

How does I draw it?

Ran into a rather interesting problem this week, it involves finding the common (outer) tangents of two circles, but more on that in a bit. First lets look at why.
You have a bunch of Nav-Circles all set up neatly on a map, but all you can see are the circles.

 Indeed drawing circles on a computer screen is only a small jump and a bit of maths from drawing a triangle so that need not be the issue, the issue is what you should see between the circles. If you look at my previous examples (and the one below) you will no doubt notice that all the walk-able areas are draw (in Inkscape's beautiful list of default colours), and that was pretty easy doing it all by hand.

I naively figured that it would be pretty simple to get the computer to do the same; all the information's there, it's just a bit of vector maths, how hard could it be? It turns out to be a non trivial task if you're on the wrong track, thankfully I have a teacher at hand to solve the problem in five minutes and make me look incompetent.
So what's the solution? Maybe I'll start with...
The problem:
Find t where t is the vector that shares a common outer tangent with two circles that have centre positions at A and B respectively and radii of R and r.
First we find the vector from A to B (we'll call this vector D for difference), so D = B - A

What we want to do is normalize D, rotate it by a certain angle, scale it by R and add A to find the point P (shown bellow), as well as scale it by r and add B to find point Q

The problem now is finding the angle to rotate by, let's denote the angle with the Greek letter Omega. By projecting a line from B onto the line AP, we can form a helpful little triangle. The triangle's sides have lengths: (R - r), |t| and hypotenuse |D|.

Using the Pythagorean theory we can at least find out the length of t

But that's not all that helpful, but what we can use is SOH CAH TOA to find omega, we know the Adjacent length (R-r) and the Hypotenuse (|D|) so
(or if you're an idiot like me you'll use arcsin( |t|/|D|) and not notice your gratuitous scheme until you're writing a web-log post on it)

Excellent, now we can find the points P and Q, you also only need to draw one line PQ (or if you want filled in square, PQAB) for each of each circle's neighbours. When the line is drawn from the blue circle it will be on top, and when coming from pink, it will be on the bottom (or vice-versa depending on exact implementation).

No comments:

Post a Comment