FAILURE MAP
← Case archive

FA-70591 / GIS polygon topology / Open access

Douglas-Peucker simplification of a topology arc: coincident endpoints · case 01

Closed arcs collapse to a single point.

Verified by executionVariant 1 · 8 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

When the endpoints coincide every interior vertex is given distance 0.

THE FAILURE

When the endpoints coincide every interior vertex is given distance 0.

Unsuccessful approach: Manhattan distance overestimates diagonal offsets and keeps vertices within tolerance.

Case contract

Input [points, tol]: an arc as integer [x, y] positions (possibly closed, first == last). Keep both endpoints; recursively (explicit stack) find the interior vertex farthest from the SEGMENT between the current endpoints (projection clamped to the segment; distance to the point itself if the endpoints coincide), taking the first maximum; keep it and split when that distance is strictly greater than tol. Return kept positions in order.

Why this case matters

Shared arcs are simplified once so adjacent polygons stay gap-free; distance and split errors change which boundary vertices survive.

1 / The failure

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    pts, tol = x
    def dist(p, a, b):
        dx, dy = b[0] - a[0], b[1] - a[1]
        if dx == 0 and dy == 0:
            return 0.0
        t = ((p[0] - a[0]) * dx + (p[1] - a[1]) * dy) / (dx * dx + dy * dy)
        t = max(0.0, min(1.0, t))
        return math.hypot(p[0] - a[0] - t * dx, p[1] - a[1] - t * dy)
    keep = [False] * len(pts)
    keep[0] = keep[-1] = True
    stack = [(0, len(pts) - 1)]
    while stack:
        i, j = stack.pop()
        best, idx = -1.0, -1
        for k in range(i + 1, j):
            d = dist(pts[k], pts[i], pts[j])
            if d > best:
                best, idx = d, k
        if idx != -1 and best > tol:
            keep[idx] = True
            stack.append((i, idx))
            stack.append((idx, j))
    return [p for p, f in zip(pts, keep) if f]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('control #0', [[[0, 0], [3, 1], [6, -1], [9, 1], [12, 1], [15, 4], [18, 1], [21, -2], [24, 1]], 2], [[0, 0], [6, -1], [15, 4], [21, -2], [24, 1]]), ('control #1', [[[0, 3], [3, -4], [6, 1], [9, 3], [12, -4], [15, 1], [18, -1]], 1], [[0, 3], [3, -4], [9, 3], [12, -4], [15, 1], [18, -1]]), ('control #2', [[[0, -4], [3, 3], [6, -2], [9, -1], [12, 2], [15, 1], [18, 1]], 0], [[0, -4], [3, 3], [6, -2], [9, -1], [12, 2], [15, 1], [18, 1]]), ('control #3', [[[0, -3], [3, -1], [6, -3], [9, -2]], 3], [[0, -3], [9, -2]]), ('control #4', [[[0, -2], [3, -4], [6, -1], [9, -4], [12, 1], [15, 2]], 3], [[0, -2], [9, -4], [15, 2]]), ('control #5', [[[0, -2], [3, 2], [6, 2], [9, -3], [12, 3], [15, 4], [18, 2], [21, -2]], 0], [[0, -2], [3, 2], [6, 2], [9, -3], [12, 3], [15, 4], [18, 2], [21, -2]]), ('regression #16', [[[0, 0], [4, 4], [8, 0], [4, -4], [0, 0]], 1], [[0, 0], [4, 4], [8, 0], [4, -4], [0, 0]]), ('boundary #27', [[[0, 0], [3, 3], [0, 0]], 5], [[0, 0], [0, 0]])], [('control #3', [[[0, -3], [3, -1], [6, -3], [9, -2]], 3], [[0, -3], [9, -2]]), ('control #4', [[[0, -2], [3, -4], [6, -1], [9, -4], [12, 1], [15, 2]], 3], [[0, -2], [9, -4], [15, 2]]), ('control #5', [[[0, -2], [3, 2], [6, 2], [9, -3], [12, 3], [15, 4], [18, 2], [21, -2]], 0], [[0, -2], [3, 2], [6, 2], [9, -3], [12, 3], [15, 4], [18, 2], [21, -2]]), ('control #6', [[[0, 4], [3, -1], [6, 2], [9, 2], [12, 2]], 3], [[0, 4], [3, -1], [12, 2]]), ('control #7', [[[0, -4], [3, 0], [6, -3], [9, 1], [12, 1], [15, 3]], 2], [[0, -4], [3, 0], [6, -3], [15, 3]]), ('control #8', [[[0, -4], [3, -4], [6, 1], [9, 3], [12, 3], [15, -4]], 1], [[0, -4], [3, -4], [9, 3], [12, 3], [15, -4]]), ('regression #17', [[[0, 0], [6, 1], [6, 7], [0, 6], [0, 0]], 2], [[0, 0], [6, 1], [6, 7], [0, 6], [0, 0]]), ('boundary #28', [[[0, 0], [4, 3], [1, 4], [0, 0]], 5], [[0, 0], [0, 0]])], [('control #6', [[[0, 4], [3, -1], [6, 2], [9, 2], [12, 2]], 3], [[0, 4], [3, -1], [12, 2]]), ('control #7', [[[0, -4], [3, 0], [6, -3], [9, 1], [12, 1], [15, 3]], 2], [[0, -4], [3, 0], [6, -3], [15, 3]]), ('control #8', [[[0, -4], [3, -4], [6, 1], [9, 3], [12, 3], [15, -4]], 1], [[0, -4], [3, -4], [9, 3], [12, 3], [15, -4]]), ('control #9', [[[0, -3], [3, 4], [6, 0], [9, -4], [12, 0], [15, -1], [18, 4]], 0], [[0, -3], [3, 4], [9, -4], [12, 0], [15, -1], [18, 4]]), ('control #10', [[[0, -4], [3, -2], [6, 1], [9, 1]], 2], [[0, -4], [9, 1]]), ('control #11', [[[0, 4], [3, -3], [6, -2], [9, -4], [12, 4], [15, 4], [18, -1]], 2], [[0, 4], [3, -3], [9, -4], [12, 4], [18, -1]]), ('regression #16', [[[0, 0], [4, 4], [8, 0], [4, -4], [0, 0]], 1], [[0, 0], [4, 4], [8, 0], [4, -4], [0, 0]]), ('boundary #27', [[[0, 0], [3, 3], [0, 0]], 5], [[0, 0], [0, 0]])], [('control #9', [[[0, -3], [3, 4], [6, 0], [9, -4], [12, 0], [15, -1], [18, 4]], 0], [[0, -3], [3, 4], [9, -4], [12, 0], [15, -1], [18, 4]]), ('control #10', [[[0, -4], [3, -2], [6, 1], [9, 1]], 2], [[0, -4], [9, 1]]), ('control #11', [[[0, 4], [3, -3], [6, -2], [9, -4], [12, 4], [15, 4], [18, -1]], 2], [[0, 4], [3, -3], [9, -4], [12, 4], [18, -1]]), ('control #12', [[[0, 2], [3, -3], [6, 3], [9, -1]], 1], [[0, 2], [3, -3], [6, 3], [9, -1]]), ('control #13', [[[0, 4], [3, -1], [6, -4], [9, -2], [12, 4], [15, -3], [18, -1], [21, 0]], 3], [[0, 4], [6, -4], [12, 4], [15, -3], [21, 0]]), ('regression #14', [[[0, 0], [10, 0], [14, 3], [20, 0]], 2], [[0, 0], [10, 0], [14, 3], [20, 0]]), ('regression #17', [[[0, 0], [6, 1], [6, 7], [0, 6], [0, 0]], 2], [[0, 0], [6, 1], [6, 7], [0, 6], [0, 0]]), ('boundary #28', [[[0, 0], [4, 3], [1, 4], [0, 0]], 5], [[0, 0], [0, 0]])], [('control #12', [[[0, 2], [3, -3], [6, 3], [9, -1]], 1], [[0, 2], [3, -3], [6, 3], [9, -1]]), ('control #13', [[[0, 4], [3, -1], [6, -4], [9, -2], [12, 4], [15, -3], [18, -1], [21, 0]], 3], [[0, 4], [6, -4], [12, 4], [15, -3], [21, 0]]), ('regression #14', [[[0, 0], [10, 0], [14, 3], [20, 0]], 2], [[0, 0], [10, 0], [14, 3], [20, 0]]), ('regression #15', [[[0, 0], [5, 0], [-6, 1], [10, 0]], 2], [[0, 0], [5, 0], [-6, 1], [10, 0]]), ('regression #16', [[[0, 0], [4, 4], [8, 0], [4, -4], [0, 0]], 1], [[0, 0], [4, 4], [8, 0], [4, -4], [0, 0]]), ('regression #17', [[[0, 0], [6, 1], [6, 7], [0, 6], [0, 0]], 2], [[0, 0], [6, 1], [6, 7], [0, 6], [0, 0]]), ('boundary #18', [[[0, 0], [5, 2], [10, 0]], 2], [[0, 0], [10, 0]]), ('boundary #27', [[[0, 0], [3, 3], [0, 0]], 5], [[0, 0], [0, 0]])]]
for label, args, expected in fixtures[N-1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
control #0[[0, 0], [6, -1], [15, 4], [21, -2], [24, 1]][[0, 0], [6, -1], [15, 4], [21, -2], [24, 1]]Passed
control #1[[0, 3], [3, -4], [9, 3], [12, -4], [15, 1], [18, -1]][[0, 3], [3, -4], [9, 3], [12, -4], [15, 1], [18, -1]]Passed
control #2[[0, -4], [3, 3], [6, -2], [9, -1], [12, 2], [15, 1], [18, 1]][[0, -4], [3, 3], [6, -2], [9, -1], [12, 2], [15, 1], [18, 1]]Passed
control #3[[0, -3], [9, -2]][[0, -3], [9, -2]]Passed
control #4[[0, -2], [9, -4], [15, 2]][[0, -2], [9, -4], [15, 2]]Passed
control #5[[0, -2], [3, 2], [6, 2], [9, -3], [12, 3], [15, 4], [18, 2], [21, -2]][[0, -2], [3, 2], [6, 2], [9, -3], [12, 3], [15, 4], [18, 2], [21, -2]]Passed
regression #16[[0, 0], [0, 0]][[0, 0], [4, 4], [8, 0], [4, -4], [0, 0]]Failed
boundary #27[[0, 0], [0, 0]][[0, 0], [0, 0]]Passed

SHA-256 / 84caf6d859d02a784c8927f5ac51f1e523b56e969b93d900a7807723b5ba4d57

2 / The unsuccessful fix

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    pts, tol = x
    def dist(p, a, b):
        dx, dy = b[0] - a[0], b[1] - a[1]
        if dx == 0 and dy == 0:
            return abs(p[0] - a[0]) + abs(p[1] - a[1])
        t = ((p[0] - a[0]) * dx + (p[1] - a[1]) * dy) / (dx * dx + dy * dy)
        t = max(0.0, min(1.0, t))
        return math.hypot(p[0] - a[0] - t * dx, p[1] - a[1] - t * dy)
    keep = [False] * len(pts)
    keep[0] = keep[-1] = True
    stack = [(0, len(pts) - 1)]
    while stack:
        i, j = stack.pop()
        best, idx = -1.0, -1
        for k in range(i + 1, j):
            d = dist(pts[k], pts[i], pts[j])
            if d > best:
                best, idx = d, k
        if idx != -1 and best > tol:
            keep[idx] = True
            stack.append((i, idx))
            stack.append((idx, j))
    return [p for p, f in zip(pts, keep) if f]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('control #0', [[[0, 0], [3, 1], [6, -1], [9, 1], [12, 1], [15, 4], [18, 1], [21, -2], [24, 1]], 2], [[0, 0], [6, -1], [15, 4], [21, -2], [24, 1]]), ('control #1', [[[0, 3], [3, -4], [6, 1], [9, 3], [12, -4], [15, 1], [18, -1]], 1], [[0, 3], [3, -4], [9, 3], [12, -4], [15, 1], [18, -1]]), ('control #2', [[[0, -4], [3, 3], [6, -2], [9, -1], [12, 2], [15, 1], [18, 1]], 0], [[0, -4], [3, 3], [6, -2], [9, -1], [12, 2], [15, 1], [18, 1]]), ('control #3', [[[0, -3], [3, -1], [6, -3], [9, -2]], 3], [[0, -3], [9, -2]]), ('control #4', [[[0, -2], [3, -4], [6, -1], [9, -4], [12, 1], [15, 2]], 3], [[0, -2], [9, -4], [15, 2]]), ('control #5', [[[0, -2], [3, 2], [6, 2], [9, -3], [12, 3], [15, 4], [18, 2], [21, -2]], 0], [[0, -2], [3, 2], [6, 2], [9, -3], [12, 3], [15, 4], [18, 2], [21, -2]]), ('regression #16', [[[0, 0], [4, 4], [8, 0], [4, -4], [0, 0]], 1], [[0, 0], [4, 4], [8, 0], [4, -4], [0, 0]]), ('boundary #27', [[[0, 0], [3, 3], [0, 0]], 5], [[0, 0], [0, 0]])], [('control #3', [[[0, -3], [3, -1], [6, -3], [9, -2]], 3], [[0, -3], [9, -2]]), ('control #4', [[[0, -2], [3, -4], [6, -1], [9, -4], [12, 1], [15, 2]], 3], [[0, -2], [9, -4], [15, 2]]), ('control #5', [[[0, -2], [3, 2], [6, 2], [9, -3], [12, 3], [15, 4], [18, 2], [21, -2]], 0], [[0, -2], [3, 2], [6, 2], [9, -3], [12, 3], [15, 4], [18, 2], [21, -2]]), ('control #6', [[[0, 4], [3, -1], [6, 2], [9, 2], [12, 2]], 3], [[0, 4], [3, -1], [12, 2]]), ('control #7', [[[0, -4], [3, 0], [6, -3], [9, 1], [12, 1], [15, 3]], 2], [[0, -4], [3, 0], [6, -3], [15, 3]]), ('control #8', [[[0, -4], [3, -4], [6, 1], [9, 3], [12, 3], [15, -4]], 1], [[0, -4], [3, -4], [9, 3], [12, 3], [15, -4]]), ('regression #17', [[[0, 0], [6, 1], [6, 7], [0, 6], [0, 0]], 2], [[0, 0], [6, 1], [6, 7], [0, 6], [0, 0]]), ('boundary #28', [[[0, 0], [4, 3], [1, 4], [0, 0]], 5], [[0, 0], [0, 0]])], [('control #6', [[[0, 4], [3, -1], [6, 2], [9, 2], [12, 2]], 3], [[0, 4], [3, -1], [12, 2]]), ('control #7', [[[0, -4], [3, 0], [6, -3], [9, 1], [12, 1], [15, 3]], 2], [[0, -4], [3, 0], [6, -3], [15, 3]]), ('control #8', [[[0, -4], [3, -4], [6, 1], [9, 3], [12, 3], [15, -4]], 1], [[0, -4], [3, -4], [9, 3], [12, 3], [15, -4]]), ('control #9', [[[0, -3], [3, 4], [6, 0], [9, -4], [12, 0], [15, -1], [18, 4]], 0], [[0, -3], [3, 4], [9, -4], [12, 0], [15, -1], [18, 4]]), ('control #10', [[[0, -4], [3, -2], [6, 1], [9, 1]], 2], [[0, -4], [9, 1]]), ('control #11', [[[0, 4], [3, -3], [6, -2], [9, -4], [12, 4], [15, 4], [18, -1]], 2], [[0, 4], [3, -3], [9, -4], [12, 4], [18, -1]]), ('regression #16', [[[0, 0], [4, 4], [8, 0], [4, -4], [0, 0]], 1], [[0, 0], [4, 4], [8, 0], [4, -4], [0, 0]]), ('boundary #27', [[[0, 0], [3, 3], [0, 0]], 5], [[0, 0], [0, 0]])], [('control #9', [[[0, -3], [3, 4], [6, 0], [9, -4], [12, 0], [15, -1], [18, 4]], 0], [[0, -3], [3, 4], [9, -4], [12, 0], [15, -1], [18, 4]]), ('control #10', [[[0, -4], [3, -2], [6, 1], [9, 1]], 2], [[0, -4], [9, 1]]), ('control #11', [[[0, 4], [3, -3], [6, -2], [9, -4], [12, 4], [15, 4], [18, -1]], 2], [[0, 4], [3, -3], [9, -4], [12, 4], [18, -1]]), ('control #12', [[[0, 2], [3, -3], [6, 3], [9, -1]], 1], [[0, 2], [3, -3], [6, 3], [9, -1]]), ('control #13', [[[0, 4], [3, -1], [6, -4], [9, -2], [12, 4], [15, -3], [18, -1], [21, 0]], 3], [[0, 4], [6, -4], [12, 4], [15, -3], [21, 0]]), ('regression #14', [[[0, 0], [10, 0], [14, 3], [20, 0]], 2], [[0, 0], [10, 0], [14, 3], [20, 0]]), ('regression #17', [[[0, 0], [6, 1], [6, 7], [0, 6], [0, 0]], 2], [[0, 0], [6, 1], [6, 7], [0, 6], [0, 0]]), ('boundary #28', [[[0, 0], [4, 3], [1, 4], [0, 0]], 5], [[0, 0], [0, 0]])], [('control #12', [[[0, 2], [3, -3], [6, 3], [9, -1]], 1], [[0, 2], [3, -3], [6, 3], [9, -1]]), ('control #13', [[[0, 4], [3, -1], [6, -4], [9, -2], [12, 4], [15, -3], [18, -1], [21, 0]], 3], [[0, 4], [6, -4], [12, 4], [15, -3], [21, 0]]), ('regression #14', [[[0, 0], [10, 0], [14, 3], [20, 0]], 2], [[0, 0], [10, 0], [14, 3], [20, 0]]), ('regression #15', [[[0, 0], [5, 0], [-6, 1], [10, 0]], 2], [[0, 0], [5, 0], [-6, 1], [10, 0]]), ('regression #16', [[[0, 0], [4, 4], [8, 0], [4, -4], [0, 0]], 1], [[0, 0], [4, 4], [8, 0], [4, -4], [0, 0]]), ('regression #17', [[[0, 0], [6, 1], [6, 7], [0, 6], [0, 0]], 2], [[0, 0], [6, 1], [6, 7], [0, 6], [0, 0]]), ('boundary #18', [[[0, 0], [5, 2], [10, 0]], 2], [[0, 0], [10, 0]]), ('boundary #27', [[[0, 0], [3, 3], [0, 0]], 5], [[0, 0], [0, 0]])]]
for label, args, expected in fixtures[N-1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
control #0[[0, 0], [6, -1], [15, 4], [21, -2], [24, 1]][[0, 0], [6, -1], [15, 4], [21, -2], [24, 1]]Passed
control #1[[0, 3], [3, -4], [9, 3], [12, -4], [15, 1], [18, -1]][[0, 3], [3, -4], [9, 3], [12, -4], [15, 1], [18, -1]]Passed
control #2[[0, -4], [3, 3], [6, -2], [9, -1], [12, 2], [15, 1], [18, 1]][[0, -4], [3, 3], [6, -2], [9, -1], [12, 2], [15, 1], [18, 1]]Passed
control #3[[0, -3], [9, -2]][[0, -3], [9, -2]]Passed
control #4[[0, -2], [9, -4], [15, 2]][[0, -2], [9, -4], [15, 2]]Passed
control #5[[0, -2], [3, 2], [6, 2], [9, -3], [12, 3], [15, 4], [18, 2], [21, -2]][[0, -2], [3, 2], [6, 2], [9, -3], [12, 3], [15, 4], [18, 2], [21, -2]]Passed
regression #16[[0, 0], [4, 4], [8, 0], [4, -4], [0, 0]][[0, 0], [4, 4], [8, 0], [4, -4], [0, 0]]Passed
boundary #27[[0, 0], [3, 3], [0, 0]][[0, 0], [0, 0]]Failed

SHA-256 / d84b8098e75f9f816f99e082767bfc55e8341a2c38f933d140c8f29bd39e94e8

HELD IN THE MEMBER ARCHIVE

The verified repair and its recorded checks are member-only.

This mechanism has 8 recorded checks per implementation. The open-access tier publishes the failure and the unsuccessful fix; the repaired source that passes every check, and the observations that prove it, are available to members.

Every case sharing this mechanism uses the same contract and the same repair, so this one record is held back for all of them.

Member access is invitation-based. Sign in with your invited account to inspect the repair.

Sign in to the archive ↗

Verification & scope

Stipulated deterministic toy contract on a bounded input domain; results are rounded as stated and no conformance with any published standard or library is claimed. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:48:22.187692+00:00.

Case digest / c327156618cad900059530bdb5a62a91e119e2c6bb8dba5bc14271ec4d46b8d9