Get nearest point on spline?

Helper

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 22/10/2008 at 00:32, xxxxxxxx wrote:

User Information:
Cinema 4D Version:   10.1
Platform:   Windows ; Mac ;
Language(s) :     C++ ;

---------
Hi,

is there a function to get the nearest point on a spline?

For example, I have an object somewhere in the scene and a spline. How can I calculate the position of the point where the spline is nearest to the object?

Thanks in advance for any help!

Best regards,
Jack

Helper

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 22/10/2008 at 00:56, xxxxxxxx wrote:

The problem is this is not very welld defined. Lets say you have a point in the center of a circular spline. Each distance to the spline would be identical. Currently I can only think of splitting the spline into line segments and using PointLineDistance() to measure the distance and comparing the measured distances.

cheers,
Matthias

Helper

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 22/10/2008 at 04:47, xxxxxxxx wrote:

I agree with Matthias. Finding the closest point on a spline analytically is quite tricky in the general case. The best approach is to convert the spline to line segments, and then do the check for all segments.

regards
/Filip

Helper

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 22/10/2008 at 12:50, xxxxxxxx wrote:

Sounds like a good approach to me, thank you guys

Greetings,
Jack

Helper

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 06/01/2009 at 15:42, xxxxxxxx wrote:

Quote: _Lets say you have a point in the center of a circular spline. Each distance to the spline would be identical.
>
> * * *
_

While I agree with this, it is not always a problem making a (eh-hem) 'random' decision in cases where there are competing equidistant closest point options. You can do this randomly or first-encountered or whatever other decision criteria.

The reason I say this is because my situation is going to be like this. I'm growing ivy and want it 'generally' to follow a user-specified spline. In order to do that, there must be a consideration of proximity constantly.

My question is this though: how accurate is the LineObject from GetLineObject() and what values for Real lod (0.0 to 1.0? meaning?)?

Helper

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 17/03/2009 at 12:10, xxxxxxxx wrote:

Hi Robert,

did you figure something out? (I guess so :D)
How's it done? Can you give me a little hint?

I guess, I'll just sample a given amount of positions along the spline and pick the nearest one. That way, the user has control about precision and performance.

Greetings,
Jack

Helper

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 17/03/2009 at 12:43, xxxxxxxx wrote:

Well, first you need a LineObject which can be tricky. Here is the routine I used for IvyGrower to get the proper one from a Spline of some sort:

> // Prepare spline (primitive to real, consider deformers) \> //\*---------------------------------------------------------------------------\* \> Bool Ivy::PrepareSpline(SplineObject\* sobj) \> //\*---------------------------------------------------------------------------\* \> { \> Matrix mg = sobj->GetMg(); \> // GetRealSpline (returns self if already 'real') \> Bool free = FALSE; \> SplineObject\* test = sobj->GetRealSpline(); \> if (!test) return ErrorException::Throw(GeLoadString(SIVY_ERR_GENERAL), "Ivy.PrepareSpline.GetRealSpline"); \> if (test != sobj) \> { \> // Clone Spline \> sobj = ToSpline(sobj->GetClone(0L, NULL)); \> if (!sobj) return ErrorException::Throw(GeLoadString(SIVY_ERR_GENERAL), "Ivy.PrepareSpline.GetClone"); \> // MakeEditable \> ModelingCommandData mcd; \> mcd.doc = doc; \> mcd.op = sobj; \> mcd.mode = 0L; \> if (!SendModelingCommand(MCOMMAND_MAKEEDITABLE, mcd)) \> { \> return ErrorException::Throw(GeLoadString(SIVY_ERR_GENERAL), "Ivy.PrepareSpline.SendModelingCommand(MAKEEDITABLE)"); \> } \> sobj = ToSpline(mcd.result->GetIndex(0L)); \> if (!sobj) return ErrorException::Throw(GeLoadString(SIVY_ERR_GENERAL), "Ivy.PrepareSpline.sobj"); \> free = TRUE; \> } \> // CurrentStateToObject obj \> ModelingCommandData mcd; \> BaseContainer mbc; \> mbc.SetBool(MDATA_CURRENTSTATETOOBJECT_INHERITANCE, TRUE); \> mbc.SetBool(MDATA_CURRENTSTATETOOBJECT_KEEPANIMATION, FALSE); \> #ifdef C4D_R95 \> mbc.SetBool(MDATA_CURRENTSTATETOOBJECT_NOGENERATE, FALSE); \> #endif // C4D_R95 \> mcd.doc = doc; \> mcd.flags = 0L; \> mcd.bc = &mbc; \> mcd.mode = MODIFY_ALL; \> mcd.op = sobj; \> if (!SendModelingCommand(MCOMMAND_CURRENTSTATETOOBJECT, mcd)) \> { \> if (free) SplineObject::Free(sobj); \> return ErrorException::Throw(GeLoadString(SIVY_ERR_GENERAL), "Ivy.PrepareSpline.SendModelingCommand(CURRENTSTATETOOBJECT)"); \> } \> if (free) SplineObject::Free(sobj); \> SplineObject\* cstoObj = static_cast<SplineObject\*>(mcd.result->GetIndex(0L)); \> if (!cstoObj) return ErrorException::Throw(GeLoadString(SIVY_ERR_GENERAL), "Ivy.PrepareSpline.cstoObj"); \> // Get LineObject \> followSpline = cstoObj->GetLineObject(doc, 1.0f, NULL); \> SplineObject::Free(cstoObj); \> if (!followSpline) return ErrorException::Throw(GeLoadString(SIVY_ERR_GENERAL), "Ivy.PrepareSpline.GetLineObject()"); \> if (!followSpline->GetSegmentCount()) \> { \> LineObject::Free(followSpline); \> followSpline = NULL; \> return ErrorException::Throw(GeLoadString(SIVY_ERR_GENERAL), "Ivy Grower doesn't support following multi-segmented splines"); \> } \> followSPtCnt = followSpline->GetPointCount(); \> #ifdef C4D_R10 \> followSPoint = followSpline->GetPointW(); \> #else \> followSPoint = followSpline->GetPoint(); \> #endif \> if ((followSPtCnt < 2L) || !followSPoint) \> { \> LineObject::Free(followSpline); \> followSpline = NULL; \> return ErrorException::Throw(GeLoadString(SIVY_ERR_GENERAL), "Ivy.PrepareSpline.followSPoint"); \> } \> // Apply global matrix to points \> for (LONG n = 0L; n != followSPtCnt; ++n) \> { \> followSPoint[n] \*= mg; \> } \> // Always considering pairs of points (line segments) \> --followSPtCnt; \> \> return TRUE; \> }

And then here you can see how I test for distance. Not optimized for speed in any way (always tests all line segments) :

> // Get the distance of a line segment from a Sphere surface. \> // Input: a Line Segment P0-P1 and a Sphere C,r \> // Return: whether or not line segment is outside sphere \> // Pn contains the closest point on the line segment \> // dist contains the shortest distance from P0-P1 to C,r \> //\*---------------------------------------------------------------------------\* \> Bool DistanceSegmentSphere(const Vector& P0, const Vector& P1, const Vector& C, const Real r, Vector& Pn, Real& dist) \> //\*---------------------------------------------------------------------------\* \> { \> Vector v = P1 - P0; \> Vector w = C - P0; \> \> double c1 = w \* v; \> if (c1 > 0.0) \> { \> double c2 = v \* v; \> if (c1 < c2) \> { \> c1 /= c2; \> Pn = P0 + c1 \* v; \> } \> else Pn = P1; \> } \> else Pn = P0; \> \> v = C-Pn; \> // Inside sphere \> if (Len(v) < r) return FALSE; \> // Outside/on sphere \> dist = Sqrt(v\*v); \> return TRUE; \> } \> //\*---------------------------------------------------------------------------\* \> Bool Ivy::computeTowardsSpline(const Real& floatLength, const Vector& oldPos, Vector& newPos, Bool& climbing) \> //\*---------------------------------------------------------------------------\* \> { \> Vector nearPt = newPos; \> Vector segPt; \> Real r = Len(newPos-oldPos); \> Real minDistance = MAXREAL; \> Real distance; \> \> climbing = FALSE; \> for (LONG n = 0L; n != followSPtCnt; ++n) \> { \> // LineSegment-Sphere Distance calculation - return if a line segment is found to be interpenetrating sphere \> if (!DistanceSegmentSphere(followSPoint[n], followSPoint[n+1], oldPos, r, segPt, distance)) \> { \> climbing = TRUE; \> return TRUE; \> } \> if (distance >= minDistance) continue; \> minDistance = distance; \> nearPt = segPt; \> } \> // get a point along line segment 'nearPt to newPos' using a 0.0 to 1.0 parameter (splineWeight with some random variation) \> nearPt = !(nearPt - oldPos); \> newPos = !(newPos - oldPos); \> segPt = newPos + ((nearPt - newPos) \* splineWeight \* rand() \* irand); \> newPos = (!segPt \* r) + oldPos; \> climbing = (minDistance <= floatLength); \> return climbing; \> }

Hope that helps a bit.

Helper

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 17/03/2009 at 12:45, xxxxxxxx wrote:

Note that I'm testing DistanceSegmentSphere as there is a line segment (not associated with the spline) being tested for closeness allowing for change in direction.

Helper

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 17/03/2009 at 15:56, xxxxxxxx wrote:

Ha, I already solved it

But totally different from your approach. I just take a user-given amount of samples from the spline and store those positions in an array.

Then I iterate the array whenever I need to get a nearest point on the spline, and calculate the distance from my position to each of the positions in the array. The one that gives the lowest distance is returned.

The performance is astonishingly good, and the code is quite simple.

This function creates fills an array with sampled positions on the spline:

> void SampleSplinePoints(SplineObject \*sp, GeDynamicArray<Vector>&SampleArr;, LONG Accuracy) \> { \> LONG i = C_ZERO; \> \> // Init Length \> sp->InitLength(); \> \> for (i = C_ZERO; i < Accuracy; i++) \> { \> SampleArr[i] = sp->GetSplinePoint(sp->UniformTonatural((Real)i / (Real)(Accuracy-C_ONE))); \> } \> \> // Free Length \> sp->FreeLength(); \> } \>

This function picks the one that gives the lowest distance and returns it in "ShortestPos". Forget about the "Flat" parameter, it's just something I needed for a specific feature.

> void GetNearestPoint(GeDynamicArray<Vector>&SampleArr;, Vector &Position;, LONG &Accuracy;, Vector &ShortestPos;, const Bool Flat = TRUE) \> { \> LONG i = C_ZERO; \> Real p = C_FLOATZERO; \> \> Vector Match = Vector(C_FLOATZERO); \> Vector pos = Vector(); \> Real Dist = C_FLOATZERO; \> Real Shortest = C_FLOATZERO; \> \> // Iterate sample positions on spline \> for (i = C_ZERO; i < Accuracy; i++) \> { \> // Get position \> pos = SampleArr[i]; \> \> // Calculate Distance \> if (Flat) \> Dist = Len(Vector(pos.x, C_FLOATZERO, pos.z) - Vector(Position.x, C_FLOATZERO, Position.z)); \> else \> Dist = Len(pos - Position); \> \> // If shortest distance found, memorize! \> if ((i == C_ZERO) || (Dist < Shortest)) \> { \> Shortest = Dist; \> Match = pos; \> //GePrint("Position=" + VectorToString(Position) + "; Found=" + VectorToString(pos) + "; Dist=" + RealToString(Dist)); \> } \> } \> \> // Return position with shortest distance \> ShortestPos = Match; \> } \>

This approach is, of course, only as exact as the user allows it to be (be specifying the Accuracy == Number of samples). But it's totally sufficient for what I'M doing with it

Best Greetings,
Jack

Helper

On 18/10/2017 at 13:20, xxxxxxxx wrote:

Maybe someone else will find it helpful to have this ported to Python

Thanks to the OP(s) for the original code

# build an array of points from a spline
def SampleSplinePoints(spline, acc) :                           #spline object, accuracy (int)
    
    sarr = []                                                  #point array
    for i in xrange(0, acc) :                                   #iterate through points
      sarr.append(spline.GetSplinePoint(float(i) / (acc-1)))   #append current point to array
    
    return sarr                                                #return array
  
  
# find the nearest point in a point array
def GetNearestPoint(sarr, p) :          #point array, point (vector)
    
    index = 0                          #closest point index
    md = 9e9999                        #min dist to keep track of
    
    for i in xrange(0, len(sarr)) :     #iterate through point array
        v = sarr[i]-p                  #store current difference vector
        d = v.GetLength()              #calc distance of vector
        if d < md:                     #if dist < minimum so far
            index = i                  #   then store index
            md = d                     #   and also set new minimum
            
    return index                       #return index of closest point in array

Hope it helps

Jenny