CODEWITHSUNDEEP
c#algorithmdesign-patterns
Alex
Alex

Reputation: 278

2D Pattern Searching

What would be a good algorithm for searching through 2D arrays of data and creating borders around data of the same sort? The data would be random so there wouldn't be any prior knowledge of the data available, other than that it'd contain numeric values.

Otherwise are there any good articles/books on the subject?

Edit

Here is an example of what I'm trying to achieve:

enter image description here

And the same for the two's

Upvotes: 4

Views: 517

Answers (3)

Aravind
Aravind

Reputation: 3199

Breadth First Search could help you here.First construct the graph G as follows:

Graph G has edge (u,v) is and only if value of u-th cell=value of v-th cell.

Then carrying out BFS gives nice pieces of the graph that you can conveniently mark as visited using the value of the cell.

Upvotes: 3

PeterK
PeterK

Reputation: 6317

A naive solution (which will work fine for small data sets) is to define a comparison operator that takes two arguments and returns true if they are equal and false otherwise and then simply compare all pairs of adjacent values (both horizontally and vertically) and drawing a border if the comparison returns false.

Upvotes: 0

Matthew Watson
Matthew Watson

Reputation: 109762

This is a complex problem which I think is equivalent to finding the concave hull of a set of points.

You would first have to define an equality operation for the data points so that you can determine the set of "same sort" data points.

Having identified a set of points in that way, you then need to find the concave hull for that set of points.

(I'm assuming you want the concave hull and not the convex hull).

Finding the concave hull is a non-trivial task.

See here for details: https://gis.stackexchange.com/questions/1200/concave-hull-definition-algorithms-and-practical-solutions

If it's actually the convex hull you want, see here for an implementation in C#:

http://miconvexhull.codeplex.com/

Upvotes: 1

Related Questions