CODEWITHSUNDEEP
algorithmbinary-treepolygontriangulation
wondra
wondra

Reputation: 3583

How to convert binary tree to polygon triangulation and vice versa

According to wikipedia, there is bijection (1:1 correspondence) between binary tree of n - 2 nodes and simple n-vertex polygon triangulation. I am wondering, how to convert between each other*?
In other words, how to convert set of triangles to binary tree and how to convert binary tree to set of triangles? Triangle is ccw triplet of vertices (v0, v1, v2) and links neighbour triangles (n0, n1, n2).
* from programmer's view, an algorithm, code example etc.

Upvotes: 1

Views: 1365

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65498

Here's a recursive bijection.

The base case is that the degenerate 2-vertex polygon corresponds to the empty tree.

Inductively, the tree has at least one interior node. Assume that the vertices of the polygon have preexisting labels from 1 to n in clockwise order. Examine the unique triangle T that includes the edge 12.

   1-----2
  /|    /|\
 / | T / | \
6  |  /  |  3
 \ | /   | /
  \|/    |/
   5-----4

If we delete T, we get two triangulated polygons. In this case, we get 2345 and 156. Recursively biject the polygon including 1 to get the left subtree of the root. Recursively biject the polygon including 2 to get the right subtree of the root.

A particularly slick way to view this bijection is that we derive the tree by taking the planar dual graph of the triangulation, deleting the edges incident to the infinite face, and designating the face adjacent to 12 as the root.

Upvotes: 2

Related Questions