Visualizing Flip Graphs - by philippe ajoux and bobby prochnow

Source code: button flip_graph fgraph geom triangulation or Fork on GitHub

Built with Processing

Instructions:

  1. Place points by clicking on in the applet. You may move points once they have been places.
  2. The Delaunay triangulation of the points is created interactively as you add and drag points.
  3. Once you have entered enough points (MAX of 8) click on the "Generate Flip Graph" button.
  4. This will display a lifting of the Flip Graph for the given embedding of points.
  5. You can click+drag to rotate the flip graph.
  6. Focusing on a node will zoom in on that node. Pressing spacebar will defocus and zoom out.
  7. Clicking on a node will display the triangulation in the top left corner.
  8. The colors and heights of each node represent a given triangulation heuristic. To switch between heuristics, use the buttons in the lower left corner (or the keys 1, 2, 3).

Purpose:

The purpose of this applet is to explore the flip graphs of small triangulations. Specifically, we felt it would be interesting to visualize the "utility" of each node in the flip graph. The flip graph is displayed as a lifting with the height of each node defined by one of three heuristics: number of Delaunay edges, minimum angle, and flips to Delaunay. Being able to visualize the graph under different heuristics allows the user to further understand the structure of the flip graph.

Algorithms:

  • Delaunay Triangulation - We implement an O(n^2) Delaunay Triangulation algorithm (we did not implement the History DAG) which is run interactively while the user places points. Whenever a point is added or moved, the Delaunay triangulation should be updated.

  • Flip Graph Generation - A simple Breadth-First-Search is used to walk through all the possible edge flips in the triangulation. From this search we can generate the actual flip-graph.

  • Graph Drawing - A modified version of Tutte's algorithm (using simulated annealing) is used to draw the flip graph. Since the graph will be represented in a 3D lifting, edge crossings in 2D do not affect the 3D aesthetics as much. Sometimes the edge crossings are unavoidable - as large flip graphs are not planar in 2D, and other times, we purposely introduce them (when pinning the outer face) to create better vertex layout.

Getting the Code:

You can clone the project with Git by running:

$ git clone git://github.com/pajoux/CompGeom10

** Note - The number of points is capped at 8 not because of our triangulation algorithm. This is mainly a cap emposed so that the flip graph generated remains reasonably legible. With more than 8 vertices, the flip graph can become rather large and unmanagable.