How can I determine the perimeter of a polygon based on a collection of X,Y

I have a boolean[][] where the true indexes make up a solid polygon. With this information how can I

• A. determine which blocks make up the perimeter, and
• B. which points (in order) can开发者_StackOverflow社区 draw the polygon using the polygon class.

I intend to use Polygon class to call .contains but the code I have currently gives me the polygon points out of order (as i am simply scanning from left to right, top to bottom). Any help on the subject is appreciated.

I should think that you would just need to determine the corner points and connect them. A convex hull algorithm may not work because the polygon may not be convex. For instance, the third polygon from the left (the green one) on the wikipedia page for polygons is not convex. Also for polygons that are already convex a convex hull algorithm will likely be overkill.

Unless I am mistaken there should be four types of points in your list of Boolean values based on the status of the point's neighbors. In a regular grid an element at index i,j should have 8 neighbors. Based on these 8 neighbors you should have four different types of points assuming that your polygon does not touch any of the edges of the region:

1. Interior Points - Points which have all 8 neighboring values set to true
2. Interior Edge Points - Points which have a value of true and have 5 out of 8 neighbors set to true. These are points which are on the far edge of a polygon but not at the intersection of two polygon edges
3. Polygon Edge Points - Points which have a value of true and have fewer than 5 out of 8 neighbors set to true. These points occurs are the corner points of the polygon.
4. Outside Points - Points which have a value of false

You can go through your Boolean values and pick out all of the edge points for the polygon (you will have to take extra care in the case when the polygon is touching an edge of the region, for instance there is a true value at the smallest row and the smallest column). Once you have the edge points you determine which points connect to which by trial and error. Attempt to connect two points and see if the edge is valid. If the edge is valid then it will have all true values on one side and all false values on the other up to a reasonable margin or error. If it does not have this property then it must not be an edge of the polygon.

You're looking for a Convex Hull algorithm.

You need a couple of algorithms

First: a way to translate your boolean[][] into a set of X-Y coordinates.

Second: a way to convert those points into a polygon (read up on Convex Hull algorithm)

Third: a way to calculate the perimeter of that polygon.

Now go fill in the blanks!

It doesn't sound like a convex hull algorithm will be sufficient since the polygon might be concave. What you want is a bitmap to vector algorithm. Check out this link for a description of such an algorithm: http://cardhouse.com/computer/vector.htm

Once you've got the polygon points you can just do a distance calculation on each segment.