Geometric primitives are a compact and versatile representation of the environment and the objects within. From a motion planning perspective, the geometric structure can be leveraged in order to implement potentially faster and smoother motion control algorithms than it has been possible with grid- based occupancy maps so far. In this paper, we introduce a novel perception pipeline that efficiently processes the point cloud obtained from an RGB-D sensor in order to produce a floor-projected 2D map in the field-of-view of the robot where obstacles are represented as polygons rather than cells. These polygons can then be processed by path planning algorithms and obstacle avoidance controllers. Our pipeline includes a ground floor plane detector that performs significantly faster than other contemporary solutions and a grid segmentation algorithm that uses image processing techniques to identify the contours of obstacles in order to convert them to polygons. We demonstrate the performance of our approach in experiments with a wheeled and a humanoid robot and show that our polygonal perception pipeline works robustly even in the presence of the disturbances caused by the shaking of a walking robot.