If you came here searching for the Karnaugh Map boolean algebra program, please click here.
Amorphous maze creation algorithm is based on starting from an outermost wall and extending the wall by a small segment at a time in a manner that avoids walls from crossing over each other. Each time a line segment is successfully extended, it is added to a global repository of line segments to test against. When the extending operation comes to a dead end, a different coordinate is randomly chosen from the repository as a starting point of a new branch.
|
There are various sections within my program that need to compute the distance between two points. If P1=(x1,y1) and P2=(x2,y2), then by the Pythagorean theorem, distance between two points P1 and P2 is:
Sometimes, we need to calculate if a given point lies within a circle or a rectangle. We can test if a certain point P lies inside or outside a circle by calculating the distance between P and the center of the circle using the aforementioned distance formula. As for the rectangle, we can tell if a certain point Q lies inside or outside of a bounded rectangle by conducting four tests that tell on which side of a line a point lies. Which leads to the next topic of:
There are several ways to determine on which side of a line segment P2P3 a point P1 lies. One way is to find the equation of the line y=ax+b that passes through the two points and test if y<ax+b, but this runs into difficulty when the line is perfectly vertical. A better way is to find the normal vector P4P5 emanating from the center point P4 of the line segment and compute the inner product of vectors P1P4 and P4P5.
Iff the inner product is positive, P1 lies on the white side of the line segment and iff negative, the yellow side in the picture above.
Sometimes we need to rotate a point. The formula for rotating a point P1 theta radians counter clockwise about the origin, resulting in P2, is:
 |
If we want to test if two line segments intersect, one method is to write the equations of the lines in the format of y=a1x+b1, y=a2x+b2 and solve for (x,y). The problem with this approach is that it cannot handle perfectly vertical lines. To overcome this, we introduce a third scalar variable k. Consider a single line segment with end points P and Q. Vector originating at point P and terminating at point Q is ( Q - P ). Therefore, a vector R parallel to this line is
R = k( Q - P )
where k is an arbitrary scalar constant. Therefore, all points on the line can be expressed as
S = P+k( Q - P )
This form is called the parametric representation of a line.
By expressing the two line segments parametrically, it is relatively simple to determine if line segments 1 and 2 intersect. Let
Using the parametric representation of lines
Where m and n are the amount by which P5 is into each line segments. I.e., m is the distance of P1 to P5, normalized with respect to length of line segment 1 and n is the distance of P3 to P5, normalized with respect to length of line segment 2. In the figure above, if the intersection lies to the left of P1, m becomes negative, and if the intersection lies to the right of P2, m becomes greater than one. Solving for the intersection requires solving the following four simultaneous equations:
Eliminating x5 and y5,
Using Cramer's rule to solve this pair of equations for m and n,
We need to satisfy both 0<m<1 and 0<n<1. Write m and n as:
where M and N are numerators whose signs are adjusted so that the denominator D is always positive.
If the lines are parallel, D, the determinant at the denominator is zero and will cause a divide-by-zero error. So rather than evaluating M/D or N/D, we take the numerators and denominators apart and test for the following four conditions:
The line segments 1 and 2 intersect if and only if these four conditions are met.
Last update 2011-07-31
