Algorithms in a Nutshell

Overview | 257

Computational

Geometry

by the angle formed with a vertical line. One must be careful when processing

collinear points.

The inefficiency of this approach is clear since it will require O(n^4 ) individual

executions of the triangle detection step. This chapter presents an efficient

CONVEXHULLSCAN algorithm that computes the convex hull in O(n logn).

Computing intersections from a set of line segments

Given a set of line segmentsSin a two-dimensional plane, determine the full set of

intersection points between all segments. One may also want to know if there is at

least one intersection (i.e., stop after reporting the first intersection). In the

example in Figure 9-5 there are two intersections (shown as small black circles)

found in this set of four line segments. The brute-force algorithm shown in

Figure 9-6 computes the intersections of the line segments inS using O(n^2 ) time.

Example 9-1 shows the implementation of BRUTEFORCEINTERSECTION. There

are C(n,2) segment pairs, or:

possible pairings. For each pair, the implementation outputs the intersection, if it

exists.

Figure 9-4. Sample set of points in plane with its convex hull drawn

Figure 9-5. Three line segments with two intersections

n

⎝⎠ 2

⎛⎞ nn()–^1

2

=---------------------

Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use