Computer Aided Engineering Design

280 COMPUTER AIDED ENGINEERING DESIGN

xxxx

yyyy

zz z

t

s

xx

yy

zz

B ACD

B ACD

B ACD

CA

CA

CA

• –


• –


• – z

=

⎡

⎣

⎢

⎢

⎢

⎤

⎦

⎥

⎥

⎥

⎡

⎣

⎢

⎤

⎦

⎥

⎡

⎣

⎢

⎢

⎢

⎤

⎦

⎥

⎥

⎥

Ifs or t∉ [0, 1], then d = min (| AC |, | AD |, | BC |, | BD |). Note that for a unique solution of [ts]T,
the respective coefficient matrix should not be singular. That is, AB or CD should not represent a
point or ABandCD should not be parallel.

9.3 Relation Between a Point and a Polygon

A closed polyline or polygon can be a representation of many planar objects. A polygon is an area
enclosed by a series of lines connected end-to-end. The convention is to traverse through the boundary
lines in the counterclockwise fashion. This ensures that the area immediate to the left of any line
(Section 9.1) is interior to the polygon (Figure 9.5a). A polygon is said to be convex if a line joining
any two points within the polygon lies completely inside it. For computational check, in a convex
polygon, at any vertex, the edges loop counterclockwise. The concave vertex in a non-convex polygon
has the edges looping clockwise (Figure 9.5b).

9.3.1 Point in Polygon

For any given polygon, one way to find whether a point is inside it is the Jordan’s curve theorem (see
Chapter 8). An alternate description is that a point is inside a polygon if, for any ray from this point,
there is an odd number of crossings or intersections of the ray with the polygon’s edges (Figure 9.6).
This requires a crossings test as follows:
A ray is shot from the test point along a specified line (+X is commonly used) and the number of
crossings is computed. For odd number of intersection points, the point lies within the polygon, else
outside. If the test ray passes through any vertex of the polygon, the test point is shifted up or down
by a very small distance and the new ray is intersected (Figure 9.7).
The algorithm returns the status of the test point as either ‘in’ or ‘out’ of the polygon. Before the
crossings test, the point in query is tested whether it lies on the polygonal boundary or not in two
stages: (a) the test point is compared with the vertices for coincidence and (b) if it does not coincide
with any vertex, then it is tested for its belonging on the polygonal edge. The area of the triangle made
by the point and the end points of an edge is computed for the purpose (Section 9.1).
Convex polygons can be intersected faster due to their geometric properties. A point lies inside the

Figure 9.5 (a) A convex polygon and (b) a non-convex polygon

(a) (b)