Finding indexes of convex points on a contour

Question

I have a vector of ordered Points that make up the contour of a worm (found with opencv). I am trying to get points along the skeleton of the worm. I want to do this very fast and so have a simple segmentation function:

void Worm::segmentWorm(void)
{
    int jump = 5;
    int numPoints = wormContour.size();

    int currentIndex = headIndex; //large circle in image w/overlay
    int endIndex = tailIndex;     //small circle in image w/overlay
    int matchingIndex;

    int direction = (endIndex - currentIndex)/abs(endIndex - currentIndex);

    int thisSideLength = abs(endIndex - currentIndex);
    int otherSideLength = numPoints - thisSideLength;

    double lengthPercentage;

    if (direction > 0) {
        while (currentIndex < endIndex - jump) {
            currentIndex += jump;

            lengthPercentage = (double)(endIndex - currentIndex)/(double)thisSideLength;
            matchingIndex = boundCheck((int)((lengthPercentage * otherSideLength) + endIndex), numPoints - 1);

            segments.push_back(pair<int, int>(currentIndex, matchingIndex));
        }
    } else if (direction < 0) {
        while (currentIndex > endIndex + jump) {
            currentIndex -= jump;

            lengthPercentage = (double)(currentIndex - endIndex)/(double)thisSideLength;
            matchingIndex = boundCheck((int)(-(lengthPercentage * otherSideLength) + endIndex), numPoints - 1);

            segments.push_back(pair<int, int>(currentIndex, matchingIndex));
        }
    }
}

The problem with this function is that when the worm bends a lot, i.e. the contour becomes concave on one side the skeleton cuts the corner and no longer represents the center of the worm. My solution is to shift the segment ends if they are concave, correcting the segments and skeleton.

Any suggestions on a very time efficient function that will find all the concave (or convex) points on the contour?

image of problem:

Answer 1

There is no way to get the right point pairs out of that array without some geometric calculations.

One solution would be to iterate along one side and then use the normal to find a points' counterpart. I suppose if the worms' width doesn't change too much you could use a fix offset length to search for the other point and also for the other point use a subset of the points on the other side, which would mean that a BF match should be very fast. Then you could update the offset and subset as you iterate.

edit: If the initial guess of the index of the counterpart is not really awful, then a brute force match isn't even necessary since you can traverse the side until no point is closer anymore.