Algorithms in a Nutshell

(^254) | Chapter 9: Computational Geometry
Today’s computers are sufficiently advanced that this no longer is an obstacle to
performance. However, Chapter 2 discusses important issues, such as round-off
error, relating to floating-point computations that impact the algorithms in this
chapter.
Finally, some computational geometry algorithms require the concept of an
interval over integer values, shown in Figure 9-3:
IInterval
Represents the semi-closed range [left,right) over integer values; that is, it
includes the valueleftbut not the valueright. It can determine its relation-
ship to a given integer value (whether to the left, to the right, or intersecting).
Each of these interface types is realized by a set of concrete classes used to instan-
tiate the actual objects (for example, the classTwoDPointrealizes both theIPoint
andIMultiPoint interfaces).
Computation
Computations in computational geometry are typically related to spatial ques-
tions, such as those shown in Table 9-1. There are three general task types:
Query
Select existing elements within the input set based upon a set of desired
constraints (e.g., closest, furthest); these tasks are most directly related to the
search algorithms discussed in Chapter 5.
Computation
Perform a series of calculations over the input set (e.g., line segments) to
produce a number of specific geometric structures that incorporate the
elements from the input set (e.g., intersections over these line segments). The
result of the computation task is the answer to the problem.
Preprocessing
Embed the input set in a rich data structure to be used to answer a set of
questions. In other words, the result of the preprocessing task is used as input
for a set of other questions.
Figure 9-3. Interface to represent interval [left, right)
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
Licensed by
Ming Yi