CODEWITHSUNDEEP
c#arraysunity-game-engine2d
Caius Eugene
Caius Eugene

Reputation: 855

Finding outer edge of grid islands

I'm attempting to compute the outer edges of islands on a grid. Each grid tile has 4 vertices which make up the corners, I want to compute the edge in a clockwise direction so that it is ordered.

My grid is a 2D byte array byte[,] grid and I can easily find the neighbour tiles, however I'm struggling to find a solution for finding the edge of the islands.

0 0 0 0 0 0 0 0 0
1 1 1 0 0 0 1 1 0
1 1 1 0 0 0 1 1 0
1 1 1 1 1 0 0 0 0
1 1 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

In this image the red dots represent vertices and the green line in the bit I'm trying to find.

enter image description here

Does anyone has any idea's on how this can be achieved?

Thanks, C.

Upvotes: 3

Views: 3098

Answers (2)

Tom
Tom

Reputation: 627

basically this:

1) check every square if its filled or not

2) if its filled check the neighbours

3) for each neighbour that is free add the line to a list between this square and the neighbour

you end up with a list that contains the complete border as separate pieces. Now you need to play domino with this list so that you get the borders of all islands as separate ordered lists where the last piece should perfectly fit onto the first. then you can even do some cleanup in the lists by adding up line pieces that go in the same direction.

Upvotes: 2

Jias
Jias

Reputation: 174

Basically a vertex is on an edge if there is a zero within 1 in the x direction and 1 in the y direction. So for vertex [a,b] you'll need to check every vertex from [a-1,b-1] to [a+1,b+1]. Watch out for when the vertex is on the edge like [0,b] or [a,maxy].

Upvotes: 1

Related Questions