---
jupyter:
  description: 'The Hausdorff distance with planex2d: how far a regular polygon lies from its circle, against the
    sagitta r (1 - cos(pi/n)), Archimedes'' 96-gons around pi, and the chord tolerance of a tessellation.'
---

# The Hausdorff distance

How far does a polygon lie from the circle it stands for? The Hausdorff distance answers it: the largest distance from
a point of either curve to the other, so how far apart the two are at their worst. For a regular polygon of $n$ sides
inscribed in a circle of radius $r$, the worst point is the middle of an arc, and its distance to the chord below it
is the sagitta

$$d_H = r\left(1 - \cos\frac{\pi}{n}\right) \approx \frac{\pi^2 r}{2 n^2}.$$

The same number is the chord tolerance with which a CAD program or a mesh generator turns a circle into segments.
Archimedes used polygons of 96 sides around and inside a circle to bound $\pi$.

`px.measurements.Hausdorff(a, b)` measures it between two named parts of one object.

![A hexagon and a dodecagon in their circles, the gaps between them shaded and the Hausdorff distance in red](../_static/gallery/hausdorff-distance.png){.result}

```python
import math

import planex as px
```

```python nbsphinx="hidden"
from docs_figures import Chart, Row
```

## A polygon in its circle

The circle has a radius of 10, and `Polygon` draws a regular polygon with its corners on it. Glued together, the
circle and the polygon keep their names, and the Hausdorff distance between the two parts follows the sagitta:

```python
circle = px.Circle((0, 0), 10)
circle.name = "circle"


def hausdorff(n):
    polygon = px.QuickSketch().Polygon((0, 0), 10, n).Wire()
    polygon.name = "polygon"
    both = px.Glue([circle, polygon])
    return both.Measure(px.measurements.Hausdorff("circle", "polygon")), polygon


for n in (6, 12, 24, 96):
    print("n", n, "| Hausdorff", hausdorff(n)[0], "| sagitta", 10 * (1 - math.cos(math.pi / n)))
```

```python nbsphinx="hide-input"
Row(*[(px.Compound([circle, hausdorff(n)[1]]), f"{n} sides", {"fill": False}) for n in (6, 12)],
    caption="A hexagon and a dodecagon in their circle")
```

Doubling the sides divides the distance by about four, as $\pi^2 r / (2 n^2)$ says (Figure 2):

```python nbsphinx="hide-input"
sides = [6, 8, 12, 16, 24, 32, 48, 64, 96]
Chart("number of sides", "Hausdorff distance",
      dots={"planex2d": (sides, [hausdorff(n)[0] for n in sides])},
      lines={"the sagitta r (1 - cos(π/n))": (sides, [10 * (1 - math.cos(math.pi / n)) for n in sides])},
      title="A regular polygon against its circle of radius 10")
```

## Archimedes' 96-gons

The polygon of 96 sides inside the circle is shorter than the circle, and the one around it, with its corners at
$r / \cos(\pi/96)$, is longer. Their perimeters bound $\pi$. Archimedes, bounding the square roots on the way by
fractions, stated $223/71 < \pi < 22/7$, a little wider than the polygons themselves:

```python
inside = px.QuickSketch().Polygon((0, 0), 10, 96).Wire()
around = px.QuickSketch().Polygon((0, 0), 10 / math.cos(math.pi / 96), 96).Wire()
print("inside", inside.mass / 20, "| around", around.mass / 20)
print("Archimedes", 223 / 71, "<", math.pi, "<", 22 / 7)
```

## A chord tolerance

A tessellation goes the other way: from a tolerance to a number of segments. For a chord height of at most $t$, a
circle needs at least $n = \lceil \pi / \arccos(1 - t/r) \rceil$ segments. `Polylines(tol)` turns the circle into such a
polyline, and its Hausdorff distance from the circle stays within the tolerance:

```python
for tol in (0.1, 0.01, 0.001):
    points = circle.Polylines(tol)[0][:-1]
    polyline = px.FromPolyline(points, closed=True)
    polyline.name = "polyline"
    distance = px.Glue([circle, polyline]).Measure(px.measurements.Hausdorff("circle", "polyline"))
    print("tolerance", tol, "| segments", len(points), "| at least", math.ceil(math.pi / math.acos(1 - tol / 10)),
          "| Hausdorff", distance)
```

```python nbsphinx="hidden"
import sys
sys.path.insert(0, "..")
import matplotlib.pyplot as plt
import numpy as np
from docs_figures import FACE, INK, RED
from gallery import save_figure
fig, axes = plt.subplots(1, 2, figsize=(6.4, 3.4))
for ax, n in zip(axes, (6, 12)):
    distance, polygon = hausdorff(n)
    disc = px.Face([circle])
    (disc - px.Face([polygon])).Plot(ax=ax, face_col="#f2b8bf", line_col=INK, arc_col=INK, legend=False)
    px.Face([polygon]).Plot(ax=ax, face_col=FACE, line_col=INK, legend=False)
    edge = polygon.edges[0]
    mid = (np.asarray(edge.start)[:2] + np.asarray(edge.end)[:2]) / 2
    rim = 10 * mid / np.linalg.norm(mid)
    ax.plot(*np.c_[mid, rim], color=RED, lw=2.2, zorder=5)
    ax.plot(*np.c_[mid, rim], "x", color=RED, ms=7, mew=2, zorder=6)
    ax.set_aspect("equal")
    ax.axis("off")
save_figure(fig, "hausdorff-distance", bare=True)
```