I have a user defined path which a user has hand drawn - the distance between the points which make up the path is likely to be variant.
I would like to find a set of points along this path which are equally separated.
Any ideas how to do this?
Asked
Active
Viewed 8,963 times
8
-
A curved path, or a piecewise-linear path? (The first one is more difficult.) – J. M. ain't a mathematician May 03 '11 at 12:05
-
a piecewise-linear path – MathsFailure May 03 '11 at 12:21
-
In case someone else finds this question after 7 years, this answer provided exactly the solution I was looking for. – Joost Sep 09 '18 at 14:49
2 Answers
3
If you measure distance along the path it is no different from a straight line. If the length is $L$ and you want $n$ points (including the ends) you put a point at one end and every $\frac{L}{n-1}$ along the way. If you measure distance as straight lines between the points there is no guarantee of a solution, but you could just start with this guess (or something a bit smaller) and "swing a compass" from each point, finding where it cuts the curve (could be more than once-this is problematic), and see how close to the end you wind up. Then a one-dimensional rootfinder (the parameter is the length of the radius) will do as well as possible.
Ross Millikan
- 374,822
1
You're looking for an arc-length parametrization that you can sample uniformly. See http://groups.google.com/group/comp.graphics.algorithms/msg/c7025fd53b18db94 .
You probably need to smooth the input data before doing this. See for instance Efficient Curve Fitting. See also a summary.
lhf
- 216,483
-
He said his path is piecewise linear, so I'm not sure how unit-speed applies. – J. M. ain't a mathematician May 03 '11 at 13:13
-
@J.M., it certainly does apply because the lengths of each piece are likely to be different. You cannot simply sample each piece uniformly. OTOH, it's certainly much simpler to find an arc-length parametrization for a piecewise linear curve, though not entirely trivial. – lhf May 03 '11 at 13:20