<p>I am trying to find an algorithm for the following problem.</p>
<p>Assume we have a black and white image. The image contains a white region that encloses a space. This space may be concave but it has no holes, i.e. there is only one boundary.</p>
<p>We must create a polyline such that, each point in the polyline, that point is inside a boundary pixel in the original image, the winding direction of the polyline points is the same for all images fed to the algorithm.</p>
<p>I know opencv has a couple of functions that do this but I am interested in the algorithm rather than the implementation.</p>

CC BY-SA 4.0
2022-02-22T09:12:32.087Z
The simplest thing is to just check the vertices in the middle of every 4 pixels. If the 4 pixels are of different classes make the vertex a boundary vertex. Then do a pass to connect said vertices along the 4 possible edges.
lightxbulb
CC BY-SA 4.0
2022-02-22T16:04:37.793Z
It sounds like you are looking for a _contour tracing_ or _boundary tracing_ algorithm (Search terms useful in your quest.)  Algorithms include _Square Tracing_ and _Moore Neighbour Tracing_ and others.  See [this website](http://www.imageprocessingplace.com/downloads_V3/root_downloads/tutorials/contour_tracing_Abeer_George_Ghuneim/alg.html).  The winding direction is trivial to determine (and to invert as a post processing step if it's not the preferred direction.)
Wyck
<computational-geometry><image-processing><polygon><line-drawing>
How to get a polyline from an image with consistent winding number
Makogan
# How to get a polyline from an image with consistent winding number

(Asked by: username_0 on 2022-02-22)

I am trying to find an algorithm for the following problem.

Assume we have a black and white image. The image contains a white region that encloses a space. This space may be concave but it has no holes, i.e. there is only one boundary.

We must create a polyline such that, each point in the polyline, that point is inside a boundary pixel in the original image, the winding direction of the polyline points is the same for all images fed to the algorithm.

I know opencv has a couple of functions that do this but I am interested in the algorithm rather than the implementation.

**Tags:** computational-geometry, image-processing, polygon, line-drawing

> **Comments:**
> **username_1**: The simplest thing is to just check the vertices in the middle of every 4 pixels. If the 4 pixels are of different classes make the vertex a boundary vertex. Then do a pass to connect said vertices along the 4 possible edges.  
> **username_2**: It sounds like you are looking for a _contour tracing_ or _boundary tracing_ algorithm (Search terms useful in your quest.)  Algorithms include _Square Tracing_ and _Moore Neighbour Tracing_ and others.  See [this website](http://www.imageprocessingplace.com/downloads_V3/root_downloads/tutorials/contour_tracing_Abeer_George_Ghuneim/alg.html).  The winding direction is trivial to determine (and to invert as a post processing step if it's not the preferred direction.)  

---

## 0 answers

