1
\$\begingroup\$

enter image description here

Given only an image, I have to find a way of determining whether any two irregular bodies in that image are bordering one another. This is a map of districts, each with their own name, and my goal is to build a database which stores, for each district, which districts border it. I could manually create an entry for each district, and simply list which districts are bordering them. There are hundreds of districts, however, and I'm sure there's some way to automate this process. Not to mention, this map of districts is subject to change.

I've tried so far by defining a central point for a handful of districts, then testing if a line could be drawn between a pair of points and only cross over a border line once. This would mean the two districts were bordering, but this solution only works with districts that have simple geometry.

Any help here would be much appreciated!

\$\endgroup\$
1
  • \$\begingroup\$ You could use a polygon filling algorithm to colour each region slightly different shades, then check black vertices/pixels for a radius for different shades, for each check, you may find one or more colours, allowing you to match them to regions \$\endgroup\$
    – Natalo77
    Jul 30, 2020 at 8:44

1 Answer 1

2
\$\begingroup\$

(Assuming your borders are only 1-pixel wide. If they're thicker, do a pre-process to thin the borders/expand their regions until there's only a 1 pixel separation between regions)

  1. Prepare an array of region IDs as large as your image, initialized with a default "unassigned" value.

  2. Iterate over the pixels of your image in some order.

  3. If you come to a pixel that is an interior (not a border), and the corresponding entry in your region ID array is unassigned, assign it the next unused region ID, and start a flood fill from that location.

  4. The flood fill will spread over all connected interior pixels, marking them as your newly-chosen region ID in your array.

  5. When your flood fill reaches a border pixel, check if any of its neighbouring cells has a different region ID (that's not unassigned). If so, you've discovered a place where a different region meets this one. Check if you've already recorded this other region as a neighbour of this one. If not, add it, and add this region as a neighbour of the other one.

  6. Once you run out of interior pixels to fill or border pixels to check, you're done exploring this region. Resume your orderly iteration over the remaining pixels, skipping over any you've already assigned to a region.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .