How to model complex shapes using representative points?

I experimented with approximating a polyline path using approxPolyDP . When the shape is closed it is simple and always gives a good approximation. But when the form is open, like the sample image, sometimes the ordering of the approximated points is not supported (I gave an example of this below). It's hard to describe every detail of the approach, so I commented out the code c++

as best I could. Hope this helps.

The direction of the gradient at the approximated points of the polyline (the red points are the approximate points of the polyline, offset by some amount in the opposite direction of the gradient, and the blue points are in the direction of the gradient):

Endpoint approximations (point inside red blob) and navigation order (blue arrows)

Examples of gradient shapes and directions. Note the difference between closed and open forms. For a closed form, the red dots are located on one side of the stroke. For open pieces, red dots are located on both sides of the move.

The shape in the upper left corner does not match the navigation order because the path does not start at the tip of the shape. However, this is a good point-to-point approximation.

int _tmain(int argc, _TCHAR* argv[])
{
    Mat im = imread("1.png", 0);
    Mat roi = Mat::zeros(im.size(), CV_8UC1);
    /* find the gradient at every point */
    Mat dx, dy;
    Sobel(im, dx, CV_32F, 1, 0, 7);
    Sobel(im, dy, CV_32F, 0, 1, 7);
    /* take the distance transform */
    Mat dist;
    distanceTransform(im, dist, CV_DIST_L2, 5);
    /* max stroke radius */
    double th;
    minMaxLoc(dist, NULL, &th);

    /* for display/debug purposes */
    Mat rgb = Mat::zeros(im.size(), CV_8UC3);
    Mat rgb2;
    cvtColor(im, rgb2, CV_GRAY2BGR);
    Mat rgb3 = Mat::zeros(im.size(), CV_8UC3);

    Mat tmp = im.clone();
    // find contours, get every point with CV_CHAIN_APPROX_NONE
    vector<vector<Point>> contours;
    vector<Vec4i> hierarchy;
    findContours(tmp, contours, hierarchy, CV_RETR_CCOMP, CV_CHAIN_APPROX_NONE, Point(0, 0));

    for(int idx = 0; idx >= 0; idx = hierarchy[idx][0])
    {
        /* draw contours */
        drawContours(rgb, contours, idx, Scalar(0, 255, 255), 2, 8);
        drawContours(rgb2, contours, idx, Scalar(0, 255, 255), 1, 8);
        drawContours(rgb3, contours, idx, Scalar(0, 255, 255), 1, 8);

        /* polyline approximztion of the contour */
        vector<Point> poly;
        approxPolyDP(contours[idx], poly, th, false);
        /* 
            now we'll sample the gradient along the points in the polyline, 
            find another opposite point in the coitour in the gradient direction, 
            then find the peak location in the distance image (looks like the
            mid point should also work, but I didn't try it).
        */
        for (Point& pt: poly)
        {
            /* sample dx, dy at our point of interest */
            float x = dx.at<float>(pt);
            float y = dy.at<float>(pt);
            float n = sqrtf(x*x + y*y);
            /*  
                select another point in the direction of the gradient that intersects the stroke:
                by choosing a point that around 2.5 times the max stroke radius, we hope
                to cross the stroke with this line 
            */
            Point pt2(pt.x + 2.5*th*x/n, pt.y + 2.5*th*y/n);
            /* offset the first point a bit in the opposite gradient direction */
            Point pt1(pt.x - .5*th*x/n, pt.y - .5*th*y/n);
            /* draw a thick line */
            line(roi, pt1, pt2, Scalar(255, 255, 255), 2, 8);
            /*
                display the points
            */
            line(rgb3, pt1, pt2, Scalar(255, 255, 255), 2, 8);
            line(rgb2, pt1, pt2, Scalar(0, 255, 255), 2, CV_AA);
            circle(rgb2, pt1, 3, Scalar(0, 0, 255), -1, CV_AA);
            circle(rgb2, pt2, 3, Scalar(255, 0, 0), -1, CV_AA);
        }   

        /* dilate the lines so that nearby lines can merge */
        Mat kernel = getStructuringElement(MORPH_ELLIPSE, Size(3, 3));
        morphologyEx(roi, roi, CV_MOP_DILATE, kernel, Point(-1, -1), 1);
        /* only for debug */
        morphologyEx(rgb3, rgb3, CV_MOP_DILATE, kernel, Point(-1, -1), 1);
        /* we are interested in lines segments that are within the shape */
        roi &= im;
        /* collect all these line segments */
        vector<vector<Point>> regions;
        findContours(roi, regions, CV_RETR_CCOMP, CV_CHAIN_APPROX_SIMPLE, Point(0, 0));
        /* 
            now that we have all the info about lines segments, 
            we can use the image for other purposes such as a mask
        */
        roi.setTo(Scalar(0, 0, 0));
        /* our points of interest when we approximate the shape */
        vector<Point> shapeApprox;
        /*
            for each point on the shape contour, see if it is within a line segment
            that we found using gradients. if so, find the peak location from the distance image.
            it is a point in the skeleton
        */
        for (Point& pt: contours[idx])
        {
            for (size_t i = 0; i < regions.size(); i++)
            {
                if (-1 != pointPolygonTest(regions[i], pt, false))
                {
                    /* using roi as a mask to find the peak location from distance image */
                    drawContours(roi, regions, i, Scalar(255, 255, 255), -1);
                    double mx;
                    Point mxLoc;
                    minMaxLoc(dist, NULL, &mx, NULL, &mxLoc, roi);
                    /* 
                        if this point is not already in the list, add it. 
                        as the gradient line can intersect the shape contour at two
                        points most of the time, we'll find the same peak twice
                    */
                    if (shapeApprox.end() == find(shapeApprox.begin(), shapeApprox.end(), mxLoc))
                    {
                        //cout << mx << " @ " << mxLoc << endl;
                        shapeApprox.push_back(mxLoc);
                    }
                    /* no need to test other gradient lines */
                    break;
                }
            }
            /* reset the mask */
            roi.setTo(Scalar(0, 0, 0));
        }
        /* draw the (possibly merged) gradient line segments */
        drawContours(rgb, regions, -1, Scalar(0, 0, 255), -1);
        /* draw the shape approximation */
        for (size_t i = 1; i < shapeApprox.size(); i++)
        {
            arrowedLine(rgb, shapeApprox[i-1], shapeApprox[i], Scalar(255, 0, 0), 2, CV_AA, 0, .1);
            //imshow("approx", rgb);
            //waitKey(0);
        }
    }

    imshow("debug", rgb3);
    imshow("points", rgb2);
    imshow("approx", rgb);
    waitKey(0);

    return 0;
}