Spatial graph

Definition

The spatial graph describes the shape of spaces, as well as their adjacency and connectivity. Edge elements and boundary elements reference edges.

Planar graph

Under the hood the spatial graph leverages the concept of a planar graph. A graph with nodes and edges where the nodes have positions and therefore a loop of edges creates a face. Adopted to spatial data the graph face is a space and the edge is a wall.

Adjacency

The direct result of two spaces sharing the same edge is that they are adjacent. This requires no further computation and is always the ground truth.

Connectivity

Connectivity of spaces is defined by taking adjacency and the element that references the edge into account. If an edge is simply a space divider or a wall with a door opening is on that edge the spaces on each sides of the edge are connected.

JSON example

The spatial graph is in 2d space. Using the x and z axis.
See coordinate system.

//  (v1)--e1--(v2)--e5--(v5)
//   |         |         |
//   e4   s1   e2   s2   e6
//   |         |         |
//  (v4)--e3--(v3)--e7--(v6)

{
  "spatialGraph": {
    "vertices": [
      { "type": "spatialGraph:vertex", "id": "v1", "position": [0, 0] },
      { "type": "spatialGraph:vertex", "id": "v2", "position": [2, 0] },
      { "type": "spatialGraph:vertex", "id": "v3", "position": [2, 2] },
      { "type": "spatialGraph:vertex", "id": "v4", "position": [0, 2] },
      { "type": "spatialGraph:vertex", "id": "v5", "position": [4, 0] },
      { "type": "spatialGraph:vertex", "id": "v6", "position": [4, 2] }
    ],
    "edges": [
      { "type": "spatialGraph:edge", "id": "e1", "vertices": ["v1", "v2"] },
      // e2 is the shared edge
      { "type": "spatialGraph:edge", "id": "e2", "vertices": ["v2", "v3"] },
      { "type": "spatialGraph:edge", "id": "e3", "vertices": ["v3", "v4"] },
      { "type": "spatialGraph:edge", "id": "e4", "vertices": ["v4", "v1"] },
      { "type": "spatialGraph:edge", "id": "e5", "vertices": ["v2", "v5"] },
      { "type": "spatialGraph:edge", "id": "e6", "vertices": ["v5", "v6"] },
      { "type": "spatialGraph:edge", "id": "e7", "vertices": ["v6", "v3"] }
    ]
  },
  "spaces": [
    {
      "type": "layout:space",
      "id": "s1",
      "boundaries": [{ "edges": ["e1", "e2", "e3", "e4"] }]
    },
    {
      "type": "layout:space",
      "id": "s2",
      "boundaries": [{ "edges": ["e5", "e6", "e7", "e2"] }]
    }
  ]
}