19
TCG2061 Computational Geometry Chapter 2 (23/06/00) page
Chapter 2. Points, Lines, and Polygons
2.1 Point Relationships
Placing a set of points in sorted order can significantly speed up the computation of some computational geometry problems.
· A lexicographic order relation ( or, dictionary order relation) between two points p and q along the x-direction can be defined as
p < q if px < qx ;
or, px = qx AND py < qy
· A lexicographic order relation along the y-direction can be defined as
p < q if py < qy ;
or, py = qy AND px < qx
· Sorting N points in a lexicographic order can be done in O(N log2N) time, using a quick sort or merge sort algorithm.
· Searching sorted arrays can be done in O(N log2N) time (using a binary search).
2.2 Point-Line Relationships
The two-point form equation of a line passing through two points p and q can be written as
This formula is easily derived from proportional triangles. To avoid division by zero for vertical or horizontal lines, the equation can be rewritten as:
fpq(x, y) º (qx- px) (y- py) - (qy- py) (x- px) = 0.
· A point r lies on the line if fpq(r) = 0.
· A point r lies on the on the left side of line if fpq(r) > 0.
· A point r lies on the on the right side of line if fpq(r) < 0.
Note: fpq(r) º (qx-px)(ry-py) - (qy-py)(rx-px) = (for 2D vectors)
Therefore, r is on the left side of if it forms a positive angle from the vector .
The following statements are equivalent:
The point r is on the left of the directed line .
Points p, q, and r are oriented in an anti-clockwise sense.
The triangle pqr is positively oriented.
fpq(r) > 0
Note the following:
· The area of the triangle pqr is.
· The line equation can be written in determinant form as
fpq(r) = = (qxry - qyrx ) + ( pyrx - pxry) + ( pxqy - pyqx)
= qx ry - pyqx - pxry - qyrx + pxqy + pyrx
= ( qx ry - pyqx - pxry + pxpy)- (qyrx - pxqy - pyrx + pxpy)
= (qx-px)(ry-py) - (qy-py)(rx-px)
To summarize, the orientation of the triplet pqr is:
· anti-clockwise if fpq(r) > 0.
· collinear if fpq(r) = 0.
· clockwise if fpq(r) < 0.
The line pq divides the entire plane into two half planes
· fpq(x, y)³0
· fpq(x, y)£ 0.
Two points, r and s, are on the same side of a line , if they belong to the same half-plane.
· if fpq(r) fpq(s) > 0, r and s lie on the same side of a line .
· if fpq(r) fpq(s) < 0, r and s lie on opposite sides of a line .
2.3 Line Segment Intersection
The parametric form of the equation of a line in 2 dimensions, defined by 2 points p and q, is given by
x = px + t (qx - px)
y = py + t (qy - py)
If 0 £ t £ 1, the point (x, y) lies on the line segment
If t > 1, the point (x, y) lies beyond the point q on the line.
If t < 0, the point (x, y) lies beyond the point p on the line.
Two line segments and intersect at a point w, if and only if the point of intersection is between the end points of both the line segments. Using t1 and t2 as parameters for and respectively, at the intersection point w:
px + t1 (qx - px) = rx + t2 (sx - rx)
py + t1 (qy - py) = ry + t2 (sy - ry)
These two linear equations can be solved for the two unknowns t1 and t2. If the solution satisfies the relations
0 £ t1 £ 1 , and 0 £ t2 £ 1,
then a valid intersection point between the two line segments exists.
The most straightforward way to solve for the intersection of two lines is to rearrange the above equations into a matrix formalization and use Cramer’s rule to solve for t1 and t2. This looks like the following:
t1 (qx - px) - t2 (sx - rx) = rx - px
t1 (qy - py) - t2 (sy - ry) = ry - py
Can be written as
Using Cramer’s rule gives:
det =
t1 =
t2 =
Note:
· Both t1 and t2.must lie between zero and one for a valid intersection to exist.
· If the determinant of the matrix (det) is zero, the lines are parallel. There are two cases: 1) there is no solution or
2) the lines are colinear and there are an infinite number of solutions.
· The determinant of the matrix is the cross product of and , which calculates the sin of the angle between the two vectors.
The necessary and sufficient condition for two line segments and to intersect is that the points p and q lie on either side of the line , and the points r and s lie on either sides of line . That is:
fpq(r) fpq(s) £ 0, and
frs(p) frs(q) £ 0.
2.4 Convex Polygons
A region in a plane is convex if, for any two points in the region, the line segment between the two points lies entirely in the region.
A convex polygon has the following properties:
· Every diagonal of a convex polygon is a chord (from definition).
· Every vertex of a convex polygon is convex (less than 180°).
· Every convex polygon is simple (no edge intersections).
· Every anti-clockwise traversal of a convex polygon either continues straight or turns left at every vertex. Similarly a clockwise traversal turns right at every vertex.
· The intersection of two convex polygons is also convex (prove!).
· A convex polygon can be easily triangulated using chords from any vertex connecting all its non-adjacent vertices.
The above properties make convex polygons easier to work with than arbitrary polygons.
The area of a convex polygon L with n vertices p0 , p1 , p2 ,...., pn-1 is
L =
The point inclusion test refers to the problem of determining whether a given point is inside a convex polygon. The point inclusion test can be formally stated as follows.
A point q is inside a convex polygon if and only if it is on the same side of all its edges.
For example, if the polygon is traversed in the anti-clockwise sense, then the point q is an interior point only if it lies on the left of all the edges. In this case, the vertices p0 , p1 , p2 ,...., pn-1 are in anti-clockwise order, and if a point q has to be inside the polygon, then
fpipi+1 (q) ³ 0, for i = 0, 1, 2, ...n-1; Pn = P0 .
2.5 Star-Shaped Polygons
Consider two points p and q inside a polygon. The point p is said to be visible at q (or p “sees” q) if the line segment pq is entirely within the polygon and does not intersect any of the edges. The set of those points in a polygon that see every point of the polygon’s interior is called the kernel of the polygon. A
polygon is called star-shaped if its kernel is non-empty.
The kernel of a convex polygon is the whole of its interior.
2.6 Monotone Polygons
A simple polygon is called monotone with respect to a line l if, for any line l¢ perpendicular to l, the intersection of the polygon with l¢ is connected (i.e., the intersection must be a single line segment, or a point or empty).
A polygon that is monotone with respect to the x-axis is called x-monotone. An x-monotone polygon is composed of two monotone chains: the polygon’s upper chain and lower chain. Each chain terminates at the polygon’s leftmost and rightmost vertices. When an x-monotone chain is traversed beginning from its leftmost vertex, its vertices are visited by increasing x-coordinates.
A y-monotone polygon is also similarly defined with respect to the y-axis, and consists of two monotone chains: the left and the right chain. When a y-monotone polygon is traversed along one of its chains beginning at the topmost vertex, the vertices are visited in decreasing order of y-coordinates.
Note:
· The main advantage of monotone polygons is that they can be easily triangulated using a simple algorithm (to be discussed later).
· Monotone polygons can contain reflex vertices.
· A convex polygon is monotone with respect to any line.
· A star-shaped polygon need not be a monotone polygon (give an example).
2.7 Monotone Decomposition of Simple Polygons
In general, simple polygons need not be monotone and can have an arbitrary shape which is not self-intersecting. A simple polygon which is not monotone, can be split into a set of monotone polygons. Before an algorithm to accomplish this is presented, consider the following definitions:
· Merge vertex (): A reflex vertex which is greater than both its neighbors (in terms of x).
· Split vertex (<): A reflex vertex which less than both its neighbors (in terms of x).
Examples of these vertices are labeled in the figure below. Note that:
Vertex v3 is a merge vertex because it is a reflex vertex and has a x component greater than the x components of vertex v2 and v4, its neighbors (v3x > v2x and v3x > v4x).
Vertex v9 is a split vertex because it is a reflex vertex and has a x component less than the x components of vertex v8 and v10, its neighbors (v9x < v8x and v9x < v10x).
Fig.: A non-monotonic polygon with its merge and split vertices labeled.
Algorithm 1: A simple, but flawed, algorithm for dividing a simple, non-monotonic polygon into a set of monotone polygons:
Step 1: Sort its vertices in a lexicographic order along the x-direction.
Step 2: Connect every merge vertex to the next vertex in the sorted list.
Step 3: Connect every split vertex to the previous vertex in the sorted list.
Fig.: 5 monotonic polygons created from the non-monotonic polygon in the previous figure.
This algorithm performs correctly for many cases but it creates invalid diagonals (and therefore invalid sub-polygons) when the diagonal to the previous vertex intersects an edge. This can happen for both split and merge vertices. An example for a split vertex creating an invalid edge is show below:
This problem with the algorithm could be corrected in several ways. A "brute force" technique could test for intersections between the new diagonal and the polygon's edges, but this would be computationally expensive. Another approach is to recognize that the problem exists because a vertex from the "lower chain of vertices" is being connected to a vertex in the "upper chain of vertices." If a diagonal from a split or merge vertex was always connected to another vertex in the same chain, then we can guarantee that the diagonal will not cross an existing polygon edge. A modified algorithm using this approach follows:
Algorithm 2: Divide a simple, non-monotonic polygon into a set of monotone polygons:
Step 1: Sort its vertices in a lexicographic order along the x-direction.
Step 2: Create an "upper" and "lower" chain of vertices, where each list of vertices starts with the first vertex in the lexicographic ordering and ends with the last vertex in the lexicographic ordering.
Step 3: Traverse each "vertex chain" separately, doing the following:
a) Connect every merge vertex to the next vertex in its vertex chain.
b) Connect every split vertex to the previous vertex its vertex chain.
For example, this algorithm would do the following on the sample polygon below:
Step 1: v0, v1, v23, v22, v2, v21, v4, v20, v3, v19, v5, v18, v6, v7, v9, v8, v17, v15, v11, v16, v10, v14, v12, v13
Step 2: Upper chain: v0, v1, v2, v4, v3, v5, v6, v7, v9, v8, v11, v10, v12, v13
Lower chain: v0, v23, v22, v21, v20, v19, v18, v17, v15, v16, v14, v13
Step 3: Traverse each "vertex chain" separately, doing the following:
a) Merge vertices: connect v3 to v5; connect v10 to v12
b) Split vertices: connect v9 to v7; connect v15 to v17
Algorithm 2 Analysis: This algorithm is efficient and can be accomplished in O(N Log N) time as follows:
Step 1: Use a "quick sort" to sort its vertices. O(N Log N).
Step 2: Make one pass through the sorted list from step one. For each vertex, if its index is between the index of the first and last vertices in the sorted list, add it to the "upper chain", otherwise add it to the lower chain (Assuming a clockwise ordering of the points). O(N).
Step 3: Traverse each "vertex chain", connecting points as required. O(N)
In summary, a simple, non-monotonic polygon can be triangulated (divided into a set of triangles) using a two step process:
· Use the above algorithm to create a set of monotonic polygons.
· Triangulate each of the monotonic polygons.
2.8 Summary of Classification of Simple Polygons
The following diagram shows the relationships between the various types of simple polygons.
· A triangle is a convex, star-shaped, monotonic, simple polygon.
· A convex polygon is a star-shaped, monotonic, simple polygon.
· A star-shaped polygon is a simple polygon, but it may, or may not be, monotonic.
· A monotonic polygon is a simple polygon, but it may, or may not be, star-shaped.