Corner detection algorithm

[mike3]

Hi.

I have a question. What kind of algorithm could be used to determine if a wall square is a corner? E.g.

Code: [Select]

...
##.
...

identifies as

Code: [Select]

...
-X.
...

where - is a horizontal wall and X is a corner? So given the tiles in the vicinity of the wall square, how do we find out if it's a corner or straight wall?

[Hi]

it's nice when people ask me questions by name

from what I think you're asking
check each of the surrounding 8 squares if it is only next to one other wall it's an end square.
if you allow diagonal moves you only need to check the 4 squares next to it.

are you asking about L type corners?
are you including T and + ?

[mike3]

Yeah, the center of this would be a corner too:

Code: [Select]

###
###
##.

and this

Code: [Select]

.#.
###
.#.

and this

Code: [Select]

.#.
###
#.#

This would NOT have a corner at the center, but a horizontal wall segment

Code: [Select]

###
###
#.#


[Hi]

.0.
3#1
.2.

so if it has at least one diagonal free and walls of opposite divisibility it is a corner?

[mike3]

Uh, but

Code: [Select]

.#.
.##
.#.

has a corner at the center.

[Darren Grey]

Code: [Select]

789
456
123
IF ( 9 = . AND 8 = # AND 6 = # )
OR
IF ( 7 = . AND 8 = # AND 4 = # )
OR
IF ( 1 = . AND 2 = # AND 4 = # )
OR
IF ( 3 = . AND 6 = # AND 2 = # )

However this doesn't include your original post of a long wall jutting out - I fail to see how this counts as a corner, to be honest.

[mike3]

It is a corner, since if you look on the right, there are two floor spaces such that if you were standing on them, that central wall tile would be in the corner.

[Kaskad]

Had to deal with this earlier today actually.

Firstly, unless you specifically have to deal with diagonal walls, which I don't, forget about this:

Code: [Select]

...
...
...
and just think about these

Code: [Select]

.
...
 .

So let's say our function gives us a wall to test, that wall is the middle guy:

Code: [Select]

.
.#.
 .

so he's known, the unknowns are to his east, west, north, and south. This is what the algorithm starts off knowing.

First, check the spot to the right:

Code: [Select]

.
.#?
 .

If it's a wall, check the spot to the left:

Code: [Select]

.
?##
 .

If that's not a wall, the algorithm ends and returns that we have a corner. If it is a wall, check both above and below at the same time. If either is a wall, the algorithm returns a corner; but if neither is, it returns not a corner.

Code: [Select]

?
###
 ?

If, however, the spot to the east was not a wall, we have to repeat the process starting from north (only we don't have to check east on the last step):

Code: [Select]

?
.#.
 .


Code: [Select]

#
.#.
 ?


Code: [Select]

#
?#.
 #

If neither the east nor north tile is a wall, we can return corner.

The algorithm can take up to 4 steps, but as few as 2, so it's more efficient than checking the situation against every possible permutation of a corner.

[Darren Grey]

I don't see how you can ignore the diagonals like that...  Consider:

Code: [Select]

#.#      ..#
.##  VS  .##
#.#      #.#
Or many other layouts, for that matter...  Of course I can't think of any elegant method to include diagonals.

mike3, if you include the jutting out square as a corner then I presume you include the following too:

Code: [Select]

#..
.#.
..#
I really can't see any easy way to judge this, but I have the problem stuck in my head now...

[Darren Grey]

Hmm, well, brute force would be like this:

Code: [Select]

789
456
123
IF ( 9 = . AND 8 = # AND 6 = # )
OR
IF ( 7 = . AND 8 = # AND 4 = # )
OR
IF ( 1 = . AND 2 = # AND 4 = # )
OR
IF ( 3 = . AND 6 = # AND 2 = # )
OR
IF ( 9 = . AND 8 = . AND 6 = . )
OR
IF ( 7 = . AND 8 = . AND 4 = . )
OR
IF ( 1 = . AND 2 = . AND 4 = . )
OR
IF ( 3 = . AND 6 = . AND 2 = . )

It ain't elegant, but as far as I can see it works.

[mike3]

Actually I think I finally figured this one out now. I did this by looking at it backwards: instead of trying to determine what's a corner, let's find everything not a corner first, namely horizontal/vertical walls and free rock, and then corners are found via exclusion.

It's like this:

With neighborhood

123
456
789

do this:

1. Check if the tile may be a horizontal or vertical wall. This is done by seeing if 4 and 6 are both walls, or 2 and 8 are both walls. In the former, we have a horizontal wall candidate. In the latter, we have a vertical wall candidate. If not, declare a corner and end. Don't worry about cases where both are walls, just arbitrarily call it a horizontal/vertical wall candidate and move on to step 2.

Code: [Select]

...
### = Horizontal Wall Candidate
...

..#
### = Horizontal Wall Candidate
...

.#.
.#. = Vertical Wall Candidate
.#.

##.
.## = Vertical Wall Candidate (but will turn out to be a corner)
##.

...
.#. = Corner Candidate
.#.

2. Check to see if there are walls in tiles 2 and 8 or 4 and 6, respectively for horizontal and vertical wall candidates. If one of these is found to contain a wall, then we check if the two corner tiles adjacent to it are floors. If at least one is, then this tile is a corner and we are done. If they are both walls, then we repeat this test on the other side. If the entire neighborhood turned out to be full of walls, this tile is free rock. If not, and none of the corner-tile floor checks declared this a corner, we call it a horizontal or vertical wall depending on which type of candidate it was.

Code: [Select]

Given:
##.
.##
##.

Check if there are walls in tiles 4 or 6.

##.
?#?
##.

There is no wall in tile 4. There is one in tile 6. What are the two corner squares adjacent to tile 6?

##?
.##
##?

And they're floors. Thus this is a corner.

See?

[K.I.L.E.R]

It's been a while since I've done any image processing, however looking at various algorithms for corner detection. I've come across a few things here.

I'm looking into "The Trajkovic and Hedley corner detector", as it seems the easiest and most feasible. I doubt people will want to look into convolutions and whatnot to solve this problem, as it is overkill.

[Kaskad]

I don't see how you can ignore the diagonals like that...  Consider:

Code: [Select]

#.#      ..#
.##  VS  .##
#.#      #.#
Or many other layouts, for that matter...  Of course I can't think of any elegant method to include diagonals.

I think you misunderstand. The algorithm I suggested would return both of those as corners.

These are the only situations which will return a corner when they are not:

Code: [Select]

..#   #..
.#.   .#.
#..   ..#

If your game has the possibility of this occurring, you can hard-code in checks for either of those situations and tack it on the end of the algorithm, which would increase total potential steps to 5. So it's still a lot more elegant than brute forcing by comparing to every possible permutation, and it also only has to look at walls, not floors (which reduces the ways in which things could go wrong). If there isn't a chance of those specific cases occurring, which was the case for my game, you don't have to worry about it.

[Etinarg]

Just a quick note: You could make use of the symmetry and get away with much less tests, if you use rotation and mirroring before applying the test. (You can do that with a simple 2D matrix transform if your enviroment has support for that).

[Darren Grey]

I don't see how you can ignore the diagonals like that...  Consider:

Code: [Select]

#.#      ..#
.##  VS  .##
#.#      #.#
Or many other layouts, for that matter...  Of course I can't think of any elegant method to include diagonals.

I think you misunderstand. The algorithm I suggested would return both of those as corners.

The problem being that the first example is not a corner.  The middle tile has no diagonal edges exposed.