Algorithms in a Nutshell

(^258) | Chapter 9: Computational Geometry
This computation requires O(n^2 ) individual executions of its core step. Deter-
mining the intersection between two line segments may involve trigonometric
functions or division, both computationally expensive operations; additionally, as
described in Chapter 3, such operations often introduce round-off error into the
resulting computation. We implement a more efficient technique that detects
intersections using only addition, subtraction, multiplication, and comparison
(Cormen et al., 2001).
It is not immediately clear that any improvement over O(n^2 ) is possible, yet this
chapter presents the innovative LINESWEEPalgorithm, which on average shows
how to compute the results in O((n+k) logn) wherekrepresents the number of
reported intersection points.
Figure 9-6. Brute Force Intersection fact sheet
Example 9-1. Brute Force Intersection implementation
public class BruteForceAlgorithm extends IntersectionDetection {
public Hashtable<IPoint, ILineSegment[]> intersections
(ILineSegment[] segments) {
startTime( );
initialize( );
for (int i = 0; i < segments.length-1; i++) {
for (int j = i+1; j < segments.length; j++) {
IPoint p = segments[i].intersection(segments[j]);
if (p != null) {
record (p, segments[i], segments[j]);
}
}
}
computeTime( );
return report;
}
}
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