(Note: this article was originally written in and transcribed to WordPress, so forgive the equation alignment. Get the original).

In a previous post, I outlined an analytical solution for intersecting lines and ellipses. In this post I’m doing much the same thing but rather with lines on lines. I’ll point out why the normal slope-intercept form for a line is a poor representation, and what we can do about that.

The triangular numbers are an interesting mathematical phenomenon that appears constantly in computer science. When you, the programmer, talk about the Big-Oh complexity of a nested for loop that gets executed times, you might just slap on it and call it a day.

But do you ever think about what that summation actually is? In this article I’ll present an alternative formulation of the series that I think is satisfying from a programmer’s point of view, and also present some interesting results from looking at the series in different ways.

(Note: this article was originally written in and transcribed to WordPress, so forgive the equation alignment. Get the original). If you have a line and an ellipse, how can you tell where they intersect? This is a relatively simple problem that has worked-out examples all over the web if you Google for “line ellipse intersection”. However, what I’ve come to find is that nobody will actually give you the solution for an arbitrary line and an arbitrary ellipse. I’m here to do just that. Read the rest of this entry »

Recently I was fortunate enough to be brought aboard a student-driven game design project by Jake Ross and some other students who are members of Texas A&M’s Visualization Lab (you should really check them out, they send a lot of animators to studios like Pixar and Dreamworks). Together, with a core team of about 8, we spent a year building an iPad game in our free time and named it Titan Ph.D. I built the AI (artificial intelligence), and this is the first of a 3-post series on how I did it.

Image provided courtesy of Reddit user TelescopicSaddlebag

Computers can seem pretty dumb sometimes, can’t they? Why can’t they just learn how to do things like we do? Learning comes so effortlessly to us humans; we don’t even remember learning something as extraordinarily complicated as speech – it just sort of happened. If I showed you 10 pictures, 5 with cats in them and 5 without (actually this is the internet, so 11 of those 10 pictures would have cats in them, but bear with me) you could easily identify which images contained cats. Because computers are basically math machines, unless you can very precisely define what a cat is, then a computer will not be very good at such a task. That’s where neural networks come in – what if we could simulate a human brain? And like a human brain, what if we could purpose our simulation to only look at cats?

Remember my post on the Dubin’s car? It’s a car that can either go forward, turn fully left, or turn fully right. In that post I explained that the shortest path from one point to another via the Dubin’s car could be described by one of six control sequences. The Reeds-Shepp car is essentially the same thing as the Dubin’s car, except it can also move backwards! This post isn’t quite the comprehensive step-by-step guide as the Dubin’s one, but I’ll give you a great overview of the paths, point you to some great online resources, and give you some tips if you plan on implementing them yourself!

Imagine you have a point, a single little dot on a piece of paper. What’s the quickest way to go from that point to another point on the piece of paper? You (the reader) sigh and answer ”A straight line” because it’s completely obvious; even first graders know that. Now let’s imagine you have an open parking lot, with a human standing in it. What’s the quickest way for the human to get from one side of the parking lot to the other? The answer is again obvious to you, so you get a little annoyed and half-shout ”A straight-line again, duh!”. Okay, okay, enough toss-up questions. Now what if I gave you a car in the parking lot and asked you what was the quickest way for that car to get into a parking spot? Hmm, a little harder now.

You can’t say a straight line because what if the car isn’t facing directly towards the parking space? Cars don’t just slide horizontally and then turn in place, so planning for them seems to be a lot more difficult than for a human. But! We can make planning for a car just about as easy as for a human if we consider the car to be a special type of car we’ll call a Dubin’s Car. Interested in knowing how? Then read on!

[Update: 10-21-2012: The geometry discussed in this post has been superseded by the discussion about path planning for Dubin’s Cars: https://gieseanw.wordpress.com/2012/10/21/a-comprehensive-step-by-step-tutorial-to-computing-dubins-paths/] I recently had a geometry problem I needed to solve involving finding tangent lines to two circles. If you’re like me, you don’t remember all the geometry you learned in school. And if you’re like me, you prefer searching the internet for answers versus turning to your books. I looked and looked online, but couldn’t really find a satisfying guide on finding the tangent points for two circles. Right now, even the Wikipedia page is a mess. How exactly does one “equate theta” and then “add x-y coordinates of a triangle” to a point? Perhaps in the future this will improve, but for now, here’s how I figured it out. I’m only going to run through finding one external tangent point. Figuring out the others as well as the tangent lines should become trivial afterwards.

Let’s say you want to learn how to classify something, but the ‘rules’ behind the classification are not obvious. For example, given some measurements about a person’s heart, can we tell if they have heart disease? What if you are hiking through the woods and want to know if a mushroom you see is edible or not? Perhaps the stem has a certain color, the head is a certain width, or it has a ‘curtain’ around it. Instead of spending years mastering which mushrooms are edible based on sight, how about you simply get a computer to tell you? Well, with decision trees you can!

Thanks to Scott Y’s comments in my article regarding a Sudoku Solver I wrote as part of an AI project, I decided to write a real solver that not only can solve any Sudoku puzzle, but can do it in just a few milliseconds.

Long story short: I represented Sudoku as an exact cover problem, then used Donald Knuth’s Algorithm X and Dancing Links implementation to solve that exact cover problem. Still here? Good, it’s time for me to explain a few things.

(Update October 2013: This project is available on GitHub!)