0

I have a problem with a relatively simple math problem. I have a vector with points in 2d space. Also there is a 2D curve using a spline representation. Now I would like to move the points along the normal vector. The points and the curve are shown in the figure 1. Also I would like to know the distance between these points and the curve in normal direction as shown in the figure.

I am trying to solve the problem in Python and numpy library. Unfortunately I'm quite a beginner. Is there anyone who has an idea for me, how I can calculate the distance in normal direction between the individual points and the curve?

thanks a lot

tingeltangel
  • 1
  • 2

2 Answers2

1

Method for computing normals

In 2D, the normal is any vector orthgonal to the tangent. For most popular splines, there is a closed form for the tangent. If you don't have that, you can compute it numerically.

Computing it numerically: For a function p(s) which returns points on the spline as a function of the scalar s, tangent_at_s = (p(s + e) - p(s - e)) / (2 * e), where e is a small but nonzero number. Say 1e-6.

You can get a normal vector by rotating tangent_at_s 90 degrees. In 2D, that is easy: normal_at_s = [-tangent_at_s.y, tangent_at_s.x]. Divide by the norm of n to get a unit normal.

Code for computing normals

import numpy as np

def p(s):
   '''p(s) returns an np.array of size 2. A point on the spline.
   s + e is a different point for all s within the spline, and nonzero e. 
   '''
   return a_point_on_the_spline

def get_unit_normal(p, s):
    # Compute tangent by central differences. You can use a closed form tangent if you have it.
    tangent_at_s = (p(s + e) - p(s - e)) / (2 * e)
    normal_at_s = np.array([-tangent_at_s[1], tangent_at_s[0]])
    unit_normal_at_s = normal_at_s / np.linalg.norm(normal_at_s)

my_normal = get_unit_normal(p, 0.1)

To translate a point at p(s) along the normal vector, you can just construct a point, p'(s) = p(s) + d_along_normal * get_unit_normal(p, s). The distance to the original point is norm(p'(s) - p(s)).

Distance to curve in general

The shortest segment between a point and a curve is always either perpendicular to the curve, or attached to one of the curve endpoints. You can compute a decent approximation by iterating over nearly spaced points on the curve, and finding the point on the curve that minimizes distance to your query point.

For a more accurate estimate, you might check with large spacing, and then use a Newton method to find the minimum in small segments of the curve.

Jacob Panikulam
  • 1,196
  • 1
  • 9
  • 12
0

I'd split problem to two problems: 1) finding normal line to curve (points), 2) finding line and spline intersection.

First one is simple: take two consecutive points, find phi = atan2((y2 - y1) / (x2 - x1)) - its angle between x axis and tangent line, psi = phi +- pi / 2 is angle betveen curve and normal line, solve y1 = tan(psi) * x1 + b for b and you get line equation y = tan(psi) * x + b.

Second is more complicated. You can try solutions in this question. I'd try to find two points along that line that lies higher and lower than spline and bisect until intersection, but method of finding this two points is not clear to me. Alternatively you can try to find two points of spline on opposite sides to the line and bisect between them.

mugiseyebrows
  • 4,138
  • 1
  • 14
  • 15