The traditional environment representation for footstep planning and collision detection for humanoid robots is the 2.5D height map. Although easy to compute and relatively space efficient, height maps have limitations that prevent a humanoid from achieving its full navigational potential in complex real-world environments, e.g., due to lack of explicit representaion of walkable surfaces. In this paper, we propose to represent planar surfaces with 3D polygons having explicit boundaries which significantly reduces the memory footprint required for a map. These 3D polygons serve as explicit representations of plan-able regions for a humanoid be it for footstep planning or hand or object placement for support and manipulation. We also use the aforementioned 3D polygons for robot localization within the map while it is being built from sensor data in real time. We hereby combine visual odometry techniques based on plane and edge registration with well-defined polygonal set operations to build an accurate and compact representation of indoor environments with a global ground plane. The result is a geometric map which not only provides an explicit bounded planar surface representation but also allows analytically computed collision and placement information. As our experimental results obtained with the Nao humanoid robot show, we are able to obtain 3D polygonal maps built over extended sequences of RGB-D frames while maintaining a reasonably efficient per frame run-time at an especially small memory consumption.