C Algorithm to determine the largest polygon out of a dot matrix

Question

Here's a question which annoyed me through the night.

Given a set of points, say:

the largest polygon is a 4x4 square. For this:

the largest is the trapezoid, but there will be irregular, and other variations...

How to determine the largest possible? (The largest means the one cannot be enclosed by any other polygon) What kind of algorithm should I use?

Also they need other attributes, like area, perimeter, convex(t/f), and number of invariant rotations...

This is provided in the instruction but I don't really understand what exactly it is about...

Call encoding any 2-dimensional array of size between between 2x2 and 50x50 (both dimensions can be different),
all of whose elements are either 0 or 1.
Call neighbour of a member
m
of an encoding any of the at most eight members of the array whose value is 1,
and each of both indexes differs from
m
's corresponding index by at most 1. Given a particular encoding, we
inductively determine for all natural numbers
d
the set of polygons of depth
d
(for this encoding) as follows:

Let a
natural number
d
be given, and suppose that for all d₀ < d, the set of polygons of depth d₀ has been determined.
Change in the encoding all 1's that determine those polygons to 0. Then the set of polygons of depth d is determined
as the set of polygons which can be obtained from that encoding by connecting 1's with some of their neighbours
in such a way that we obtain a maximal polygon (that is, a polygon which is not included in any other polygon
obtained from that encoding by connecting 1's with some of their neighbours).

Recommended for you: Get network issues from WhatsUp Gold. Not end users.

Answer 1

Create some integer B, set it to zero.

For every point p:
    If p has not been marked as "been":
        Mark p as "been"
        BFS/DFS from p and count the number of adjacent reachable points. Also mark each of these points as "been".
        If the number of reachable points + 1 is greater than B:
            B = the number of reachable points + 1

At the end, B = the maximum size of the polygon (in points "covered").

C Algorithm to determine the largest polygon out of a dot matrix

Sign up