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.

import math

import planex as px

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:

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)))

n 6 | Hausdorff 1.3397459621556165 | sagitta 1.339745962155613
n 12 | Hausdorff 0.34074173710931777 | sagitta 0.3407417371093169
n 24 | Hausdorff 0.08555138626189761 | sagitta 0.08555138626189618
n 96 | Hausdorff 0.005354125236346173 | sagitta 0.005354125236343155

(a) 6 sides

(b) 12 sides

Figure 1: 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):

Figure 2: 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:

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)

inside 3.1410319508905093 | around 3.1427145996453656
Archimedes 3.140845070422535 < 3.141592653589793 < 3.142857142857143

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:

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)

tolerance 0.1 | segments 24 | at least 23 | Hausdorff 0.0855513862618975
tolerance 0.01 | segments 72 | at least 71 | Hausdorff 0.009517784181424361
tolerance 0.001 | segments 224 | at least 223 | Hausdorff 0.0009834824042516286