Planar Graph Face Discovery

About

Given graph with the following properties;

1. The graph is undirected
2. The graph is planar
3. Each vertex in the graph has a defined (x,y) position

enumerate all of the faces of the graph. Can also be described as finding all of the polygons within the graph, or the minimum cycle basis.

That is from the following;

Determine the following closed regions;

Installation

npm install --save planar-face-discovery

Usage

1. PlanarFaceTree

This exposes the raw algorithm to find the faces of the graph.

Input

import { PlanarFaceTree } from "planar-face-discovery";

const solver = new PlanarFaceTree();

/**
 * Each node is defined by its [X,Y] position.
 * The coordinate system is oriented as such
 * 
 *  +y
 *   |
 *   |
 *   |
 *   |__________ +x
 *   
 * That is you should have your nodes exist in positive
 * XY space only, negative positions are not allowed.
 * 
 * The index in the array defines the nodes "id"
 */
const nodes: Array<[number, number]> = []

/**
 * Edges are defined by [source id, target id]
 */
const edges: Array<[number, number]> = []

const result = solver.discover(nodes, edges)

Output

The output of the algorithm is a set of trees, aptly named a "forest". Each tree will contain a cycle and/or child cycles

Trees can be converted to JSON via their toJSON method, an example output will look like

[
    {
        "cycle": [],
        "children": [
            {
                "cycle": [0, 1, 3, 0],
                "children": []
            },
            {
                "cycle": [1, 2, 3, 1],
                "children": []
            }
        ]
    }
]

With the cycle indicating the path of vertices for each enclosed shape or "face"

2. getAreaTree

Get the faces formed by the graph in a tree structure where each has an area attached which is calculated exclusive of the areas of its children.

The nodes and edges values are the same as described for PlanarFaceTree

import { getAreaTree } from "planar-face-discovery";

const result = getAreaTree(nodes, edges)

Output

{
  "type": "ROOT",
  "children": [
    {
      "type": "CHILD",
      "polygonIndex": 1,
      "area": {
        "total": 100,
        "withoutChildren": 40
      },
      "polygon": [
        1,
        4,
        5,
        7
      ],
      "children": [...]
    }
  ]
}

Acknowledgement

This module is a typescript port of the algorithm found in the Geometric Tools C++ library.

You can find a fantastic paper that explains the algorithm in detail in their documentation

You can also find this paper and a reference implementation from the library in the reference directory. The document may change in future so the versions stored in this repo are the ones that were used to write the code.

The implementation has been kept as close as possible to the original.

License

The original algorithm and by extension this code are released under the Creative Commons Attribution 4.0 International License