[Algorithms] zone/portal partitioning

[Oskar L. <osk...@me...>]

Hi,

I've got a small problem regarding partitioning of polygons into
zones separated by portals.

Say, I have two sets of polygons of which one set contains the 
geometry and the other set contains portals. I want to partition
the geometry set into disjoint subsets, zones, to be connected by 
portals.

I guess this problem doesn't have a solution for the general case, 
but if I can assume some kind of continuity between the geometry-
polygons, i.e. the polygons might form one or a few meshes making
up rooms and corridors, there should be cases where this problem is
solvable.

This is what my current solution method looks like:
1) Build an adjacency graph of the geometry-polygons, i.e. each
   node is a polygon and graph-edges correspond to shared edges. 
2) For each portal, cut the graph at the edges that match those of
   the portal. 

This should result in a lot of subgraphs. The polygons of subgraphs
that are the result of portal cuts can easily be assigned to zones,
but what of the other subgraphs?

These subgraphs could be other geometry, that is no part of a 
continuous wall-ceiling-floor-mesh. How do I choose which zone 
these polygons should belong to? Polygons that intersect portals 
could be forbidden or maybe clipped and I guess I could do some kind 
of intersection testing between the volumes made up of the current 
zones and the unassigned polygons, but this seems rather untrivial.

Before trying to do this the hard way, I would like to know if there 
are any better or more general algorithms for this last part or for 
the entire problem.


Hälsningar,
  Oskar Linde