# Get polygons points from an array of 0 and 1

I have an 2D array containing 1 for walls or 0 for empty cells.

I can draw my maze by iterating through the map, placing a wall when map[x][y] is equal to 1 but I want to get the points of the different polygon formed by the 1 in order to have minimum draw call.

But I'm not sure about the Maths and I don't know how to proceed.

Would you please give me some hint ?

• Programming games will need lots of math. You should study up on that: khanacademy.org/math/linear-algebra/vectors_and_spaces.
– House
Sep 9, 2013 at 13:48
• Yes I know ... I'm currently studying vectors with my character movements. Thanks for the link ! Sep 9, 2013 at 14:09

A simple to understand, but probably not optimal method is the following:

• Step through all elements of the array, starting at the top left.
• At each step, examine the current element and 3 of its neighbors: the one to its right, the one to its bottom, and the on to its bottom right.
• Check how many of the 4 elements have the value 1. If exactly 4 or 0, you don't have a point there. If 1 or 3, you have a point. If 2, and these two are in the same row OR in the same column, you don't have a point.

Some illustration:

Black means a wall, white means empty space. A,B,C and D are the elements of your array, e.g. [i,j], [i+1,j], [i,j+1] and [i+1,j+1]. The red dot shows where a polygon point must be created.

So go through the whole array, collect the points in a list (there will be many duplicate points, just don't add them or remove them later). Pay extra attention to the area near the boundaries of the array!

• Thank you for the hint ! I will try it soon and provide my feedback ! Sep 9, 2013 at 14:32
• Rather than iterating across the array in row/column order, you might instead prefer to follow the wall like a spider crawling along it: sticking to the barrier between 0 & 1, and turning corners when the passages do. This not only gives you the list of points you need, but also the order of traversal for turning them into edges & polygons for rendering. Each time you make a concave turn, you know it's time to make a split in your triangulation. May 22, 2018 at 16:48