Hi
Is there any reason your cells cannot be perfect squares? If they could be perfect squares then you could simplify everything immensely.
Having a massive navmesh loaded at the same time isn’t actually a big deal if it is completely static. It just contributes to additional memory usage, but for just pathfinding (no updates) it should be just as fast.