Area Perimeter

I have a two dimensional array with some of the elements marked, in essence like the image below. I want to calculate the points needed to draw an outline around the marked elements. In this case it would be (2,2),(1,2),(1,3),(1,4),(2,4),(3,4),(4,4), etc.

Using a flood fill I can put together a set of elements are on the line, either inside touching, or outside touching, however, the elements will be in an pseudorandom order, rather than in-order going around the perimeter.

Does anyone know of a good to find the perimeter in this situation?

From your list of points on the perimeter, find the coordinates where the x and y values *both* differ NOT from the previous points values, but from the point before that.

It's a "not tonight, but the night before", kind of thing, but with points coordinates.

OK, you're at a point, the x and y values are BOTH different than they were two points back. So you're NOT at a corner now, but your point one back (which will NOT have values that differ in both x and y from their adjacent points), is the corner point. Work it out on your diagram if you don't believe me. :D

Another way to view it is when you find a point where one coordinate (say X for example), has been changing, and now the Y coordinate value starts to change, and the X value is not changing, then you have just gone PAST the corner - so go back one point.

Putting your x and y values into an array of structs with x and y int's in it, is a nice way to keep things organized, imo.

I don't have a list of perimeter points, I have a list of elements (squares) from my 2d array that are touching the perimeter, and they are not in-order because I am using a recursive method to find them, so a square from one side may be followed by a square from the other side (in theory; not so much for this area, but if it were E shaped),

I had an idea that I could compare the sides of every square outside to those inside. If two squares share a side, then that side must form part of the perimeter. That seems somewhat inefficient though, I feel like there must be a better way. But maybe it doesn't really matter.

Seems to me this would be easier if you had all the squares that make up the shape. Then you could go through that list of squares, and count how many edges of each square are not shared with another square in the shape. Here is a graphical representation of the example you gave:

Code:

---

.......
.xxxxx.
.x212x.
.x201x.
.xx22x.
.xxxxx.
.......

---

I have used a . to mean squares of no significance, an x to symbolize the points you were given, that lie on the outer edge of your shape, and a number to represent the "perimeter value" of each square. Corners contribute 2 units to the perimeter, edges contribute 1 unit, internal shapes contribute 0, etc.

I hope that gets you going in the right direction.

Your squares should be in order, so you can "walk" the perimeter of your shape.

If the word "point" doesn't appeal to you, just replace it with "square". Same concept, whatever the name being used. No difference at all.

Quote:

---

Originally Posted by anduril462

Seems to me this would be easier if you had all the squares that make up the shape. Then you could go through that list of squares, and count how many edges of each square are not shared with another square in the shape. Here is a graphical representation of the example you gave:

Code:

---

.......
.xxxxx.
.x212x.
.x201x.
.xx22x.
.xxxxx.
.......

---

I have used a . to mean squares of no significance, an x to symbolize the points you were given, that lie on the outer edge of your shape, and a number to represent the "perimeter value" of each square. Corners contribute 2 units to the perimeter, edges contribute 1 unit, internal shapes contribute 0, etc.

I hope that gets you going in the right direction.

---

This is what I did and it ended up working good. Thanks,