I'm trying to write a program that should solve a 12x12 rush hour problem:
I won't go in the details of this program to much. The program already works for 6x6 puzzles, but for 12x12 puzzles, it is just too slow. Investigating what made my program slow shows that most of the time, my CPU is busy trying to calculate if two cars overlap.
Now, every car is basically a vector I guess in mathematical terms. I see the point in the top left as (0,0). And the right bottom corner, as point (11,11).
So I see the green car in the top left as the vector from (0,0) to (1,0). And the yellow car in the top left, as a vector form (0,2) to (2,2).
Now to see if two cars overlap. I just check if any of the points that the green car covers {(0,0), (1,0)} is equal to any of the points that the yellow car covers {(0,2), (1,2), (2,2)}. (so if the intersection is empty or not). It seems like my CPU is busy with this calculation 40% of the time.
So I'm wondering, could I make this calculation faster? Would there be some magic formula, that I could do with those 8 numbers (in this example:
(0,0), (1,0) and (0,2),(2,2)), so that could do this calculation more efficient?
So you want to find out whether the rectangle with corners $(x_1,y_1),(x_2,y_2)$ overlaps the one with corners $(x_3,y_3),(x_4,y_4)$.
Let's assume you have already ordered your coordinates such that $$x_1\le x_2,\quad y_1\le y_2,\quad x_3\le x_4,\quad y_3\le y_4.$$
Then your rectangles overlap if the interval $[x_1,x_2]$ overlaps with $[x_3,x_4]$ and the interval $[y_1,y_2]$ overlaps with $[y_3,y_4]$.
The former is the case if $x_2\ge x_3$ and $x_1\le x_4$. The latter is the same, only with $y$s instead of $x$s. So what you should test is whether $$ x_2 \ge x_3 ~\land~ x_1\le x_4 ~\land~ y_2 \ge y_3 ~\land~ y_1\le y_4 $$