Closest point to line

[Alexey Vanzhula]

Hi. I want to find closest point to line. Geometry has millions of points and the line is located somewhere in space. Need some fast solution.

image

 

[ikoon]

Hi Alexey, maybe this?

https://www.sidefx.com/docs/houdini/vex/functions/ptlined.html

[Noobini]

but isn't the catch here is point Q ?....how to get point Q out of the 'million' possible points...

 

[Noobini]

just testing...no idea how to VEXify...(pretty fast for ~3mil points pighead)

ClosestPtLine.hipnc

[Noobini]

my feeble attempt at VEX...won't win any speed contest...

 

ClosestPtLineWrangle.hipnc

Edited January 18, 2018 by Noobini

[Alexey Vanzhula]

Thanks guys! Noobini, the line is really infinite. Sorry for wrong image. Currently I walk through all points with ptlined in wrangle SOP (detail mode). It works well but not so fast as I want. Still experimenting.

[ikoon]

Hi Alexey, I am no master at optimization, but you may divide it into more steps:

- point wrangle to store @distance (so it uses all the cpu cores)
- sort by attribute (compilable, so maybe it can use all the cores?)

[Alexey Vanzhula]

Just now, ikoon said:

Hi Alexey, I am no master at optimization, but you may divide it into more steps:

- point wrangle to store @distance (so it uses all the cpu cores)
- sort by attribute (compilable, so maybe it can use all the cores?)

I also think about this. I'll try it

[Noobini]

15 minutes ago, Alexey Vanzhula said:

Thanks guys! Noobini, the line is really infinite. Sorry for wrong image. Currently I walk through all points with ptlined in wrangle SOP (detail mode). It works well but not so fast as I want. Still experimenting.

haha...no worries...there's just a slight difference between something....and something infinite.....(small technical details )

[Alexey Vanzhula]

4 hours ago, ikoon said:

compilable, so maybe it can use all the cores?

Compiled block will use all the cores only when you wrap foreach block with it 

[animatrix]

ptlined will be slow because it's calling sqrt(). You should implement your own pointLineDistanceSquared:
 

vector pointLineDistanceSquared ( vector p; vector linep0; vector linep1 )

{

    vector dir = linep1 - linep0;

    vector pp = p - linep0;

    return length2 ( cross ( dir, p ) ) / length2 ( dir );

}

Then you can multi-thread the distance calculation using Run Over Numbers, storing them as detail attributes and then compute the smallest one at the last step.

Edited January 19, 2018 by pusat

[Alexey Vanzhula]

27 minutes ago, pusat said:

ptlined will be slow because it's calling sqrt(). You should implement your own pointLineDistanceSquared:
 

vector pointLineDistanceSquared ( vector p; vector linep0; vector linep1 )

{

    vector dir = linep1 - linep0;

    vector pp = p - linep0;

    return length2 ( cross ( dir, p ) ) / length ( dir );

}

Then you can multi-thread the distance calculation using Run Over Numbers, storing them as detail attributes and then compute the smallest one at the last step.

Very interesting. I never used Run Over Numbers. Can you create example scene, please?

[fathom]

distance to an infinite line is really a 2d distance that's been rotated out of alignment to a cardinal axis.  so imagine rather than an arbitrary line, you were trying to find the point closest to the y axis.  it would be the point with the least value of (x*x+z*z).  trivial.  so now you just need to transform everything such that your infinite line is the y-axis.  because we only care about distance, we can do this very easily with a shear transform -- adding a proportion of the y value to each of x and z.  the proportions for each is based on the slope of your original line.

the math would be something like this (drycoding here... don't have houdini available atm):

>
	// p0 and p1 are the points of your line
	float x = P.x - p0.x - P.y*(p1.x-p0.x)/(p1.y-p0.y);
	float z = P.z - p0.z - P.y*(p1.z-p0.z)/(p1.y-p0.y);
	f@distanceSquared = x*x+z*z;
	

if p1.t-p0.y is too small (like abs() less than 0.0001 or something), you should select a different cardinal axis.

 

[Alexey Vanzhula]

12 hours ago, fathom said:

distance to an infinite line is really a 2d distance that's been rotated out of alignment to a cardinal axis.  so imagine rather than an arbitrary line, you were trying to find the point closest to the y axis.  it would be the point with the least value of (x*x+z*z).  trivial.  so now you just need to transform everything such that your infinite line is the y-axis.  because we only care about distance, we can do this very easily with a shear transform -- adding a proportion of the y value to each of x and z.  the proportions for each is based on the slope of your original line.

the math would be something like this (drycoding here... don't have houdini available atm):

 

>
	// p0 and p1 are the points of your line
	float x = P.x - p0.x - P.y*(p1.x-p0.x)/(p1.y-p0.y);
	float z = P.z - p0.z - P.y*(p1.z-p0.z)/(p1.y-p0.y);
	f@distanceSquared = x*x+z*z;
	

 

if p1.t-p0.y is too small (like abs() less than 0.0001 or something), you should select a different cardinal axis.

 

Thanks, I'll try it.