Welcome

Welcome to the website for my final project for "5008 Computational Geometry" at Carleton University.

This project is a dynamic, interactive visualization of the triangulation refinement method for answering point location queries.

Ok, so what does that mean?

Basically I will show you, step by step, a very cool algorithm that takes a point in 2D and tells you what region of a 2D planar graph the point lies in.

How is that useful?

Well imagine you're looking at a map of Canada and you click on Ontario. Sure YOU can easily see that you've clicked on that region, but the computer knows nothing more than the (x,y) co-ordinates of the point you clicked on and a bunch of vertices and edges representing the graph that is the map. This project explains one algorithm that can happen behind the scenes to determine (very quickly) which region you have clicked on.

Site Breakdown

• Main - Obviously that's where you are now.
  
  
• Proposal - This is the formal proposal for my project, to be approved by my professor.
  
  
• Documentation - This is a textual section that includes a formal description of the problem, the history of the problem, related topics, and a description of the solution algorithm that I have chosen to visualize.
  
  
• Demonstration - This is the section you don't want to miss! Here you will find a java applet that visualizes the point location algorithm step by step (from pre-processing to final result) and you can interact with the applet to help fully understand how things work.
  
  
• Links & References - This section contains the formal references for this project, plus some links to other websites that contain information about this problem and/or solution.