ofPolyline: interpolated index of closest point

Good day gents,

I came across a situation whereby I needed to find the length/pct on a ofPolyline in relation to the closest point (using the getClosestPoint(ofVec2f) method. However, there wasn’t any way to get this using the already existing functions.

Hence, I modified the existing getClosestPoint function to suit my requirement.

It worked fine for me, but I’m not sure if there’s anything that could be done to make it more efficient. That aside, I might propose adding the following function to ofPolyline? (The name of the function probably could use a bit of summarization :grinning:)

float ofPolyline::getIndexInterpolationAtClosestPoint(const ofPoint &target) const
{
    const ofPolyline & polyline = *this;
    
    if(polyline.size() < 2) {
        return 0;
    }
    
    float distance = 0;
    ofPoint nearestPoint;
    unsigned int nearest = 0;
    float normalizedPosition = 0;
    unsigned int lastPosition = polyline.size() - 1;
    if(polyline.isClosed()) {
        lastPosition++;
    }
    for(int i = 0; i < (int) lastPosition; i++) {
        bool repeatNext = i == (int) (polyline.size() - 1);
        
        const ofPoint& cur = polyline[i];
        const ofPoint& next = repeatNext ? polyline[0] : polyline[i + 1];
        
        float curNormalizedPosition = 0;
        ofPoint curNearestPoint = getClosestPointUtil(cur, next, target, &curNormalizedPosition);
        float curDistance = curNearestPoint.distance(target);
        if(i == 0 || curDistance < distance) {
            distance = curDistance;
            nearest = i;
            nearestPoint = curNearestPoint;
            normalizedPosition = curNormalizedPosition;
        }
    }
    
    return float(nearest) + normalizedPosition;
}
1 Like

I second the need of this function, was wondering the same in this thread

Hi Dimitre,

In the interim, the above function should work for you if you drop it into ofPolyline.cpp and create a definition for it in ofPolyline.h, though I have not tested it very extensively.

Alternatively, you could create a subclass of ofPolyline and add it in. I used this method for what I needed.

To make a function like this more accessible. IMO it makes sense to write it “c-style”.

float getIndexInterpolationAtClosestPoint(const ofPolyline& polyline, const ofPoint &target) const
{
    ...
    return float(nearest) + normalizedPosition;
}

// call
getIndexInterpolationAtClosestPoint(polyline, {x, y});

That way you can just drop it anywhere in your project.

i understand it correctly that the return result of this would be for example 3.5 meaning half distance between vertex 3 and 4?

if that’s the case perhaps getLerpIndexAtClosestPoint() might be a slightly shorter name but still understandable. can you send a PR with the fucntion + a comment with documentation?

this seems like a great function (and one that I’d probably use / have written in the past) but maybe it’s worth considering if it’s not great as part of an addon with more advanced or specific polyline functionality? as you describe I think it would benefit from a readme and an actual example.

Yes you are right. Half distance between vertex 3 and 4 would return 3.5.

All I did was really just alter the last few lines of the ‘getClosestPoint()’ function that already exists in ofPolyline.
The section that assigns a value to an unsigned int pointer, added an extra step that rounded off the number to the closest vertex (which also has its uses) and I essentially just removed that and set it to return a float instead.

Either way I’ll put together an example that compares the 2 functions (is that what you meant by PR?) and add some proper comments as soon as I get a chance to.

And here it is! It’s an Xcode project, but you should be able to regenerate with project generator on whatever platform you fancy. It doesn’t require any other addons.

getLerpIndexAtClosestPoint.zip (28.1 KB)

While building this, I’ve noticed a bug with the function when it comes to closed polylines. It lerps between the last and first vertex indices when the closest point resides between the two at the ‘closed’ end (ie. the full range of vertices). I suppose the behavior should be a lerp between the last vertex and the last vertex+1? Hence if there was a polyline with 12 vertices, and the point in question was midway between index 11 and index 0, it should read 11.5. Would everyone agree?

I’ll try to think of how to implement this, however, the reset of the example should demonstrate the function and how it can be applied.

Edit:
After a bit more testing, it seems its the other existing functions that the lerp is working correctly, but it’s the other existing functions that use an interpolated index as an argument, which become buggy when the value of the index is higher than the index of the last vertex. Not sure how to take this forward…

While I was working on a helper function to achive the same results, I came across this forum.
I’m also interested in this function. Strange its not there already.

currently I made a simple helper function that is actually almost the same as yours. Copied the original from OF closestPoint. It works with gfPolyline::getPointAtIndexInterpolated.

What kind of bugs are you experiencing with the other existing functions.

for a reference here is the code I’m using currently:

glm::vec2 getLerpIndexAtClosestPoint(const ofPolyline &polyline,const glm::vec3& target, float* nearestIndex){
	if (polyline.size() < 2) {
		if (nearestIndex != nullptr) {
			nearestIndex = 0;
		}
		return target;
	}

	float distance = 0;
	glm::vec3 nearestPoint;
	unsigned int nearest = 0;
	float normalizedPosition = 0;
	unsigned int lastPosition = polyline.size() - 1;
	if (polyline.isClosed()) {
		lastPosition++;
	}
	for (int i = 0; i < (int)lastPosition; i++) {
		bool repeatNext = i == (int)(polyline.size() - 1);

		const auto& cur = polyline[i];
		const auto& next = repeatNext ? polyline[0] : polyline[i + 1];

		float curNormalizedPosition = 0;
		auto curNearestPoint = getClosestPointUtil(cur, next, target, &curNormalizedPosition);
		float curDistance = glm::distance(toGlm(curNearestPoint), toGlm(target));
		if (i == 0 || curDistance < distance) {
			distance = curDistance;
			nearest = i;
			nearestPoint = curNearestPoint;
			normalizedPosition = curNormalizedPosition;
		}
	}

	if (nearestIndex != nullptr) {
		*nearestIndex = nearest + normalizedPosition;
	}

	return nearestPoint;
}