Mesh algorithm for setting up indoor locations
The whole Indoorway team strives to simplify the process of setting digital maps and make it easy for our clients. We do our best to keep the tools simple for users. But making such advanced mechanisms intuitive and effective takes a lot of testing, brainstorming and coding.
Recently we stumbled upon a problem of creating a navigation mesh. For a given building plan we had to generate a grid of evenly distributed points connected with each other. Sounds like a piece of cake? Well, this story proves it was not that easy.
For our purposes the algorithm had to:
- Calculate mesh edges to be “as parallel as possible” to the building walls
- Each node had to cover the area of around 1 square meter
- Be universal for any type of building or space plan
This problem concerns different geometric objects and operations. As the saying goes “A picture is worth a thousand words”, so we provided images to let you understand our considerations and solutions better.
Our ideas
Uniform grid
The simplest idea that came to our minds was to cover the space with a regular orthogonal grid and to cut it to the size and shape of a given building plan. By doing so, we would meet the requirements of the second condition, but as you can see on the image below, there was a problem with the first one. With simple geometric figures, like squares or polygons, the basic grid behaved well. However, by applying this idea on curved shapes, like semi-circles or ovals, we didn’t achieve the parallelism-to-walls condition.
Unstructured mesh — polygon triangulation
Another proposition was to use a polygon triangulation algorithm to place single nodes in the center of each triangle and obtain almost equal distance between each of them. Unfortunately, one of the conditions wouldn’t be met. As mentioned in Wikipedia:
Unstructured Grid — An unstructured grid is a tessellation of a part of the Euclidean plane or Euclidean space by simple shapes, such as triangles or tetrahedra, in an irregular pattern.
Thus, nodes would be distributed equidistantly, but placed irregularly in more complex geometries (not parallel to walls). The pattern is presented in the image below.
Structured mesh — curvilinear grid
We continued our research of other solutions and meshes. The most promising was a curvilinear grid, which is used in large-scale oceanographic modeling. It aligns to curves in a desirable manner, but unfortunately the spacing between junctions is too small in narrow areas (Pic.3).
As we couldn’t find any suitable off-the-shelf solution, we decided to develop our custom algorithm, which would successfully meet all the demands.
Indoorway custom algorithm
Our approach was to split the problem into two parts, having in mind our requirements at each step. We focused on parallelism to the neighboring wall and maintaining equidistance between each generated node.
Generating inner layers
We started with the parallelism constraint. To achieve that, we took each edge of the polygon and translated them to the inside of the shape. Then, we detected where these moved lines intersected and created a new polygon based on intersection points (Pic. 4).
That’s how we created a new smaller polygon with edges parallel to the their “ancestors”. Also, we repeated this step until the edges of new polygons passed centroid of the previous polygon (Pic. 5). Furthermore, for the next step (nodes generation) we needed to reference the edges of newly created sublayers to their “ancestors” edges.
Generating nodes on layers
Another challenge was to generate nodes on the base layer and previously created sublayers. We started with creating junctions along each edge of the outer polygon, distributing them with 1 meter space from one another. Then, at the generated junctions we drew abstract lines starting from junction and finishing at the center of shape. In this way, we obtained other nodes on intersections with abstract lines and previously generated sublayers. Note that we only select the intersections that occur on “descendant” edges of the base edge.
For the sake of brevity, we present only nodes of the left wall with their corresponding abstract lines and intersections with sublayers.
The last thing to do was connecting neighboring points to create a graph.
While testing the algorithm on more sophisticated shapes like this one…
…we found out our algorithm didn’t work as expected (to be honest, it did not work at all in the example presented above). So, we started improving our algorithm to make it work properly in such cases.
Splitting concave polygons
Instead of tweaking our algorithm to work with concave polygons, we decided to add an extra step which detects concave shapes first, and then divides them into set of convex ones. Bearing in mind our needs, we developed a partitioning algorithm to create new polygons — as orthogonal as possible. The idea was to find a “view angle” of each concave vertex. Then for each segment within a view find a vertex projection. If the projection exceeds the target segment, we collect the segment endpoint closest to this projection (Pic. 8).
Otherwise, we collect projection (Pic. 9).
From the set of collected points we select the one with the angle between the vertex, the point and the segment closest to the right angle. We split the polygon along that line.
Dealing with holes
To manage polygons with multiple holes, we take a similar approach as with the concave polygons partitioning. The difference is that we start the whole process from iterating over convex vertices of the inner hole, because convex vertices in inner polygons are concave for the surrounding one. Then we designate the cutting lines in the same manner as before and split our polygon to the set of polygons without holes.
For each of the polygons we use our standard algorithm for detecting concavity, generating layers and nodes.
Merging nodes
We encountered another issue when testing our idea (not a surprise at all). The problem was that in some particular cases we were generating nodes in too close proximity to each other. The simplest solution that came to our minds was to merge close points into one by calculating their midpoint.
The final result of these operations is as follows:
Summary
To sum up, the final algorithm is capable of doing these five tasks:
- Detect holes, and if they exist, find their cutting edges
- Check if the outer polygon has concave points. If it does, the algorithm resolves cutting edges
- Generate layers for each created convex polygon
- Create nodes on each layer
- Merge nodes, if they are in close proximity
We developed this solution by testing multiple complex shapes on each step and trying to break the algorithm. The final method still requires some improvements and will be further developed, but for now it satisfies our current needs. All in all, it was really fun and challenging to develop a custom mesh algorithm.
