Approximate Obstacle Ridge Method for Smooth, Fast Routing

[seveibar]

The method works like this:

Compute f(x,y), where f(x,y)=1 means there's an obstacle and f(x,y)=-1 means there's no obstacle. You must approximate this function using sum of sin weighted sin waves.

Compute f'(x,y)

You can use fixed parameter counts to make these constant-time (at the risk of over-approximating obstacles)

You can set obstacles to a higher value than 1 for more margin.

Algorithm:

1. Assume path from A to B
2. Compute x(t), where x(t=0)=A.x and y(t=0)=A.x, t=1 -> B
3. Find any zero crossings. If no zero crossing you're done
4. If zero crossing, compute the ridge function

Smooth as necessary, smoothing is a weighted equation of path complexity to cost. You can compute the integral over the path (the area under the path can be considered to approximate proximity to obstacles)

There are other functions other than sum of weighted sins (weighted periods too like FFTs) that can work, weighted spheres etc.

---

There is another interesting method where we don't use segments, but instead try to solve for our new functions x(t) and y(t) by minimizing the cost as they go across f(x,y)