Liduo - 3 years ago 144

C Question

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

Given a set of points, say:

`1 1 1 1`

1 1 1 1

1 1 1 1

1 1 1 1

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

`0 0 1 1 1`

0 1 1 1 1

1 1 1 1 1

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...

Callencodingany 2-dimensional array of size between between 2x2 and 50x50 (both dimensions can be different),

all of whose elements are either 0 or 1.

Callneighbourof a memberof an encoding any of the at most eight members of the array whose value is 1,`m`

and each of both indexes differs from's corresponding index by at most 1. Given a particular encoding, we`m`

inductively determine for all natural numbersthe set of polygons of depth`d`

(for this encoding) as follows:`d`

Let a

natural numberbe given, and suppose that for all d`d`

_{0}< d, the set of polygons of depth d_{0}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 Source

```
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").

Recommended from our users: **Dynamic Network Monitoring from WhatsUp Gold from IPSwitch**. ** Free Download**