# 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. – Byte56 Sep 9 '13 at 13:48
Yes I know ... I'm currently studying vectors with my character movements. Thanks for the link ! – Antoine Guillien Sep 9 '13 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 ! – Antoine Guillien Sep 9 '13 at 14:32