Below is a clear comparison of community-detection algorithms relevant to your use case, followed by why triangulation is such an effective graph construction for spatial layouts like floor plans.
I’ll keep this grounded in why your results improved, not just theory.
All of these operate on graphs, not raw geometry.
Best default choice
How it works
- Optimizes modularity (dense internal connections, sparse external ones)
- Greedy and hierarchical
Strengths
- Fast (scales well)
- Automatically finds number of communities
- Works very well on spatial graphs
Weaknesses
- Can produce slightly unstable results (depends on initialization)
- Sometimes merges small adjacent rooms
Why it works well here
- Rooms are dense subgraphs
- Doors create weak inter-room connections
- Modularity captures this perfectly
✅ Excellent for triangulated floor plans
⚠️ May merge very small spaces
Improved Louvain (often better)
How it works
- Same modularity objective
- Enforces community connectivity (no disconnected fragments)
Strengths
- More stable than Louvain
- Produces cleaner room boundaries
- Avoids broken or fragmented communities
Weaknesses
- Slightly slower than Louvain (still very fast)
Why it works well here
- Ensures each “room” is internally connected
- Better for complex layouts with alcoves or narrow passages
✅ Often the best choice for architectural layouts
Mathematically elegant, but fragile
How it works
- Uses eigenvectors of the graph Laplacian
- Clusters nodes in spectral space
Strengths
- Theoretically strong
- Captures global structure
Weaknesses
- You must predefine number of clusters
- Sensitive to noise
- Computationally expensive for large meshes
Why it’s weaker here
- Floor plans rarely have a known number of rooms
- Narrow connections (doors) distort eigenstructure
⚠️ Better for research than production in this case
Flow-based interpretation
How it works
- Models random walks on the graph
- Communities minimize description length of paths
Strengths
- Very good at detecting corridor vs room separation
- Sensitive to bottlenecks (doors)
Weaknesses
- Can over-segment large rooms
- Less intuitive to tune
Why it can work
- Doors act as flow bottlenecks
- Corridors naturally emerge as connectors
✅ Useful if circulation is important
⚠️ May split large open galleries
| Method | Uses topology | Handles walls | Needs parameters |
|---|
| K-Means | ❌ | ❌ | Yes |
| DBSCAN | ❌ | ❌ | Yes |
| Louvain | ✅ | ✅ | No |
| Leiden | ✅ | ✅ | No |
| Infomap | ✅ | ✅ | No |
image_group{“query”:[“floor plan triangulation mesh”,“triangulated floor plan graph”,“delaunay triangulation floor plan”],“num_per_query”:2}
When you triangulate the walkable area:
- Triangles do not cross walls
- Connectivity only exists where movement is possible
This turns geometry into navigability.
Triangulation gives you:
- Uniform local connectivity
- High edge density inside rooms
- Narrow connections at doors
This creates:
- Strong intra-room connectivity
- Weak inter-room connectivity
Which is exactly what community algorithms look for.
In a triangulated mesh:
- A door may be represented by only a few edges
- Those edges have high betweenness
- Community algorithms tend to cut there
You never explicitly model doors — they emerge.
| Graph type | Problem |
|---|
| k-NN | Connects through walls |
| Radius graph | Sensitive to thresholds |
| Grid graph | Axis-biased |
| Triangulation | Respects geometry & topology |
Triangulation adapts to shape, density, and enclosure automatically.
Humans perceive rooms as:
- Enclosed regions
- With limited access points
- Internally well connected
Triangulation + community detection reproduces this without heuristics.
You didn’t just add topology — you changed the problem from “distance clustering” to “connectivity segmentation.”
That shift is why the results suddenly look architecturally correct.
If you want, next we can:
- Compare triangulation vs medial axis vs visibility graphs
- Discuss multi-level communities (rooms → zones → buildings)
- Explore weighted edges (door width, visibility, distance)