Bug in icvApproxPolyDP (with fix) (Patch #2186)

Hi,

This is regarding the function icvApproxPolyDP(), which is in the file /modules/imgproc/src/approx.cpp

The function approximates a curve or polygon using the Douglas-Peucker algorithm.

After the core of the work of the function is done, it does a clean-up of the approximated contour. The idea of this clean up is to remove unnecessary points that are practically on straight lines. There is a bug in this clean up phase. The function should eliminate points which form 180 degree angles (straight lines), and are thus unnecessary. However, it is also removing points which form 360 degree (or 0 degree) angles. This significantly changes the lines (see examples in attachment).

The relevant code is in lines 643 to 663 of /modules/imgproc/src/approx.cpp. The code works with three points: start_pt, pt, and end_pt, which are three consecutive points being looked at. The attachment has a schematic showing the situation. To verify that the points are not forming a 360 (or 0 degree) angle, I compute the inner product between vectors (pt - start_pt) and (end_pt - pt). The attachment has an example of fix and also examples of the outputs of the code with and without the bug. In the proposed fix, I didn't worry about performance, and did things in a very straightforward way. Feel free to modify as you see appropriate, or come up with a different solution altogether.

Please let me know if anything is unclear.

best regards,
Joao