Content area
Full text
ABSTRACT
There are many geometric problems that require carefully-designed geometric algorithms as their solutions. [1] This paper considers two such algorithms for map overlaying. [2] The first involves finding all cases where line segments in two sets of line segments intersect. The second finds whether there is an intersection in a set of line segments. Two different algorithms are presented to solve similar problems in this area of computational geometry, the first is implemented in Java, the second in C++. This material is appropriate for teaching introductory computer science students about identifying algorithms within programs, analyzing algorithm complexity, and illustrating how to leverage algorithms known to the field of computational geometry within programming projects that require students to utilize two or more algorithms in such a way that they work together in order to form a third algorithm.
General Terms
Computer Science Education, Map Overlaying, Computational Geometry.
Keywords
Java, Eclipse, Map Overlay, Computational Geometry Algorithms, C++, Visual Studio, Plane Sweep, Shamos Hoey.
(ProQuest: ... denotes formulae omitted.)
1. Map Overlaying
The basic idea of Map Overlaying is that geographic maps may be constructed in layers. Each layer conveys different information about the underlying geographic region. One layer may display roads, another rivers and canals, a third power lines, another subway lines or light rail tracks, yet another major sewer lines, and so on. The different map layers could also be more abstract, show things such as population density, income levels, or demographic data such as age or race. [3]
One question we may want to examine on a map of road systems and river and canal systems, is whether any two maps have segments that intersect, and if so, at what point on the map. More generally for any two or more map overlays, are there points at which the segments contained in the map intersect. If we represent the segments of the map as line segments, one algorithm is to take each pair of segments selected from different maps and check if they intersect and then determine where. This approach has a complexity of O nA2. [3]
2. Code for Line Segment Intersects [1]
import java.util.Scanner;
import java.awt.geom.Point2D;
import java.awt.geom.Line2D;
public class LineSegments2 {
/· Comments outlining structure and purpose of program.
1....