Search code examples
javascriptalgorithmedge-detection

Algorithm for finding the edges of an unknown # of shapes

I'm looking for an efficient algorithm that can give me all the edges of a random shape. I can write one, but if anyone knows of an existing solution that may be optimized, it would be appreciated as this is going to be running on mobile phones :)

Example Shape:

=====     ==========
=====     \=========
====/      \\     
===/        \\
==/          =======
=/           =======
====================
             =======
             =======
=====\       =======
======\     /=======

For the top-left edge, I'd need data that can effectively give me: [ 0%, 0% ], [ 25%, 0% ]

Solution

  • It seems like you can't get any more optimized than a nested loop and a character check. I could be wrong, but that's where I'd start.

    Psueudo

    for ( i = 0; i < rows; i++ ){
   for (j = 0; j < cols; j++ ){
      if character[i][j] === '/' or '|' or '\'  or '-'
         // Edge-Found logic.
   }
}

    EDIT

    I rescind my previous answer. I thought about it some more, and you could optimize even further by stopping the iteration at the first found instance of a character edge and searching all immediate nodes around that point for another edge. Rinse and repeat until you've worked your way all the way back to your starting edge. This problem lends itself easily to recursion and opens up a world of programming options to by creating a linked list while mapping out the shape.

    Reminds me of some of the mouse maze problems in 2nd year computer science. Excellent question -- it's great to see fun ones every now and again! :D

    Also - for anybody else that's curious, you can check out "graph theory" for all sorts of cool problems like this one. It's basically what powers the internet, google maps, and all sorts of other cool database applications (for instance, it's the theory behind FaceBook's database and is almost single-handedly responsible for the speed of their service...Ever heard of OpenGraph?)