Example 30: ZigZag does not math a Zag
Zig-zag heavy example that shows the algorithm computing
the exact continuous monotone Fréchet morphing, using refinement.
| P |
2 |
4.0 |
| Q |
4 |
12.004996878900158 |
| Fréchet |
2.02490183048366 |
0 |
| VE Fréchet |
0.4 |
8 |
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: 21
P # vertices: 22
DFréchet iters : 462
Retract DFréchet iters : 189
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 21:03:32