Friday 8 March 2013

Algorithm for Dividing a 2D Space into Convex Polygons

I'm writing this down mainly as an aide-mémoire, and because I can't find the solution online anywhere - I can't imagine it isn't out there, because I'm trying to solve a fairly basic problem, so I'm possibly using the wrong terminology in my search.

In any case, I have a simple engine for moving a player character round a 2D game map which is split into convex polygons/cells linked by portals/doors; I'm also working on a game that, in essence, allows a player to build and walk round their own spaceship. To fit these two together, I need an algorithm that will take the outline of an area of the ship (itself a convex polygon), a set of walls that the player has added (straight edges within that area) and divide the outline into a set of convex cells such that none overlap a wall, and that any edges between cells that are not walls are marked as portals between them.

My five-minute, scribbled on a PostIt note algorithm is:

  • Every wall lies along a line that bisects the outline area into two parts. Filter out all walls that bisect the area such that any other wall overlaps both parts.
  • For each remaining wall, select the set of walls that most evenly divide the other walls (from the full set) between the two parts.
  • Pick a wall at random from that set and split the outline area into two new areas, adding portals along the dividing line where appropriate, and group the remaining walls from the full set into each area.
  • Repeat this algorithm for both new areas with their reduced wall set.
Notes:
There are two special cases - where two walls are in line with each other, and two walls directly intersect. The latter case is probably easiest to prohibit, and the former case is handled by only including one of the two walls in the selection process, but remembering to include the second wall as a non-portal edge when splitting the area.

No comments: