Polygon reduction while drawing on Map

Today we are drawing polygons on a MKMapView. We use the following pseudocode to draw polygons.

CGContextMoveToPoint
CGContextAddLineToPoint
CGContextAddLineToPoint
CGContextAddLineToPoint
CGContextClosePath
CGContextFillPath

The result could pote开发者_JS百科ntially look like this:

We get the data one row at a time, the colors are given to the cell based on the data we receive. Is there a way or polygon reduction algorithms that would group all the same colored polygons together (assuming they intersect) to give me one big polygon? So in this example all the reds would one big polygon.

CoreGraphics can handle concave polygons natively, so the main part of the problem is a flood fill to work out the boundaries of the filled area.

Thinking extemporaneously, a naive algorithm could be to associate edge flags with each cell. An edge flag is set if that edge is part of the exterior of the polygon. Flags are shared by the two cells that meet at that edge.

Pick any cell and set all four edge flags. Reset the edge flags on all other cells. Then write a recursive method that, for each cell:

• tests in turn whether each edge flag is set;
• if a flag is set, checks whether the cell that shares that edge is of the same colour;
• if it is, inverts the edge flags of that cell and recurses to it.

The inversion is the same as saying "connect to any cells you're known to be next to, set any edges that are next to cells we haven't looked at yet to be part of the boundary".

The recursion could get hundreds of items deep, so it might be worth keeping a list of cells to consider and adding to that list rather than recursing, just as a matter of implementation. It shouldn't matter what order you visit the cells in, so the outcome should be the same.

Once you've run out of cells to visit, you can reconstruct the entire boundary by walking around it from any flagged edge. The only slight complexity will be when you get to a diagonal meeting of cells, like where the yellow and green cells touch between your fourth and fifth columns. You need to apply the logic that you move from the current edge to the next one with which it shares both a vertex and a cell of the correct colour.

This is a job for the rectangle drawing functions, not the path drawing functions. See CGContextFillRect(), CGContextStrokeRect() and CGContextFillRects(). They will be much faster.