Title

"Point Location"

Brief: Applet that visualizes the triangulation refinement method for answering point location queries

Author

Derek Bradley
100263753

Problem Overview

Given an embedding of a connected planar graph G with n vertices, and a point x in R², determine the face of G that contains x. This is one of the most basic problems in Computational Geometry, and it is called Point Location. What we need is a data structure to store G, such that for any query point x we can quickly find the face of G that contains x.

A basic application of this problem would be to consider a map of Canada, represented as a graph G, where the provincial borders on the map are the edges in G. The problem is then to process point queries (such as user-selected points or longitude/lattitude locations) and return what province contains the specified location.

Project Details

The project will be mainly split up over three areas: Documentation, Demonstration and Links & References.

The major part of the written work will be in the Documentation section, including the formal problem description similar to the problem overview above, the problem history, any related problems and solutions, and a formal description of the triangulation refinement solution.

The java applet to visualize the triangulation refinement solution will be in the Demonstration section. This applet will show each step of the solution (including pre-processing) in a visual way on a planar graph. The applet will allow the user to create their own planar graphs (one vertex and one edge at a time), navigate through each step of the algorithm (one step at a time), and change the location of the query point for each query. If the user attempts to create a non-planar embedding of a graph, the applet will display an error indicating that there are crossings in the graph and the crossing edges will be highlighted. It is then up to the user to modify the graph and make it planar before continuing.

The final section will wrap-up the project with the formal references used, and include a set of links to other related websites that discuss the point location problem in computational geometry.