CODEWITHSUNDEEP
algorithmimage-processing
razor3x
razor3x

Reputation: 118

algorithm to draw image selection

I have an image with size of M*N. Each pixel can be selected or not selected.

image selection

Given selection values for each pixel (selected or not), what is the most efficient algorithm to get the set of polygons which represents a selection?

enter image description here

Upvotes: 0

Views: 89

Answers (2)

Jean-Baptiste Yunès
Jean-Baptiste Yunès

Reputation: 36401

I think any filling algorithm can be suitable:

  • get a selected pixel not already used
  • start from it and fill the surface defined by all its connected pixels
  • this will define a polygon (just retain horizontal/vertical extremas)
  • restart with any selected pixel already not considered to get another polygon

Upvotes: 1

MrSmith42
MrSmith42

Reputation: 10151

Diagonals might be tricky, because of pixel-exact rounding errors, so I would go only for rectangles with horizontal and vertical lines (overlapping ones can be merges to a polygon)

I would perform the following steps:

  1. connect selected neighbours of selected pixels to horizontal lines

  2. connect horizontal lines to rectangles

  3. connect overlapping/touching rectangles to a polygon

Upvotes: 1

Related Questions