FAILURE MAP
← Case archive

FA-70526 / GIS polygon topology / Open access

Simple ring validity diagnosis: spike direction test · case 01

Rings with a redundant collinear vertex are rejected as spiky.

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

ROOT CAUSE

Any collinear vertex is treated as a spike without checking that the boundary reverses.

THE FAILURE

Any collinear vertex is treated as a spike without checking that the boundary reverses.

Unsuccessful approach: The dot-product test is inverted, flagging straight pass-through vertices and missing real reversals.

Case contract

Input: one ring as a list of integer [x, y]. Report the first failing check in this order: fewer than 4 positions "too_few_points"; first != last "not_closed"; two cyclically consecutive equal vertices "repeated_point"; a vertex where the boundary reverses direction along a line (collinear with a negative dot product of the incoming and outgoing edge, checked cyclically) "spike"; any two non-adjacent edges sharing a point (crossing, touching or collinear overlap) "self_intersection"; otherwise "valid".

Why this case matters

Topology validators run before editing, overlay and publishing; a wrong diagnosis sends users to fix the wrong vertex or lets broken rings through.

1 / The failure

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    ring = x
    if len(ring) < 4:
        return 'too_few_points'
    if ring[0] != ring[-1]:
        return 'not_closed'
    pts = ring[:-1]
    n = len(pts)
    for i in range(n):
        if pts[i] == pts[(i + 1) % n]:
            return 'repeated_point'
    for i in range(n):
        a, b, c = pts[i - 1], pts[i], pts[(i + 1) % n]
        cross = (b[0] - a[0]) * (c[1] - b[1]) - (b[1] - a[1]) * (c[0] - b[0])
        dot = (b[0] - a[0]) * (c[0] - b[0]) + (b[1] - a[1]) * (c[1] - b[1])
        if cross == 0:
            return 'spike'
    def orient(p, q, r):
        v = (q[0] - p[0]) * (r[1] - p[1]) - (q[1] - p[1]) * (r[0] - p[0])
        return (v > 0) - (v < 0)
    def within(p, q, r):
        return min(p[0], r[0]) <= q[0] <= max(p[0], r[0]) and min(p[1], r[1]) <= q[1] <= max(p[1], r[1])
    def hit(p1, p2, p3, p4):
        o1, o2, o3, o4 = orient(p1, p2, p3), orient(p1, p2, p4), orient(p3, p4, p1), orient(p3, p4, p2)
        if o1 * o2 < 0 and o3 * o4 < 0:
            return True
        return (o1 == 0 and within(p1, p3, p2)) or (o2 == 0 and within(p1, p4, p2)) or (o3 == 0 and within(p3, p1, p4)) or (o4 == 0 and within(p3, p2, p4))
    for i in range(n):
        for j in range(i + 1, n):
            if j == i + 1 or (i == 0 and j == n - 1):
                continue
            if hit(pts[i], pts[(i + 1) % n], pts[j], pts[(j + 1) % n]):
                return 'self_intersection'
    return 'valid'
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('control #0', [[0, 0], [10, 0], [10, 10], [0, 10], [0, 0]], 'valid'), ('control #1', [[0, 0], [10, 0], [5, 8], [0, 0]], 'valid'), ('control #2', [[0, 0], [5, 0], [10, 0], [10, 10], [0, 10], [0, 0]], 'valid'), ('regression #3', [[0, 0], [10, 10], [10, 0], [0, 10], [0, 0]], 'self_intersection'), ('regression #4', [[0, 0], [10, 0], [10, 10], [10, 5], [0, 5], [0, 0]], 'spike'), ('regression #5', [[5, 0], [10, 0], [10, 10], [0, 10], [0, 0], [5, 0], [0, 0]], 'not_closed'), ('boundary #6', [[0, 0], [10, 0], [10, 10], [0, 0]], 'valid'), ('boundary #7', [[0, 0], [10, 0], [10, 10]], 'too_few_points')], [('control #2', [[0, 0], [5, 0], [10, 0], [10, 10], [0, 10], [0, 0]], 'valid'), ('regression #4', [[0, 0], [10, 0], [10, 10], [10, 5], [0, 5], [0, 0]], 'spike'), ('regression #5', [[5, 0], [10, 0], [10, 10], [0, 10], [0, 0], [5, 0], [0, 0]], 'not_closed'), ('boundary #6', [[0, 0], [10, 0], [10, 10], [0, 0]], 'valid'), ('boundary #7', [[0, 0], [10, 0], [10, 10]], 'too_few_points'), ('boundary #8', [[0, 0], [10, 0], [10, 10], [0, 10], [0, 1]], 'not_closed'), ('boundary #9', [[0, 0], [10, 0], [10, 0], [10, 10], [0, 0]], 'repeated_point'), ('regression #11', [[0, 0], [10, 0], [10, 10], [0, 10], [0, 5], [0, 12], [0, 0]], 'spike')], [('control #2', [[0, 0], [5, 0], [10, 0], [10, 10], [0, 10], [0, 0]], 'valid'), ('boundary #7', [[0, 0], [10, 0], [10, 10]], 'too_few_points'), ('boundary #8', [[0, 0], [10, 0], [10, 10], [0, 10], [0, 1]], 'not_closed'), ('boundary #9', [[0, 0], [10, 0], [10, 0], [10, 10], [0, 0]], 'repeated_point'), ('regression #10', [[0, 0], [10, 0], [10, 10], [0, 10], [0, 0], [0, 0]], 'repeated_point'), ('regression #11', [[0, 0], [10, 0], [10, 10], [0, 10], [0, 5], [0, 12], [0, 0]], 'spike'), ('regression #12', [[0, 5], [0, 0], [10, 0], [10, 10], [0, 10], [0, 12], [0, 5]], 'spike'), ('regression #15', [[0, 0], [10, 0], [10, 5], [2, 5], [6, 5], [6, 8], [0, 8], [0, 0]], 'spike')], [('control #2', [[0, 0], [5, 0], [10, 0], [10, 10], [0, 10], [0, 0]], 'valid'), ('regression #10', [[0, 0], [10, 0], [10, 10], [0, 10], [0, 0], [0, 0]], 'repeated_point'), ('regression #11', [[0, 0], [10, 0], [10, 10], [0, 10], [0, 5], [0, 12], [0, 0]], 'spike'), ('regression #12', [[0, 5], [0, 0], [10, 0], [10, 10], [0, 10], [0, 12], [0, 5]], 'spike'), ('regression #13', [[0, 0], [4, 0], [4, 4], [8, 4], [8, 8], [4, 8], [4, 4], [0, 4], [0, 0]], 'self_intersection'), ('regression #14', [[0, 0], [10, 0], [10, 10], [5, 0], [0, 10], [0, 0]], 'self_intersection'), ('regression #15', [[0, 0], [10, 0], [10, 5], [2, 5], [6, 5], [6, 8], [0, 8], [0, 0]], 'spike'), ('regression #17', [[0, 0], [10, 0], [10, 10], [0, 10], [4, 10], [0, 0]], 'spike')], [('control #2', [[0, 0], [5, 0], [10, 0], [10, 10], [0, 10], [0, 0]], 'valid'), ('regression #13', [[0, 0], [4, 0], [4, 4], [8, 4], [8, 8], [4, 8], [4, 4], [0, 4], [0, 0]], 'self_intersection'), ('regression #14', [[0, 0], [10, 0], [10, 10], [5, 0], [0, 10], [0, 0]], 'self_intersection'), ('regression #15', [[0, 0], [10, 0], [10, 5], [2, 5], [6, 5], [6, 8], [0, 8], [0, 0]], 'spike'), ('control #16', [[0, 0], [6, 0], [6, 6], [3, 3], [0, 6], [0, 0]], 'valid'), ('regression #17', [[0, 0], [10, 0], [10, 10], [0, 10], [4, 10], [0, 0]], 'spike'), ('control #18', [[1, 1], [9, 2], [8, 9], [2, 7], [1, 1]], 'valid'), ('regression #26', [[0, 0], [6, 0], [6, 6], [0, 6], [3, 6], [3, 9], [0, 9], [0, 0]], 'spike')]]
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 #0validvalidPassed
control #1validvalidPassed
control #2spikevalidFailed
regression #3self_intersectionself_intersectionPassed
regression #4spikespikePassed
regression #5not_closednot_closedPassed
boundary #6validvalidPassed
boundary #7too_few_pointstoo_few_pointsPassed

SHA-256 / 709c716880fce92440ef4e7189a46bd904b42621eb99d76232d8bf9b36b2803b

2 / The unsuccessful fix

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    ring = x
    if len(ring) < 4:
        return 'too_few_points'
    if ring[0] != ring[-1]:
        return 'not_closed'
    pts = ring[:-1]
    n = len(pts)
    for i in range(n):
        if pts[i] == pts[(i + 1) % n]:
            return 'repeated_point'
    for i in range(n):
        a, b, c = pts[i - 1], pts[i], pts[(i + 1) % n]
        cross = (b[0] - a[0]) * (c[1] - b[1]) - (b[1] - a[1]) * (c[0] - b[0])
        dot = (b[0] - a[0]) * (c[0] - b[0]) + (b[1] - a[1]) * (c[1] - b[1])
        if cross == 0 and dot > 0:
            return 'spike'
    def orient(p, q, r):
        v = (q[0] - p[0]) * (r[1] - p[1]) - (q[1] - p[1]) * (r[0] - p[0])
        return (v > 0) - (v < 0)
    def within(p, q, r):
        return min(p[0], r[0]) <= q[0] <= max(p[0], r[0]) and min(p[1], r[1]) <= q[1] <= max(p[1], r[1])
    def hit(p1, p2, p3, p4):
        o1, o2, o3, o4 = orient(p1, p2, p3), orient(p1, p2, p4), orient(p3, p4, p1), orient(p3, p4, p2)
        if o1 * o2 < 0 and o3 * o4 < 0:
            return True
        return (o1 == 0 and within(p1, p3, p2)) or (o2 == 0 and within(p1, p4, p2)) or (o3 == 0 and within(p3, p1, p4)) or (o4 == 0 and within(p3, p2, p4))
    for i in range(n):
        for j in range(i + 1, n):
            if j == i + 1 or (i == 0 and j == n - 1):
                continue
            if hit(pts[i], pts[(i + 1) % n], pts[j], pts[(j + 1) % n]):
                return 'self_intersection'
    return 'valid'
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('control #0', [[0, 0], [10, 0], [10, 10], [0, 10], [0, 0]], 'valid'), ('control #1', [[0, 0], [10, 0], [5, 8], [0, 0]], 'valid'), ('control #2', [[0, 0], [5, 0], [10, 0], [10, 10], [0, 10], [0, 0]], 'valid'), ('regression #3', [[0, 0], [10, 10], [10, 0], [0, 10], [0, 0]], 'self_intersection'), ('regression #4', [[0, 0], [10, 0], [10, 10], [10, 5], [0, 5], [0, 0]], 'spike'), ('regression #5', [[5, 0], [10, 0], [10, 10], [0, 10], [0, 0], [5, 0], [0, 0]], 'not_closed'), ('boundary #6', [[0, 0], [10, 0], [10, 10], [0, 0]], 'valid'), ('boundary #7', [[0, 0], [10, 0], [10, 10]], 'too_few_points')], [('control #2', [[0, 0], [5, 0], [10, 0], [10, 10], [0, 10], [0, 0]], 'valid'), ('regression #4', [[0, 0], [10, 0], [10, 10], [10, 5], [0, 5], [0, 0]], 'spike'), ('regression #5', [[5, 0], [10, 0], [10, 10], [0, 10], [0, 0], [5, 0], [0, 0]], 'not_closed'), ('boundary #6', [[0, 0], [10, 0], [10, 10], [0, 0]], 'valid'), ('boundary #7', [[0, 0], [10, 0], [10, 10]], 'too_few_points'), ('boundary #8', [[0, 0], [10, 0], [10, 10], [0, 10], [0, 1]], 'not_closed'), ('boundary #9', [[0, 0], [10, 0], [10, 0], [10, 10], [0, 0]], 'repeated_point'), ('regression #11', [[0, 0], [10, 0], [10, 10], [0, 10], [0, 5], [0, 12], [0, 0]], 'spike')], [('control #2', [[0, 0], [5, 0], [10, 0], [10, 10], [0, 10], [0, 0]], 'valid'), ('boundary #7', [[0, 0], [10, 0], [10, 10]], 'too_few_points'), ('boundary #8', [[0, 0], [10, 0], [10, 10], [0, 10], [0, 1]], 'not_closed'), ('boundary #9', [[0, 0], [10, 0], [10, 0], [10, 10], [0, 0]], 'repeated_point'), ('regression #10', [[0, 0], [10, 0], [10, 10], [0, 10], [0, 0], [0, 0]], 'repeated_point'), ('regression #11', [[0, 0], [10, 0], [10, 10], [0, 10], [0, 5], [0, 12], [0, 0]], 'spike'), ('regression #12', [[0, 5], [0, 0], [10, 0], [10, 10], [0, 10], [0, 12], [0, 5]], 'spike'), ('regression #15', [[0, 0], [10, 0], [10, 5], [2, 5], [6, 5], [6, 8], [0, 8], [0, 0]], 'spike')], [('control #2', [[0, 0], [5, 0], [10, 0], [10, 10], [0, 10], [0, 0]], 'valid'), ('regression #10', [[0, 0], [10, 0], [10, 10], [0, 10], [0, 0], [0, 0]], 'repeated_point'), ('regression #11', [[0, 0], [10, 0], [10, 10], [0, 10], [0, 5], [0, 12], [0, 0]], 'spike'), ('regression #12', [[0, 5], [0, 0], [10, 0], [10, 10], [0, 10], [0, 12], [0, 5]], 'spike'), ('regression #13', [[0, 0], [4, 0], [4, 4], [8, 4], [8, 8], [4, 8], [4, 4], [0, 4], [0, 0]], 'self_intersection'), ('regression #14', [[0, 0], [10, 0], [10, 10], [5, 0], [0, 10], [0, 0]], 'self_intersection'), ('regression #15', [[0, 0], [10, 0], [10, 5], [2, 5], [6, 5], [6, 8], [0, 8], [0, 0]], 'spike'), ('regression #17', [[0, 0], [10, 0], [10, 10], [0, 10], [4, 10], [0, 0]], 'spike')], [('control #2', [[0, 0], [5, 0], [10, 0], [10, 10], [0, 10], [0, 0]], 'valid'), ('regression #13', [[0, 0], [4, 0], [4, 4], [8, 4], [8, 8], [4, 8], [4, 4], [0, 4], [0, 0]], 'self_intersection'), ('regression #14', [[0, 0], [10, 0], [10, 10], [5, 0], [0, 10], [0, 0]], 'self_intersection'), ('regression #15', [[0, 0], [10, 0], [10, 5], [2, 5], [6, 5], [6, 8], [0, 8], [0, 0]], 'spike'), ('control #16', [[0, 0], [6, 0], [6, 6], [3, 3], [0, 6], [0, 0]], 'valid'), ('regression #17', [[0, 0], [10, 0], [10, 10], [0, 10], [4, 10], [0, 0]], 'spike'), ('control #18', [[1, 1], [9, 2], [8, 9], [2, 7], [1, 1]], 'valid'), ('regression #26', [[0, 0], [6, 0], [6, 6], [0, 6], [3, 6], [3, 9], [0, 9], [0, 0]], 'spike')]]
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 #0validvalidPassed
control #1validvalidPassed
control #2spikevalidFailed
regression #3self_intersectionself_intersectionPassed
regression #4self_intersectionspikeFailed
regression #5not_closednot_closedPassed
boundary #6validvalidPassed
boundary #7too_few_pointstoo_few_pointsPassed

SHA-256 / b1e86702acfbe3311a8d4d5e23a19796d7adaf72f5b1950e52d28408f7d4e9b3

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:21.605388+00:00.

Case digest / b8b7673df0e8eeb54065013372ac679a1f6e052c43ddba1908f4612dd0691a52