2D Geometry Problem Help Sat Oct 14 13:51:23 EDT 2006 For some reason many young computer scientists think that geometry problems are hard, and avoid them. The purpose of this discussion is to demonstrate that geometry problems are fairly easy after all. We will restrict ourselves here to 2D geometry. Basics ------ Let p = (px,py) and q = (qx,qy) be points in the plane. The difference v = (vx,vy) = q - p = (qx-px,qy-py) is the vector from p to q. Its length is |v| = sqrt( vx**2 + vy**2 ) The scalar product of two vectors u = (ux,uy) and v = (vx,vy) is u.v = ux*vx + uy*vy = |u| |v| cos(theta) where theta is the angle between u and v. The sign of theta does not matter because cos(theta) = cos(-theta). Note that |v| = sqrt (v.v) Note that u.v = 0 if and only if u and v are orthogonal (at right angles) to each other, i.e., if theta = + or - 90 degrees and cos(theta) = 0. A `unit' vector v is a vector of length 1 ( |v| = 1 ). If u and v are unit vectors at right angles to each other, which is the same as saying that |u| = 1, |v| = 1, u.v = 0 then one can ask what the coordinates of a point p would be in the coordinate system in which u is in the positive direction of the x-axis and v is in the positive direction of the y-axis. The answer is (u.p, v.p) Note that | u.p | | ux uy | | px | | | = | | | | | v.p | | vx vy | | py | so u and v are the rows of the 2x2 matrix which by left multiplication translates from old xy coordinates to new uv coordinates. A counterclockwise rotation R(theta) of a vector v=(vx,vy) by an angle theta is | cos(theta) - sin(theta) | | vx | R(theta).v = | | | | | sin(theta) cos(theta) | | vy | | vx cos(theta) - vy sin(theta) | = | | | vx sin(theta) + vy cos(theta) | Most particularly, if theta = 90 degrees, then | 0 -1 | R(90 degrees) = | | | 1 0 | R(90 degrees).v = (-vy,vx) Given two points p and q, it is common to want to change coordinates so these points are on the x-axis. Let v = q - p be the vector from p to q. Let w = R(90 deg).v, so w is orthogonal to v and |w| = |v|. Scalar products by v measure distance in the v direction, and scalar products by w measure distance in the w direction. w.q = w.p; to check this we see that w.p = w.q + w.(p-q) and w.(p-q) = w.v = (R(90 deg).v).v = 0. Let f = w.q = w.p. Then for any point r use the new coordinates (rx',ry') = (v.r,w.r-f). We have (px',py') = (v.p,0) and (qx',qy') = (v.q,0) because w.p-f = 0 = w.q - f. Because v and w are orthogonal and both have the same length |v| = |w| = |R(90 deg).v|, distances between points in the new coor- dinates are just |v| times distances in the old coordin- ates. For example, the distance between p and q in the new coordinate system is |v.q - v.p| = |v.v| = |v|**2 which is |v| times the distance between p and q in the old coordinate system. Since (wx,wy) = (-vy,vx) we have f = w.p = - vy * px + vx * py = w.q = - vy * qx + vx * qy w.r = - vy * rx + vx * ry ry' = - vy * rx + vx * ry - f So the summary of the part of the computation that you need to remember is vx = qx - px vy = qy - py f = - vy * px + vx * py = -vy * qx + vx * qy for r = (rx,ry) the new coordinates are rx' = - vy * rx + vx * ry - f ry' = - vy * rx + vx * ry - f distances between points in new coordinates are |v| = sqrt ( vx*vx + vy*vy ) times distances between points in old coordinates Note that if all coordinates in the old coordinate sys- tem are integers, all coordinates in the new coordinate system are integers. This is a big advantage if exact arithmetic is needed, as when one must determine if a point lies exactly on a line. This is why we do NOT di- vide all the new coordinates by |v|, and thus must deal with new coordinate distances that are not identical to old coordinate distances. The last coordinate change is basic to much elementary computational geometry, and you should learn it very well. Lines Dividing Planes ----- -------- ------ The line through points p and q, oriented in the direc- tion from p to q (p != q is assumed), divides the plane into three parts: points to the right of the line (fac- ing in the direction from p to q), points to the left of the line, and points on the line. How do we find out whether a point r is to the right, left, or on the line? If we change coordinates as indicate in the last section then for r vx = qx - px vy = qy - py f = - vy * px + vx * py = - vy * qx + vx * qy ry' = - vy * rx + vx * ry - f ry' > 0 if r is to the left of the line; ry' == 0 if r is on the line; ry' < 0 if r is to the right of the line; The distance from r to the infinite line through p and q is |ry'| in the new coordinates or |ry'|/|v| in the ori- ginal coordinates. The Distance of a Point to a Finite Line --- -------- -- - ----- -- - ------ ---- We just indicated how to find the distance between a point r and an infinite line that runs through two points p and q. What if the line is finite with ends p and q? Again shift to the new coordinates so that: vx = qx - px vy = qy - py f = - vy * px + vx * py = - vy * qx + vx * qy rx' = vx * rx + vy * ry ry' = - vy * rx + vx * ry - f px' = vx * px + vy * py py' = 0 qx' = vx * qx + vy * qy qy' = 0 So p and q are now on the x'-axis and the problem is fairly easy. There are two cases: if rx' < px' and rx' < qx' or rx' > px' and rx' > qx' then r is off the end of the line from p to q and the distance is the minimum of |r-p| and |r-q| if px' <= rx' <= qx' or qx' <= rx' <= px' then r is over the line segment and the distance is |ry'|/|v|, the same as the distance from r to the infinite line through p and q Intersection of a Finite Line and an Infinite Line ------------ -- - ------ ---- --- -- -------- ---- When does the infinite line through p1 and p2 intersect the interior of the finite line from q1 to q2? By interior we mean the part of the line that excludes the endpoints. Answer: when q1 is on one side of the infi- nite line and q2 is on the other side, if we ignore the special case where q1 and q2 are BOTH on the infinite line. So we can compute: vx = p2x - p1x vy = p2y - p1y f = - vy * p1x + vx * p1y = - vy * p2x + vx * p2y q1y' = - vy * q1x + vx * q1y - f q2y' = - vy * q2x + vx * q2y - f then q1 and q2 are on opposite sides of the infinite line through p1 and p2 if and only if: q1y' > 0 and q2y' < 0 or q1y' < 0 and q2y' > 0 or equivalently: q1y' * q2y' < 0 When does the infinite line through p1 and p2 intersect the finite line from q1 to q2, including the possibility of intersecting at an end point, i.e., at q1 or q2. Answer: if and only if q1y' * q2y' <= 0. This equation also handles the case where q1 and q2 are BOTH on the infinite line. Convex Hulls and Polygons ------ ----- --- -------- The clockwise convex hull of a set of points V in a plane is a sequence of points of V, p1, p2, p3, ..., p(N), such that for every i, all the points of V are on or to the right of the infinite line from p(i) to p((i-1 mod N)+1), and such that no point p(j) is on this line except of course p(i) and p((i-1 mod N)+1). Then the finite lines from p(i) to p((i-1 mod N)+1) for i = 1, ..., N are the sides of the smallest convex polygon such that all the points of V are inside this polygon or on its boundary. To specify a polygon we give its boundary, which for a convex polygon is either its clockwise or counterclock- wise convex hull. The counterclockwise hull has the same property as the clockwise hull with `left' replac- ing `right' in the above definition. Inside Convex Polygons ------ ------ -------- Suppose we have a clockwise convex hull p1, ..., p(N) that defines a convex polygon. So the sides of the polygon with a clockwise orientation are the lines from p(i) to p((i-1 mod N)+1), for i = 1, ..., N, and no three of the points p1, ..., p(N) lie on the same line. Then a point r is inside the convex polygon but not on the boundary of the polygon if and only if r is to the right of the infinite line that extends each clockwise oriented side of the polygon. A point r is inside OR ON the boundary of a polygon if and only if r is to the right of OR ON the infinite line that extends each clockwise oriented side of the polygon. Finding the Convex Hull ------- --- ------ ---- To find the convex hull of a finite set of points V, first find some point p1 on the hull, which can be done say by choosing a leftmost point in V and given two leftmost points choosing the highest. Then extend the hull recursively from p(i) to p(i+1) by using the following. Given a point p, define a relation among points q1, q2 that are not equal to p as follows: definition: q1 > q2 if and only if q2 is to the right of the infinite line from p through q1, or q2 is on this line and closer to p than q1 is. If p is a hull point, this relation is antisymmetric and transitive (proof to reader). So given the hull up to p(i), choose p(i+1) to be the maximum point in V accord- ing to this relation. Stop when p(i+1) = p1, in which case N=i. This is not the fastest algorithm, as it has time O(|V|*|H|) where |V| is the number of points in V and |H| is the number of points on the hull. A faster algorithm is the Graham-scan algorithm that begins with a sort of V and has running time dominated by the sort time, O(|V| log|V|). Usually the extra speed is unne- cessary, but just in case, the Graham-scan algorithm is: S = V compute p1 as above and remove it from S let j = 1 while S is not empty: let p(j+1) be any leftmost point in S and remove it from S while j >= 2 and p(j+1) is to the left of the directed infinite line from p(j-1) to pj: set pj = p(j+1) set j = j - 1 if j < 2 or if p(j+1) is NOT on the directed in- finite line from p(j-1) to pj, set j = j + 1 else if p(j-1) is closer to pj than to p(j+1), set pj = p(j+1) When this algorithm stops only half the hull has been found. To find the other half, reset S to V minus all the points on the hull, and continue the algorithm with `leftmost' replaced by `rightmost'. Intersection of Two Finite Lines ------------ -- --- ------ ----- Suppose we are given four points, p1, p2, q1, q2. Question: Does the interior of the finite line from p1 to p2 intersect the interior of the finite line from q1 to q2. By the interior of a line we mean the part of the line that excludes its end points. Also, we DO NOT COUNT as intersections parallel lines that overlap, which we will treat as a special case below. Answer: The interiors of the lines intersect if and only if the infinite line through p1 and p2 intersects the interior of the line from q1 to q2, and the infinite line through q1 and q2 intersects the interior of the line from p1 to p2. If we wanted to know whether the finite lines including end points intersect, we ask whether the infinite lines intersect the finite lines, endpoints included. Thus we use the test q1y' * q2y' <= 0 and similarly with the p's and q's exchanged. Again there is a special case where p1, p2, q1, and q2 are all on the same straight line and the finite lines may or may not intersect. What if p1, p2, q1, and q2 are ALL on the same straight line? Then p1y' = p2y' = q1y' = q2y' = 0. We compute p1x', p2x', q1x', q2x'. There is overlap (endpoints in- cluded) if and only if at least of the line ends is on the other finite line, i.e., if at least one of the fol- lowing is true: p1x' <= q1x' <= p2x' q1x' <= p1x' <= q2x' p2x' <= q1x' <= p1x' q2x' <= p1x' <= q1x' p1x' <= q2x' <= p2x' q1x' <= p2x' <= q2x' p2x' <= q2x' <= p1x' q2x' <= p2x' <= q1x' Lines Intersecting Polygons ----- ------------ -------- So when does the interior of a line from r1 to r2 inter- sect the inside of a convex polygon? It does if the interior of the line from r1 to r2 intersects the inter- ior of any side of the polygon, but r1 and r2 are not both on the infinite line extending this side. It also does if r1 and r2 are both inside or on the boundary of the polygon, but are not both on the same single side of the polygon. These are the only two cases where the interior of the line from r1 to r2 can intersect the interior of the polygon, UNLESS some of the convex hull points p1, ..., p(N) are in the interior of the line from r1 to r2. In this last case, use a convex hull point in the interior of the line to divide the line in two, and recursively ask if the interiors of either of the two new line seg- ments intersect the interior of the polygon. So all one has to do is take each clockwise side of the polygon and check that r1 and r2 are not both on that side and either the interior of the finite line from r1 and r2 intersects the interior of the side, or r1 and r2 are both on or to the right of the infinite line exten- ding the side. During this process one checks each convex hull point p to see if it is in the interior of the line from r1 to r2, and if it is, one then divides the line from r1 to r2 up into two segments, one from r1 to p and one from p to r2, and then one applies the algorithm recursively to see if the interior of either of these two segments intersects the interior of the polygon. Polygon Maze ------- ---- Problem: Given a set of convex polygons in a plane, and two points p and q outside any convex polygon, find the shortest path from p to q that does not go inside any convex polygon. Paths may travel on the edges of a polygon if these are not inside some other polygon. Solution: Let V be the set of vertexes of the polygons plus the two points p and q. Then the path to be found can be represented as a sequence of straight line segments with vertexes in V (proof to reader). So it is a shortest path in an undirected graph whose vertexes are V such that given points r1 and r2 in V, there is an edge in this undirected graph between r1 and r2 if and only if the interior of the line from r1 to r2 does not intersect the interior of any polygon. Actually, we can make the computation simpler by also deleting an edge from r1 to r2 if the interior of the line from r1 to r2 contains any member of V, as the shortest path can be composed of line segments between members of V that do not contain other members of V. Circular Anti-Maze -------- --------- Find the shortest path between two points in a plane that has circular holes in it. The part of a path that transverses a hole does NOT count toward the length of the path. Solution: let V be the set consisting of the two points and the centers of the holes. Then the path consists of straight line segments with end points in V. The length of each segment is the distance between its ends minus the radius of any hole centered at one end, or is 0 if this length is negative. The reader should try to prove that his works, even when holes overlap. Robot Arms ----- ---- Suppose we have a planar robot arm. Such an arm con- sists of line segments in an order. The beginning of each segment is a pivot point, around which a servo can rotate the segment and anything attached to its end. The end of a segment is attached to the beginning of the next segment, or to the robot hand if the segment is the last segment of the arm. We will define the end of the last segment to also be a pivot point: it could have a servo to rotate the hand. The parameters of the arm are the lengths of the seg- ments and the angular settings of the servos. A servo is typically set to have 0 angle if the segment follow- ing it continues in the same direction as the segment preceding it. We will assume that a positive angle means the arm following the servo is rotated counter- clockwise by that angle. Particular robot arms may use other conventions for servo angles. We will also assume that the first pivot point is at the origin, and that the setting of 0 degrees for the first servo points the first segment along the positive x-axis. The position of the pivot points of such an arm can be computed recursively by induction on the number of segments in the arm. If there are 0 segments, there is only one pivot point (the hand's), and it is at the origin. The setting of the servo at that pivot point is irrelevant to the position of the pivot points. If there are more than 0 segments, assume for the moment that the first segment is such that its end (not its beginning) is at the origin and its orientation is in the direction of the positive x-axis, so its servo setting is 0 degrees. Next compute the positions of the pivot points at the ends of the other segments by a recursive call, pretend- ing that the first segment does not exist, so the arm has one fewer segments than it actually has. Now translate the origin to the beginning of the first segment by adding the length of this segment to the x coordinate of every pivot point. The beginning of the first segment is now the origin. The setting of the first servo is still 0 degrees. Now rotate all the pivot points about the origin by the amount indicated by the setting of the first servo. This finishes the computation. This computation is easy because we use recursion to build the arm from its end, and not from its beginning. File: 2D_geometry Author: Bob Walton Date: See top of file. The authors have placed this file in the public domain; they make no warranty and accept no liability for this file. RCS Info (may not be true date or author): $Author: walton $ $Date: 2006/10/14 17:52:21 $ $RCSfile: 2D_geometry,v $ $Revision: 1.21 $