Weighted Terrain Meeting Point

2015-11-20 00:00:00 +0000

Overview

This project was part of the course EECS 495, Computational Geometry, at Northwestern University. The goal of the project was to implement an algorithm to calculate the meeting point of scattered robots on weighted terrain surfaces, based on the algorithm detailed in this paper by Mark Lanthier, Doron Nussbaum, and Tsuo-Jung Wang.

The algorithm consists of three main parts:

  • Calculating the Delaunay triangulation for a set of points in 3D space.
  • Constructing a graph of Steiner points and edges at ten per edge of the original triangulation.
  • Invoking a shortest path algorithm from each of the source vertices on which the robots are positioned. The algorithm is modified as a multiple-source single-target variation such that the algorithm stops at some vertex which is the approximating meeting point.
    •

    All of the code for this project is hosted on this page.

    The triangulation of a sample terrain:

    Two examples of found meeting points for robots starting at random vertices. The contour map is shown with the start locations of each robot displayed as a circle of the robot’s color, each robot’s path in a different color, and the calculated meeting point shown as a black circle.