Quad Edges / Contour Lines

As a course project in GIS, I implemented an algorithm for generating and displaying contour lines of Triangular Irregular Networks) TINs.  The TINs were stored in a Quad-Edge data structure which I also implemented.  This work was part of a larger project with three other members who implemented Delaunay Triangulation, 3D display and interfacing, additional contour display.  Unfortunately, I have no screen snapshots.

A Neighbourhood Modelling Environment

The NEMO openning title screen

The Paradigm Group at Carleton university is involved with the development of various GIS applications.  Being a member of this group, I helped in the development of NEMO.  I was responsible for the user interface and display functions for all applications that are implemented using the NEMO environment.  For more information, see the Paradigm Group homepage.

Shortest Paths in a TIN

In many situations we need to determine a path between two locations that satisfies some condition.  For instance, when a plane crashes in the mountains, it is important to get from the rescue station to the "crash site" in the least amount of time.  In addition, the rescue team may want to avoid steep slopes or avalanche-prone areas.  Thus, we need a "plan" for reaching the crash site.  Path planning and analysis finds its way into many areas such as search and rescue, robotics, planet exploration, road construction and design, orienteering, waterflow analysis, hiking and sight-seeking, traffic control, navigation, etc..
Snapshot of shortest paths on a TIN

For my Ph.D. thesis, I studied the problem of determining the minimal cost path between two points on a terrain.  I have investigated many techniques for solving this problem:

- Approximation algorithms
- Practical and theoretical (epsilon approximation) algorithms
- Different cost metrics (shortest weighted paths, minimal energy paths etc...)
- Parallel simulations (allows larger terrains, faster computation time)
Here are some images showing the minimal energy paths on some simple terrains:

'
These paths take into account turning constraints.   Without these constraints, the path may zig-zag (kinda like skiing).   Here are some more images (topdown and isometric) showing how the path looks without the turning constraints.   Note that the yellow portions of the path indicate a zig-zagging portion of the path:

 
The decision as to when to zig-zag is based on certain inclination angles of the terrain faces as well as properties of the vehicle itself.   For each face, as set of directions must be computed which correspond to impermissible angle directions (shown cyan) and braking directions (shown red):
For our parallel implementation, we divide up the terrain into rectangular regions and assign the regions to different processors in a "nice" way.   The image below shows a top-down view of a terrain.   The similar-coloured edges will be assigned to the same processor:

Once divided among processors....we compute the path.   Here are some snapshots showing the results in 3D of propagating from a single source:
 


 

 
Just for fun, here are some more images....this time...showing shortest paths on some non-convex polyhedra: