CHAIN_APPROX_SIMPLE - how does it work

I need to know what is the algorithm behind finding simplified contours.
How does CHAIN_APPROX_SIMPLE algorithm work?
Does anybody know? Can someone explain it?

It is well described in the documentation: OpenCV: Structural Analysis and Shape Descriptors, search for `CHAIN_APPROX_SIMPLE`.

compresses horizontal, vertical, and diagonal segments and leaves only their end points. For example, an up-right rectangular contour is encoded with 4 points.

I mean I know that, but how is it done?
What kind of algorithm is used? Which mathematical equasions are used to determine which points are these?

The docementation does not explain it when it cones to CHAIN_APROX_SIMPLE.

how would you do this if you were asked to figure it out?

I tried to look for answers in openCV code, but I failed. That’s why I’m looking for help here.

I don’t mean look for answers. I mean, you could think about the problem and come up with your own solution. chances are, you’ll come up with the solution that everyone does too.

to get you started, you could look at the “angles between neighbours”:

``````A --- B --- C
|
D --- E
``````

since A and C are on a straight line, we can remove B

you got all my sympathy.
the contours code is the very last remainder of the ill-fated C-api
trying to parse that is like reading aramaic glyphs.

Using a geographic analogy, we have contours described by unit steps in these directions: N, NE, E, SE, S, SW, W and NW. A contour of an upright 3x4 rectangle would look like this before the compression:

``````NNNEEEESSSWWWW
``````

which is:

``````3N, 4E, 3S, 4W
``````

which yields these coordinates after compression, assuming lower left corner is at (x, y) and Y-axis is directed upwards:

``````(x, y), (x, y+3), (x+4, y+3), (x+4, y)
``````