CODEWITHSUNDEEP
c#polygon
Cecer
Cecer

Reputation: 21

Find the largest polygon as it is completed

The Requirements
I'm not sure how to describe this so I'll give an example that should be easier to explain.

I have a small (maximum 50x50 pixels) 1bit/pixel bitmap (black and white).
Only one pixel is added at a time.
Find the largest (by area) polygon that exists using the black pixels as the edges.

The actual scenario isn't actually graphics related and uses a 2D Boolean array but the logic would be the same I imagine.

The Desired Behavior

The problem
I am not sure how to get the largest polygon when it is completed. I can do the filling if I can just get the polygon. In the above image I have highlighted the polygon that should be selected.

Upvotes: 2

Views: 723

Answers (3)

Cecer
Cecer

Reputation: 21

It turns out it was much more simple than I was expecting. I guess I was trying to make things overcomplicated. Because of the small dimensions and the fact that it will not run that frequently, speed is not a really an issue.

I don't have access to exactly how I did it right now but this is the general idea.

Each pixel is stored as an instance of SomePixelType.
There is a Stack<SomePixelType> of pixels called visitedPixels. A pixel is considered a possible polygon edge if:

  • It has between 2 and 7 (both inclusive) black neighbouring pixels.
  • It is not in the visitedPixels collection.

SomePixelType has a method named GetNextPixel.

When GetNextPixel is called it will search neighbouring pixels (starting directly up and going clockwise) for a possible polygon edge and return it. Calling it again will continue searching from the last match. Once all neighbouring pixels have been checked it will return null.

When a pixel is set this method would be called.

public Stack<SomePixelType> GetPolygonEdges(SomePixelType justSetPixel)
{
    visitedPixels.Clear();

    if(!justSetPixel.IsPossiblePolygon)
        return null; // Not a possible edge. No closed polygon could of been completed.

    visitedPixels.Push(justSetPixel);

    SomePixelType currentPixel = justSetPixel;
    while(visitedPixels.Count > 0)
    {
        currentPixel  = currentPixel.GetNextPixel();
        if(currentPixel == null) // No possible neighbouring polygon edges.
        {
            currentPixel = visitedPixels.Pop(); // Backtrack
            continue;
        }
        if(currentPixel == justSetPixel)
            return visitedPixels;

        visitedPixels.Push(currentPixel);
    }
    return null; // Not closed.
}

From here on it is fairly easy to fill in. As the question was about finding the polygon I will stop at this step.

Upvotes: 0

Ken Cheung
Ken Cheung

Reputation: 1808

Be aware that you need to ensure the polygon is "closed". There should be an algorithm named "snake" that helps you, but I heard about this 14 years ago, better have a search...

Upvotes: 0

ColinE
ColinE

Reputation: 70122

It sounds like you need a flood fill algorithm of some sort, see related StackOverflow questions:

Flood Fill Algorithms

You can use your flood fill as a way to perform segmentation, i.e. split the image into discrete 'objects' composed of connected pixels. The flood fill will also give you the number of pixels within each object allowing you to find the largest. See also the Wikipedia page on Segmentation, specifically the region-growing method:

http://en.wikipedia.org/wiki/Segmentation_(image_processing)#Region-growing_methods

Upvotes: 1

Related Questions