Fastest way to compute the closest distance between 2 lines?
3253 7 2- OdFotan
- Member
- 192 posts
- Joined: April 2015
- Offline
Hi folks,
I was hoping somebody could help me out.
xyzdist() might look at a whole polygon/surface, but it still has to look from one point; it doesn't look 'from' a whole primitive, if you know what I mean.
See the picture. It isn't a point where the lines nearly intersect.
How to find the closest distance in the most resource-efficient way ?
Thanks.
Edit: preferably in VEX, since I see this ‘primdist’ function in HScript which seems to do what I want, but I am writing VEX because HScript is just for parameters, right?
I was hoping somebody could help me out.
xyzdist() might look at a whole polygon/surface, but it still has to look from one point; it doesn't look 'from' a whole primitive, if you know what I mean.
See the picture. It isn't a point where the lines nearly intersect.
How to find the closest distance in the most resource-efficient way ?
Thanks.
Edit: preferably in VEX, since I see this ‘primdist’ function in HScript which seems to do what I want, but I am writing VEX because HScript is just for parameters, right?
Edited by OdFotan - Nov. 17, 2022 07:11:20
- Andr
- Member
- 899 posts
- Joined: Feb. 2016
- Offline
I don't have a proper math solution to this, but I think with bruteforce you can get a good enough approximation.
You resample one of the curve first, then xyzdist() and finally attrib promote to get the min distance.
Or probably more performant if you use Ray Sop instead of xyzdist()
You resample one of the curve first, then xyzdist() and finally attrib promote to get the min distance.
Or probably more performant if you use Ray Sop instead of xyzdist()
Edited by Andr - Nov. 17, 2022 08:51:50
- BabaJ
- Member
- 2114 posts
- Joined: Sept. 2015
- Online
Use the xyzdist function in a 'for each'sop lop. Use iteration odd/even number to switch alternatively between polygon/surface for each search from, search too; Using the result position (primuv() function of the xyzdist() function result)in each case.
Set the number of iterations of the for each loop to get desired granularity/precision of the answer you want.
Just do a manual delete to start with only those two near polyline segments and begin with the search at one endpoint.
Set the number of iterations of the for each loop to get desired granularity/precision of the answer you want.
Just do a manual delete to start with only those two near polyline segments and begin with the search at one endpoint.
Edited by BabaJ - Nov. 17, 2022 11:36:11
- SWest
- Member
- 313 posts
- Joined: Oct. 2016
- Offline
OdFotan
It isn't a point where the lines nearly intersect.
How to find the closest distance in the most resource-efficient way ?
Hi, just for fun I had a go, not really expecting very much.
This reminded me of some javascript code I did once that determined the distance between a bunch of bouncing balls. That is why I wanted to test this out.
However, as you mention there is no point exactly at the closest distance. So one idea I had was to first find the points that was closest, and then make a new line pair only for those points. These lines should be resampled to any desired detail. Then finally the distance is measured to the given accuracy level.
Although I do not think we will use Python for this, I just played with the numbers, and share it just for fun.
Edit: After thinking a bit about this, probably the entire lines should be resampled first, if there is no node/function that can simply "walk/follow" the entire lines and check the distances.
Edited by SWest - Nov. 17, 2022 17:31:41
Interested in character concepts, modeling, rigging, and animation. Related tool dev with Py and VEX.
- npetit
- Staff
- 399 posts
- Joined: Feb. 2008
- Offline
Here's some VEX that might help
Then all you need is the length of Pa - Pb.
If you're looking for distance between 2 segments, then a quick internet search yields plenty of examples:
https://stackoverflow.com/questions/2824478/shortest-distance-between-two-line-segments [stackoverflow.com]
#define EPSILON 0.0000001 // Given 2 lines such as line1 passes through P1 & P2, and line2 passes through P3 & P4, // find the segment intersecting the 2 lines passing through the point Pa on line1, and Pb on line2 // mua is the signed distance of the intersection point on line1 to P1 // mub is the signed distance of the intersection point on line2 to P3 // returns 1 in case of success, 0 otherwise (2 lines are parallel) int LineLineIntersect(vector P1, P2, P3, P4, Pa, Pb; float mua, mub) { vector p13 = P1 - P3; vector p43 = P4 - P3; if (length(p43) < EPSILON) return 0; vector p21 = P2 - P1; if (length(p21) < EPSILON) return 0; float d1343 = dot(p13, p43); float d4321 = dot(p43, p21); float d1321 = dot(p13, p21); float d4343 = dot(p43, p43); float d2121 = dot(p21, p21); float denom = d2121 * d4343 - d4321 * d4321; if (abs(denom) < EPSILON) return 0; float numer = d1343 * d4321 - d1321 * d4343; mua = numer / denom; mub = (d1343 + d4321 * mua) / d4343; Pa = P1 + (p21 * mua); Pb = P3 + (p43 * mub); return 1; }
Then all you need is the length of Pa - Pb.
If you're looking for distance between 2 segments, then a quick internet search yields plenty of examples:
https://stackoverflow.com/questions/2824478/shortest-distance-between-two-line-segments [stackoverflow.com]
- SlowlyLearningMath_houGuy
- Member
- 3 posts
- Joined: Aug. 2021
- Offline
npetit
Here's some VEX that might help
At a quick glance, is something like this ‘KD tree’ involved there?
https://youtu.be/BK5x7IUTIyU [youtu.be]
I recently saw this video but I am still very new to math so. But that video also seems to focus ‘from one point’ (gonna study your code later).
Edited by SlowlyLearningMath_houGuy - Nov. 21, 2022 11:01:59
- willh
- Member
- 134 posts
- Joined: Dec. 2006
- Offline
- SWest
- Member
- 313 posts
- Joined: Oct. 2016
- Offline
-
- Quick Links