# Class NumericalPath

A numerical approximation of a ParametricPath providing various functions to find points based on distance along the path and also the slope, normal, and derivatives at those points. Stores a representation of the ParametricPath as a table of values; interpolation is used to find values between table entries.

Many of the NumericalPath methods pass information via a PathPoint for both input and output.

See the myPhysicsLab page showing the Roller Coaster for more about the math involved here.

## Path Length 'p'

Points on the path are usually specified by the path distance to that point from a designated starting point on the path. The starting point is specified by the parametric t-value given by ParametricPath.getStartTValue. At that point the path distance is zero.

Path distance is abbreviated here as `p`, so you see methods named like map_p_to_slope which finds the slope at a point specified by the `p` value of the point.

## Table of Numerical Values

The path is specified by the parametric function `f(t) = (x(t), y(t))` which is defined by the ParametricPath provided to the constructor. We build the table by varying the parameter `t` from `tLow` to `tHigh` which are given by the ParametricPath methods ParametricPath.getStartTValue and ParametricPath.getFinishTValue. The table stores information about each sample point such as

• path distance `p`
• position `x,y` in space
• derivative of `x,y` with respect to `p`
• slope vector
• normal vector
• derivative of normal vector with respect to `p`

After the table is created, the parametric function `f(t)` and `tLow`, `tHigh` are no longer used, instead we interpolate data from the table as needed.

Most of the NumericalPath functions start with the `p` value to specify the point, and the other values are interpolated accordingly.

Some functions result in finding a `p` value from a location in space. For example, when the user clicks the mouse somewhere we need to find the nearest point on the path. See findNearestLocal and findNearestGlobal.

## Slope of Path

The slope is found from the relation `dy/dx = (dy/dp) / (dx/dp)`. Because we store these derivatives of `x` and `y` with respect to `p` in the table, we can interpolate those at a given point and divide them to get the slope there.

The method map_p_to_slope figures out the slope in this way, and stores it in the `slope` property of the PathPoint.

## Direction of Path

Sometimes it is important to know the direction of the path: i.e. as `p` increases, does `x` increase or decrease? This is determined from the table data as needed. For vertical sections, the question becomes whether as `p` increases, does `y` increase or decrease.

The method map_p_to_slope figures out the direction in this way, and stores it in the `direction` property of the PathPoint.

## Design Note: How Not To Calculate Slope

A previous version stored the slope, `dy/dx`, at each point in the table. It turns out to be difficult-to-impossible to interpolate on slope numbers. The slope goes to infinity on vertical sections. You can get around that by interpolating on reciprocal of slope. But a persistent problem is that you can run into situations which are not appropriate for interpolation with a cubic polynomial (which we do with the private static method `NumericalPath.interp4`).

For example, consider the following case with four values evenly spaced horizontally, but where the `y` values are highly variable:

``````[[0.01, 1E-6], [0.02, 6E-6], [0.03, 1E-3], [0.04, 1E3]]
``````

The `y` values represent slope and are monotonically increasing. But a cubic polynomial fitted to those points will swing wildly between the first 3 points giving a non-monotonic function that crosses over to negative values.

The solution is to not store slope directly, instead store `dy/dp` and `dx/dp` separately and get the slope at any point from their ratio. Both of those seem to be compatible with polynomial interpolation.

TO DO Use a curve to estimate the path distance when making the table.

TO DO PointsIterator should be able to iterate over entire table. That is, parameterize it so that you can say how many sample points you want (less for drawing).

TO DO Provide methods to return copy of the entire table as an array (or the columns).

TO DO ??? Should we always have p increase in the pvals array? This would make the code simpler. And I can't think of any reason to allow pvals to decrease.

TO DO NumericalPath doing makeTable inside of constructor: this is bad because you can’t do something as simple as pass radius to Circle constructor. Also, might want to adjust path later on (translate for example, or scale or rotate). So might want to have the makeTable thing be callable anytime.

## Constructors

• #### Parameters

• ##### path: ParametricPath

the ParametricPath to represent with a numerical table

• ##### `Optional`opt_tableLength: number

optional number of points to store in table; default is 9000.

## Properties

bounds: DoubleRect = DoubleRect.EMPTY_RECT

bounds of the path, in simulation coordinates

dxvals: number[]

dx/dp

dyvals: number[]

dy/dp

endPoint_: PathPoint

end point is used for linear extension, see map_p_to_slope

nxVals: number[]

normal x at mid-point

nxpVals: number[]

derivative of normal w.r.t. p at mid-point

nyVals: number[]

normal y at mid-point

nypVals: number[]

derivative of normal w.r.t. p at mid-point

plen: number = 0

total length of path

pvals: number[]

p, path distance. Is public only because of PointsIterator.

startPoint_: PathPoint

start point is used for linear extension, see map_p_to_slope

tableLength_: number

Number of points stored in table.

xvals: number[]

x, horizontal position. Is public only because of PointsIterator.

yvals: number[]

y, vertical position. Is public only because of PointsIterator.

DATA_POINTS: 9000 = 9000

Number of data points to record for the path.

ID: number = 1

Counter used for naming SimObjects.

## Methods

• Calculates the three point numerical derivative with respect to path distance, `p`. This numerical derivative can handle having the `p` values being unevenly spaced.

The three points used to calculate the derivative are:

``````(pvals[k], yy[k])
(pvals[k+1], yy[k+1])
(pvals[k+2], yy[k+2])
``````

The derivative can be calculated to correspond to the derivative of any of those three points. These are called the left, center, and right derivatives respectively. Usually the center derivative is used, but at table endpoints we need to use the left or right derivative. For example, to get the derivative at the first point in the table, use the left derivative. To get the derivative at the last point in the table, use the right derivative.

See equation 4.3, page 171, of Numerical Analysis, 6th edition by Burden, Faires in section 4.1 Numerical Differentiation for the three-point differentiation formula used here.

#### Parameters

• ##### k: number

the index into the table for the first point of the derivative

• ##### type: number

selects left, center, or right derivative as j = 0, 1, or 2

#### Returns number

three-point derivative of array yy

• Returns the distance-squared between the given point and a point on the path.

#### Parameters

• ##### point: GenericVector

the point of interest

• ##### i: number

index of point on the path

#### Returns number

distance-squared between the given point and a point on the path

• Returns the distance-squared between the given point and an interpolated point on the path.

#### Parameters

• ##### point: GenericVector

the point of interest

• ##### p: number

path position

• ##### k: number

index to start search at

#### Returns number

distance-squared between the given point and an interpolated point on the path.

• Finds the closest point in the path table to the given `x,y` position in `point`. This is a global search for the closest point over the entire path. This does not interpolate between table entries, see findNearestLocal for a more accurate mapping using interpolation.

#### Parameters

• ##### point: GenericVector

the `x,y` position to search for

#### Returns PathPoint

a PathPoint with the `x, y, p`, and `idx` fields are set to the closest point in the table.

• Finds the closest point on the interpolated path to the `target` position, starting from a given index into the table. This is a local search around the current position in the path, NOT a global search over the entire path for the very closest point. See findNearestGlobal. The algorithm used here moves from the starting point in the direction that reduces the distance between `target` and the path, until the distance is at a minimum. This behavior is useful so that the current path point does not “hop” across to other parts of the path when a path crosses itself.

Preserves the `p`-value (distance along the path) in the PathPoint for closed loop paths when crossing the “stitch” point where the loop reconnects. Therefore the p-value can be any value, not just from 0 to length of path. This is done to simplify the detection of collisions by for example PhysicsPathAction. Note that this feature will fail if the point is moving very rapidly around the path.

Outline of the algorithm:

``````We seek the p that gives minimum y value.
d = initial spacing between p values
p = initial p value
do {
y0 = y(p-d);  y1 = y(p);  y2 = y(p+d)
if (y0 < y1) {
p = p - d;  // shift 'left'
} else if (y2 < y1) {
p = p + d;  // shift 'right'
} else {
d = d/2;  // reduce search range
}
} while (d > tiny);
``````

#### Parameters

• ##### target: GenericVector

the point of interest

• ##### ppt: PathPoint

the PathPoint used for input and output; the table index `ppt.idx` is used to start the search; the `p` value and table index are stored in `ppt`.

#### Returns void

• Finds point p2 on the path that is a given distance from given point p1. We start the search by finding the point on the path nearest to given point p2. The initial location of p2 determines which side of the path of p1 we find p2 on.

#### Parameters

• ##### p1: Vector

the fixed point

• ##### p2: Vector

starting location for the search

• ##### x: number

the desired distance between p1 and p2.

#### Returns Vector

a point on on the path that is distance x from p1.

• Returns last path distance value of last point in this NumericalPath. Points on the path are referenced by their distance along the path. Path distance increases from start to finish.

#### Returns number

the ending path distance value

• Returns an iterator over points in the Path.

#### Parameters

• ##### numPoints: number

desired number of points

#### Returns PathIterator

an iterator over points in the Path.

• Name of this SimObject, either the language-independent name for scripting purposes or the localized name for display to user.

The language-independent name should be the same as the English version but capitalized and with spaces and dashes replaced by underscore, see Util.toName, nameEquals.

The name should give an idea of the role of the SimObject in the simulation. This allows us to to treat an object in a special way depending on its name. For example, we might use the name to decide what type of DisplayObject to create to represent the SimObject.

#### Parameters

• ##### `Optional`opt_localized: boolean

`true` means return the localized version of the name; default is `false` which means return the language independent name.

#### Returns string

name of this SimObject

• Returns a sequence number which changes when the Path changes.

#### Returns number

sequence number which indicates when Path changes

• Returns starting path distance value of first point in this NumericalPath. Points on the path are referenced by their distance along the path. Path distance increases from start to finish.

#### Returns number

the starting path distance value (usually zero)

• Returns number of points stored in the path table.

#### Returns number

number of points stored in the path table

• Whether this NumericalPath is a closed loop, ending at the same point it starts.

#### Returns boolean

Whether this NumericalPath is a closed loop

• Returns a `p` value that is in the range of the path. For a path that is not a closed loop, this returns start or end of the path when the `p` value is outside of the path range. For closed loops this returns path distance `p` modulo the total path length, see mod_p.

#### Parameters

• ##### p: number

distance along the path

#### Returns number

the equivalent path distance `p` position, limited to be within the path.

• Finds the table index corresponding to the given path distance `p` value, by doing a linear search. In theory, this is faster than binarySearch when the index is close to the `p` value.

TO DO test if we actually save operations using linear search

#### Parameters

• ##### p: number

the `p`-value to search for in the table

• ##### k: number

the index into the table to start searching at

#### Returns number

index `j` into table such that `pvals[j] <= p < pvals[j+1]`

• Makes the table of path data.

TO DO for closed loop we can use the regular centered three-point formula!

#### Returns void

• Returns the index in the path table just before the given `p` value. Usually the returned index point is at or just before the given `p` value. However if the `p` value is before the first entry then this returns index of 0.

More precisely stated: returns largest index `k` in table such that `pvals[k] <= p`, or returns 0 if `p < pvals[0]`.

#### Parameters

• ##### p: number

path value to search for

#### Returns number

index in the path table just before the given `p` value

• Given a path location `p`, calculates all the corresponding PathPoint fields such as `(x,y)` location, slope, derivative of `(x,y)` with respect to `p`, normal, derivative of normal, etc. The desired path location is specified in `PathPoint.p`. Optionally calculates the radius of curvature if `PathPoint.radius_flag` is set.

For a non-closed loop path: when the `p` value is before the start of the path, or after the end of the path, we use a linear extension of the path to find the point.

Interpolates values in the table to find corresponding values of location, slope, etc.

TO DO Use the new dxdp and dydp fields to calc radius. Find radius of curvature for the four points on circle where tangent is horizontal or vertical. Currently we get radius is infinite there which is wrong.

#### Parameters

• ##### ppt: PathPoint

the PathPoint used for input and output; `PathPoint.p` is the input path position. Optionally calculates the radius of curvature if `PathPoint.radius_flag` is set.

#### Returns void

• Returns the Vector position corresponding to the given path distance `p` value.

#### Parameters

• ##### p: number

the path distance value to search for

#### Returns Vector

the Vector position corresponding to the given path distance `p` value

• Returns the `x` value corresponding to the given path distance `p` value.

#### Parameters

• ##### p: number

the path distance value to search for

#### Returns number

the `x` value corresponding to the given path distance `p` value

• Returns the `y` value corresponding to the given path distance `p` value.

#### Parameters

• ##### p: number

the path distance value to search for

#### Returns number

the `y` value corresponding to the given path distance `p` value

• Returns the path distance `p` value corresponding to the given `x` value.

#### Parameters

• ##### x: number

the `x` value to search for

#### Returns number

the path distance `p` value corresponding to the given `x` value

#### Throws

if `x` values are not monotonically increasing or decreasing

• Returns the `y` value corresponding to the given `x` value.

#### Parameters

• ##### x: number

the `x` value to search for

#### Returns number

the `y` value corresponding to the given `x` value

#### Throws

if `x` values are not monotonically increasing or decreasing

• Uses the `x` value of the PathPoint to find a point on the path, then interpolates to find corresponding `y` and `p` values.

#### Parameters

• ##### ppt: PathPoint

the PathPoint used for input and output; `ppt.x` is the input `x` value searched for; `ppt.y` and `ppt.p` are set accordingly.

#### Throws

if `x` values are not monotonically increasing or decreasing

• Returns path distance `p` modulo total path length for closed loops. For paths that are not closed, this has no effect: it returns the given `p` value even when it is outside of the range of the path.

For example, consider a circle of radius 1; its total path length is `2*pi` and the path starts with `p` at zero. Then `mod_p(2*pi + 1)` returns 1, but `mod_p(pi)` returns `pi`.

#### Parameters

• ##### p: number

distance along the path

#### Returns number

the equivalent path distance `p` position, modulo total path length for closed paths

• Returns the table index adjusted at end points according to whether the table loops around or not.

#### Returns number

• Whether this SimObject has the given name, adjusting for transformation to the language-independent form of the name, as is done by Util.toName.

#### Parameters

• ##### name: string

the English or language-independent version of the name

#### Returns boolean

whether this SimObject has the given name (adjusted to language-independent form)

#### Returns void

• Sets the expiration time, when this SimObject should be removed from the SimList. This is intended for temporary SimObjects that illustrate, for example, contact forces or collisions.

#### Parameters

• ##### time: number

the expiration time, in time frame of the Simulation clock

#### Returns void

• Returns true if the given SimObject is similar to this SimObject for display purposes. SimObjects are similar when they are the same type and nearly the same size and location. Mainly used when showing forces - to avoid adding too many objects to the display. See SimList.getSimilar.

#### Parameters

• ##### obj: SimObject

the SimObject to compare to

• ##### `Optional`_opt_tolerance: number

the amount the object components can differ by

#### Returns boolean

true if this SimObject is similar to `obj` for display purposes

• Returns the distance between 3 neighboring p-values in the table at the k-th table entry.

#### Parameters

• ##### k: number

the index into the table

#### Returns number

returns pval[k+1] - pval[k-1], although the indexes are adjusted at table end points.

• Returns a minimal string representation of this object, usually giving just identity information like the class name and name of the object.

For an object whose main purpose is to represent another Printable object, it is recommended to include the result of calling `toStringShort` on that other object. For example, calling `toStringShort()` on a DisplayShape might return something like this:

``````DisplayShape{polygon:Polygon{'chain3'}}
``````

#### Returns string

a minimal string representation of this object.

• Finds where in the array the given value is located using a binary search algorithm. Given an array `arr[0..n-1]`, and given a value `x`, binarySearch returns a value `i` such that `arr[i] <= x` and `x < arr[i+1]`. The array must be monotonic, either increasing or decreasing.

TO DO should this return 0 or n-1 when x is outside the array?

#### Parameters

• ##### arr: number[]

the array of values, must be monotonic increasing or decreasing

• ##### x: number

the value to find

#### Returns number

index of the closest value in the table that is less than or equal to x, or -1 or n is returned to indicate that x is out of range.

• Returns the y-value corresponding to the x-value in the 4 point (3rd order) polynomial interpolant formed from the 4 values in `xx` and `yy` arrays at indexes `k, k+1, k+2, k+3`. The four points used for interpolation are therefore

``````(xx[k], yy[k])
(xx[k+1], yy[k+1])
(xx[k+2],  yy[k+2])
(xx[k+3], yy[k+3])
``````

See Introduction to Scientific Computing by Charles F. Van Loan, chapter 2 Polynomial Interpolation p. 77.

### Derivation of quadratic interpolant using Newton polynomials.

``````Let our three datapoints be (x1,y1), (x2,y2), (x3,y3), (x4,y4)
Our polynomial will be
p(x) = a1 + a2(x-x1) + a3(x-x1)(x-x2) + a4(x-x1)(x-x2)(x-x3)
The first derivative is
p'(x) = a2 + a3(2x-x1-x2) + a4((x-x2)(x-x3) + (x-x1)(2x-x2-x3))
The coefficients are given by solving the system:
a1 = y1
a1 + a2(x2-x1) = y2
a1 + a2(x3-x1) + a3(x3-x1)(x3-x2) = y3
a1 + a2(x4-x1) + a3(x4-x1)(x4-x2) + a4(x4-x1)(x4-x2)(x4-x3) = y4
Solving this system gives:
a1 = y1
a2 = (y2-y1)/(x2-x1)
a3 = (y3 - y1 - a2(x3-x1))/((x3-x2)(x3-x1))
a4 = (y4 - y1 - a2(x4-x1) - a3(x4-x1)(x4-x2))/((x4-x1)(x4-x2)(x4-x3))
``````

#### Parameters

• ##### xx: number[]

array of x-values

• ##### yy: number[]

array of y-values

• ##### x: number

the x value for which we want to find the corresponding y-value

• ##### k: number

the index into the arrays where to get the 4 array values

• ##### _closedLoop: boolean

true when the array wraps around at the end points

#### Returns number

the interpolated y-value corresponding to the requested x-value

• Returns `true` if the given array is monotonically increasing or decreasing.

#### Parameters

• ##### arr: number[]

array of values

#### Returns boolean

`true` if the given array is monotonically increasing or decreasing.

Generated using TypeDoc