Click here to Skip to main content
15,393,377 members
Please Sign up or sign in to vote.
3.00/5 (1 vote)
See more:
Hey guys,

I was going to make a program that would find the outer edges that do not equal to null(0).

I currently have two arrays, one with all the information in it from where I will find the edges, and one of them that will point out where the edges are at.

So here's an example of what I'm trying to accomplish, and I have attempted many times but failed due to lack of performance, or lack of ideas.

Information Array:
0-0-0-0-0-0-0
0-#-#-#-#-#-0
0-#-#-0-#-#-0
0-#-#-#-#-#-0
0-#-#-#-#-#-0

If the above grid is our information array, or from where to find the edges, our edges array would result in another two dimensional array as the following:

Edges Array:
0-0-0-0-0-0-0
0-#-#-#-#-#-0
0-#-0-0-0-#-0
0-#-0-0-0-#-0
0-#-#-#-#-#-0

Now obviously, this would simply mean that I would do a basic for loop for every direction and see where it hits. At least, that's what I thought until I realised that if there is a hole:

0-0-0-0-0-0-0
0-#-#-#-#-#-0
0-0-0-#-#-#-0
0-#-0-#-#-#-0
0-#-#-#-#-#-0

It wouldn't know that there are actually objects where the "@" is located.

0-0-0-0-0-0-0
0-#-#-#-#-#-0
0-0-0-#-#-#-0
0-#-@-#-#-#-0
0-#-#-#-#-#-0

Does anyone have any clues on how to perform this action?
Posted
Comments
BillWoodruff 24-Dec-13 15:42pm
   
Looking at you examples, I can't understand exactly what you mean by "edge;" could you explain a bit further ?
Deviant Sapphire 24-Dec-13 15:46pm
   
Well, it's simple really. The hashtags that are filled in just like filled square have edges. Basically the goal is to find the locations of the edges(Array[ x, y]) and put those into another array. It's easy to do this with rectangles, spheres, and every shapre for that matter, however a shape that has for instance a cut-in edge also has indirect edges as shown in the last example. I have no idea how to get those.
Deviant Sapphire 24-Dec-13 15:50pm
   
Here is what I mean.
http://i39.tinypic.com/2hfq654.png
The black lines are the "edges" in x,y cooardinates based on pixels.
Deviant Sapphire 24-Dec-13 15:50pm
   
You wouldn't be able to find those by using only two for loops, and I have no idea how to do it otherwise.
Deviant Sapphire 24-Dec-13 15:57pm
   
Also be sure not to forget that they are metaphors for real objects in a two dimensional array, from which one is null and the other one is a real object.
BillWoodruff 24-Dec-13 20:00pm
   
After a little sleep, and looking at your question again, it's clear to me that what you want to do is to "harvest" only the outermost objects in the Array that will define the borders of a virtual closed shape. I see this as analogous to an edge-detection problem in computer graphics.

I assume, but don't know for sure, that you will not have two or more shapes separated by the equivalent of "white-space."

As you have discovered, edge detection gets really interesting where you have inner "holes" in the data-structure, holes which do not touch row, or column, boundaries. You show an example with one hole; Do you need to be able to deal with possible multiple holes ?

To use a pixel metaphor: you want to exclude duplicate inner rows that are > 1 pixel high, or duplicate inner columns that are > 1 pixel wide. Does that sound right?

I hypothesize the best format for the results of this operation might be a data-structure that contains only the row/column addresses of the border-defining elements. This could be something like a List<List<Point>>, for example. Or, an Array of sparse Arrays.

If you needed to access row/column addresses using the border-defining Objects harvested, you might think of something like: Dictionary<YourObjectType, Point>.

Of course, you are the only one who can judge what you need :)

If you can define criteria for some types of input you will never need to analyze, then it's possible you can also come up with some heuristics (short-cuts) to quickly exclude certain types of inputs.

Along similar lines: if you can always assume your source data does describe a single continuous border of one shape, you can avoid much deeper levels of analysis, and error-checking.

Knowing your bigger-picture purpose here might help you get more focused advice.

If your broader-scope task is "recognizing shape(s)," you are in a different game than just recognizing border(s).

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900