Example 6: Refinement in action
Zig-zag heavy example that shows the algorithm computing
the exact continuous monotone Fréchet morphing, using refinement.
| P |
19 |
15.882300580771243 |
| Q |
30 |
19.92177634706533 |
| Fréchet |
0.9211999170149421 |
0 |
| VE Fréchet |
0.8999999999999988 |
72 |
Animation: Fréchet morphing
This is the animation of the morphing computed
that is both continuous and monotone.
Animation: VE Retractable Fréchet
This is the animation of the VE retractable morphing. It is potentially not monotone (but it is continuous.
Free space diagram heatmap:
graph + free space
[PDF]
: graph
[PDF]
With the grid
VE-Fréchet Retractable solution:
Monotonized...
Fréchet cont+monotone solution:
Discrete Fréchet
Generated by sampling 10 points along each edge...
The resulting morphing - extended to continuous:
Specifically, to get a smooth animation, the
leash is shown as moving continuously, by
interpolating between the discrete locations.
The discrete retractable version
The discrete dynamic time warping
P # vertices: 198
P # vertices: 203
DFréchet iters : 40194
Retract DFréchet iters : 3418
Refinement for removing monotonicity
By introducing vertices in the middle of parts of the curves that are being traversed in the wrong direction, one can refine the solution, till effectively reaching the optimal monotone solution. This process is demonstrated below. As one can see, the error is negligible after a few (say four) iterations. After that, it becomes a bit pointless.
We emphasize that a monotone morphing can
always
be extracted, by monotonizing the current
solution.
This is easy and fast to do, and is the error
accounted for in the below graphics.
More info
Animation: Fréchet morphing as morphing
2025-03-08 20:28:18