Automatically navigation graph creating [closed]

Question

I am recently intrestring in Indoor Mapping, and I came across Mappedin, whose innovative work particularly their data format and SDK impressed me. One of the features of Mappedin is its capability to support real-time wayfinding updates as the map is being created. This means that any modifications to your map such as adding a new room or adjusting doorways result in immediate updates to the wayfinding functionality. I encourage you all to explore Mappedin Studio to gain hands-on experience in creating your own maps.

I'd like to know how the magic happen. Based on the Data Model, it appears that the Node layer plays a critical role in facilitating wayfinding. Mappedin offers several demo maps for experimentation, and I chose the "School demo" for my research. In this scenario, it becomes evident that wayfinding computations occur on the client-side. By extracting the map data and rendering them using MapLibre GL, I was able to visualize the green points representing nodes from the map, each interconnected with its neighbors via green lines. The gray areas denote rooms, red points signify doors, black zones indicate obstructions such as desks or other objects, while the white spaces represent hallways. A blue line illustrates an example of a calculated route.

It seems clear that the nodes form a navigation graph upon which pathfinding algorithms, such as A* or Dijkstra, can operate effectively.

With that said, I have two questions that I'm eager to address:

1. Automated Graph Generation

How can one automatically generate a graph (comprising nodes and their relationships) that accurately represents walkable spaces?

1. Path Precision

Why doesn't the resulting path precisely follow the graph nodes?

In a graph-based navigation system, the identified path should consist of graph nodes and edges, with each edge's vertices being adjacent. However(see image below), as depicted, segment AB consists of nodes A and B, which are not directly connected within the graph.

This appears to be an area for potential enhancement.

Any idea how to implement this?

Answer 1

This is more a comment than an answer. It seems that graph based on a regular points:

will produce more realistic path:

compared to skeleton approach. Shortest path not necessarily goes in the middle between obstacles.

Even simplest triangular tessellation with much bigger space between nodes:

produces good looking results:

Importantly, tessellation is significantly easier calculation compared to skeleton.

Answer 2

1. Automated Graph Generation

---

This is most likely based on voronoi polygons. Similar to how centerlines are typically created. You can find some inspiration on this in pygeoops.centerline

2. Path Precision

---

Most likely the original path followed the original graph/nodes, but to get a cleaner result I think a simplify function was applied to the "raw" result.