FA-70804 / GIS polygon topology / Member archive

Iterative removal of backtracking spikes: repeat until stable · case 04

Nested spikes are only partly removed.

Member previewVariant 4 · 3 implementations · 8 checks per implementation

Case contract

Input: a closed ring of integer vertices. Working on the open vertex cycle, repeatedly delete a vertex whose cyclic predecessor equals its cyclic successor (an exact out-and-back spike) or which equals its predecessor, until no such vertex remains or fewer than 3 vertices are left. Collinear pass-through vertices and partial backtracks are kept. Return None if fewer than 3 vertices remain, else the cycle closed with its first vertex.

Why this case matters

Digitising and snapping leave out-and-back spikes; cleaning must remove nested spikes, including those at the ring start, without changing genuine shape.

One recorded failure

Sample boundary fixture

This sample comes from the broken implementation of a controlled reproducer.

Boundary fixture	Actual	Expected	Outcome
regression #2	`[[0, 0], [10, 0], [10, 10], [12, 12], [12, 12], [10, 10], [0, 10], [0, 0]]`	`[[0, 0], [10, 0], [10, 10], [0, 10], [0, 0]]`	Failed

MEMBER ARCHIVE

The complete case is available to members.

This record includes three runnable implementations, regression fixtures, execution results, and source hashes.

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