1

Is there a method of defining something that roughly resembles a curve (in 2D plane) and allows to rapidly find the nearest point on the curved line to another point?

Neither Bezier nor Catmull-Rom curves meet that second criteria because you need either an iterative or some highly complex algorithm to find nearest. The performance requirement comes from having to calculate this for every pixel in an image for a special image processing step.

What I have as a proof of concept is representing every curve as a circle segment. That is fast, but limits the types of possible curves a lot.

DragonGamer
  • 834
  • 3
  • 9
  • 27
  • Interesting question, however, more suitable for math.stackexchange.com instead, I think. – Robert Dodier Aug 30 '22 at 22:47
  • see "duplicate" [Is it possible to express "t" variable from Cubic Bezier Curve equation?](https://stackoverflow.com/a/60113617/2521214) the final GLSL version is highly optimized so in order to understand it read the whole stuff first... the input is point position and output is cubic curve parameter and position of nearest point on cubic curve – Spektre Aug 31 '22 at 07:44
  • Does this answer your question? [Is it possible to express "t" variable from Cubic Bezier Curve equation?](https://stackoverflow.com/questions/60073813/is-it-possible-to-express-t-variable-from-cubic-bezier-curve-equation) – Spektre Aug 31 '22 at 07:45
  • curious how you feel circles would change things: that still buys you very different pixel distances for constant angle intervals, so you're still going to have to iterate to find the actual next "pixel". Or are you talking about projecting a point onto a curve? – Mike 'Pomax' Kamermans Aug 31 '22 at 15:20
  • "as a circle segment" *one* circle segment? (i.e. one arc)? you should have several. then "draw" perpendiculars, subdivide your image into areas belonging each to a certain arc, kind of like in Voronoi diagram, then for each pixel/point find which area it belongs to and calculate the offset from that arc. if you work with a lot of pixels don't start anew for each point, but use the last point's area as the starting point. see "arc splines". – Will Ness Oct 04 '22 at 22:01

0 Answers0