Plotting Fréchet Free Space Diagrams for Polygonal Curves

by Axel Mosig, 
Departement of Computer Science III, 
University of Bonn, 
June 2003

This notebook provides some helpful tools for handling polygonal curves. First of all, methods for drawing the Fréchet free space of two polygonal curves is provided. This method is enhanced to plotting the difference between two Fréchet free spaces fortwo  different distance values. This is particularly interesting for showing the relations between the discrete and the continuous free space of polygonal curves.

Finally, we provide methods for determining the sampling rate of a polygonal curve as well as functions for computing oversampled versions.

All functions provided in this notebook work for polygonal curves in arbitrary dimensions.

Using the powerful InequalityPlot Function, Mathematica allows to plot Diagrams of the Fréchet free space of two polygonal curves easily. This Notebook provides the major functions to plot such diagrams.

Definitions and Functions

<< Graphics`InequalityGraphics`

We need to compute Euclidean norms, and in particular squared Euclidean norms. To this end, we define two functions:

ENorm[X_] := Sqrt[Sum[Part[X, i]^2, {i, Length[X]}]]

ENormSq[X_] := Sum[Part[X, i]^2, {i, Length[X]}]

As first ingredient for plotting free space diagrams, we plot a signle cell of the  free space diagram.

FreeSpaceCell[p0_, p1_, q0_, q1_, ε_]:=InequalityPlot[ ENormSq[(1 - s)*p0 + s*p1 - (1 - t)*q0 - 
                t*q1] < ε^2, {s,  0,  1}, {t,  0,  1},Axes -> False,DisplayFunction -> Identity,PlotRange -> {{0, 1}, {0, 1}},GridLines -> {{0, 1}, {0, 1}}]

It remains to stick together an array of free space cells to the complete diagram.

FreeSpaceDiagram[P_, Q_, ε_]:=GraphicsArray[ 
Table[
            FreeSpaceCell[P[[i]], P[[i + 1]], Q[[Length[Q] - j]], 
              Q[[Length[Q] - j + 1]], ε],  {j,   1, 
              Length[Q] - 1} ,  {i,  1, Length[P] - 1}],GraphicsSpacing -> 0]

Examples

Finally, we provide two examples.

Show[
      FreeSpaceDiagram[{{1, 0}, {2, 1}, {3, 1}, {2, 2}}, {{1.5, 0}, {1.5, 
            1.5}, {2.5, 1.5}}, 1]]

Show[
      FreeSpaceDiagram[{{1, 0}, {2, 1}, {3, 1}, {2, 2}, {2.2, 1.8}, {4, 
            5}}, {{1.5, 0}, {1.5, 1.5}, {2.5, 1.5}, {3.6, 5.3}}, 
        1.2]]

Sometimes, we want to plot the free space for two different distance bounds in one free space diagram. This can be done using the Functions DoubleFreeSpaceCell and DoubleFreeSpaceDiagram defined in the sequel.

Definitions and Functions

DoubleFreeSpaceCell[p0_, p1_, q0_, 
        q1_, ε_, δ_]:=InequalityPlot[ {ENormSq[(1 - s)*p0 + s*p1 - (1 - t)*q0 - 
                  t*q1] > ε^2, 
            ENormSq[(1 - s)*p0 + s*p1 - (1 - t)*q0 - 
                  t*q1] < δ^2}, {s,  0,  1}, {t,  0,  1},Axes -> False,DisplayFunction -> Identity,PlotRange -> {{0, 1}, {0, 1}},GridLines -> {{0, 1}, {0, 1}}]

DoubleFreeSpaceDiagram[P_, Q_, ε_, δ_]:=GraphicsArray[ 
Table[
            DoubleFreeSpaceCell[P[[i]], P[[i + 1]], 
              Q[[Length[Q] - j]], 
              Q[[Length[Q] - j + 
                    1]], ε, δ],  {j,   1, 
              Length[Q] - 1} ,  {i,  1, Length[P] - 1}],GraphicsSpacing -> 0]

P := {{1, 0}, {2, 1}, {3, 1}, {2, 2}, {2.8, 1.6}, {4, 5}}

Q := {{1.5, 0}, {3.6, 5.3}}

Show[DoubleFreeSpaceDiagram[P, Q, 1.2, 3]]

Finally, we also want to plot not just free space diagrams of polygonal curves, but we also want to paint the polygonal curves themselves.

PCurve[P_, 
        C_] := {
RGBColor[C[[1]], C[[2]], 
          C[[3]]], 
        AbsolutePointSize[
          20], 
{
Table[
Point[P[[n]]], 
{n, 
              Length[P]}
]
}, 
{
RGBColor[0, 0, 
            0], 
{Line[
              P]}
}
}

Show[
Graphics[
Join[
          PCurve[P, {1, 0, 0}], PCurve[Q, {0, 1, 0}]]
], 
      AspectRatio -> 1]