Four arcs and the false alarm is gone

The regions overlap and the parts never meet measured what a swept region costs as an interference test. Sweep each of two moving parts over the whole drive, and if the two regions do not overlap the parts never touch: that direction is sound. If they do overlap, the parts may still never touch, because a region is a projection of the motion onto the plane and has forgotten when each part was where. Chebyshev’s two long arms share 4.66 square units of ground, a third of the smaller region, and never come within 0.38 of each other.

That essay named the repair it had not measured. Cut the drive into a few arcs, sweep each part over each arc on its own, and intersect regions only for the same arc. The whole-drive test asks whether there is a $\theta_1$ and a $\theta_2$ with the parts sharing a point. A collision needs one θ. The arc-wise test asks for a $\theta_1$ and a $\theta_2$ in the same arc, which sits between the two. It is still sound, it costs a few regions per part instead of one, and it forgets less than the whole-drive test does. The open question was how many arcs it takes and what they cost.

On the two pairs that raised false alarms, four arcs and eight arcs respectively.

One sweep, cut into arcs #

The arc-wise test needs no more sweeping than the region test. Every configuration of the drive is still rasterised once for each part; the arcs only decide which grid each configuration is rasterised into. What grows with the number of arcs is the number of grids in memory and the number of intersections at the end, both small.

For each arc, the two parts’ grids are built on one shared box, so that their cells line up, and the cells both occupy are marked. The ground the test flags is the union of the marked cells over all the arcs. It is a union, not a sum, because a patch flagged by two arcs is still one patch. Adjacent arcs share their boundary configuration, so no configuration falls between two arcs.

Two instruments shape how much can be concluded from this. The grid has cells of about 0.025 of a unit on a six-unit sweep, and the room a machine sweeps calibrated its areas against a shape with a closed form. The sweep samples 360 configurations, and a sweep that missed nothing showed that sampling is where a clearance check can fail silently. Both limits apply to the arc-wise test exactly as to the region test, and the second is addressed below with a bound that needs neither.

How many arcs #

Chebyshev’s arms drive over 0.99 radians of the input. One arc, the whole drive, flags 4.657 square units. Two arcs flag 0.859, three flag 0.015, and four flag nothing, with the arc boundaries placed either of two ways. At four arcs each arc is a quarter of a radian of drive, and within any one of them the two arms never occupy a common cell.

Peaucellier’s long arm and rhombus bar drive over π radians and share more ground. One arc flags 9.97 square units, two flag 2.50, three 0.74, four 0.24 and six 0.03, and eight arcs clear it. With the arc boundaries placed at half an arc’s offset, four arcs already clear it. Where the boundaries fall matters when an arc is barely short enough, which is what one would expect of a partition drawn without regard to the motion.

Two things make these numbers trustworthy as more than a grid’s opinion. The first is nesting. An arc cut in two can only flag less ground than the arc it came from, because each half’s regions are subsets of the whole arc’s, and the measured areas never increase when the number of arcs is doubled or tripled. The second is the refusal. Chebyshev’s arms made 0.5 wide overlap each other by 0.535 at their closest, and that pair is flagged at one arc, eight, thirty-two and sixty-four. A test that cleared it would be unsound, and this one never does.

Where Peaucellier’s pair is flagged #

Peaucellier’s pair is the harder case, and the ground it still flags at four arcs shows why.

With the arc boundaries at the drive’s quarter points, four arcs still flag 0.24 square units of ground where the long arm and the rhombus bar pass the same place within a quarter of the drive of each other. Move the boundaries half an arc along and the four arcs clear the pair, because the two visits to that ground now fall on either side of a boundary. Eight arcs clear it wherever the boundaries are.

That dependence on where the cuts fall is the arc-wise test’s one real weakness. The whole-drive test has no boundaries to place, and the configuration test has a boundary at every configuration. An arc-wise test with a few arcs has a handful of boundaries, and the result can turn on where they are. Taking the worse of several placements, as the counts above do, gives a number that does not depend on the choice, at the cost of a few more arcs than the best placement would need.

Why so few arcs are enough #

The whole-drive test fails because the two arms visit the same ground at different parts of the drive. The left arm crosses the shared patch early in the stroke and the right arm late. Once the drive is cut so that no arc contains both visits, nothing is shared.

The number of arcs needed is therefore set by how far apart in drive angle the two parts’ visits are, not by how close the parts come. The arms’ closest approach, 0.38, is at the start of the drive, 0.712 radians, and has nothing to do with where the false alarm was. The false alarm came from the crossing arms’ two sweeps meeting in the middle of the drawing, as two bars that have to cross described. Cutting the drive into quarters separates the early visit from the late one.

That reading can be measured directly, and it is a third route to the same number. For every cell that both parts occupy at some point of the drive, take the least difference in drive angle between a configuration at which one part is there and one at which the other is. The least of those over all shared cells is how close in the drive two visits to common ground ever come. On Chebyshev’s arms it is 0.306 radians, across 5,510 shared cells. Arcs shorter than that cannot hold both visits to any cell, so they must clear, and the drive’s 0.99 radians divided by 0.306 is 3.2, which makes four arcs. On Peaucellier’s pair the least separation is 0.430 radians, and π divided by 0.430 is 7.3, which makes eight. Both are exactly the numbers the grid found by cutting. The separation is a single number read off one sweep, before any arc is cut, so it tells a designer how many arcs to use before the test is run rather than after.

That is also why the arc-wise test can succeed where a finer grid cannot. A finer grid sharpens the regions, but a region swept over the whole drive still contains both visits. Only cutting the drive separates them.

Three tests, written as quantifiers #

The earlier essay put the region test’s failure in one line: it asks whether there exist a $\theta_1$ and a $\theta_2$ with the parts sharing a point, and a collision needs a single θ. The arc-wise test adds a condition, that $\theta_1$ and $\theta_2$ lie in the same arc. Written out, the three tests are:

• the region test: some $\theta_1$ and some $\theta_2$ anywhere in the drive;
• the arc-wise test: some arc, and some $\theta_1$ and $\theta_2$ in it;
• the collision: some θ, with $\theta_1 = \theta_2 = \theta$.

Each implies the one above it, so a collision always raises the arc-wise flag, and an arc-wise flag always raises the region flag. As the arcs shrink, the middle line becomes the last one, because a shrinking arc forces $\theta_1$ and $\theta_2$ together. This is the sense in which the arc-wise test interpolates between the other two, and it is also why nesting holds: cutting an arc in two can only remove pairs $(\theta_1, \theta_2)$ from consideration, never add them.

What the quantifiers do not say is how fast the middle line approaches the last one. That is a property of the machine and not of the logic, and on these two pairs it is fast. The whole of the false alarm is gone before the arcs are a tenth of the drive.

A certificate that needs no grid #

The grid can still miss a sliver thinner than a cell, and the sampling can miss a collision between two configurations. A bound on the whole arc, not on sampled points, closes both gaps.

Within an arc of length Δ, a part cannot move further than its fastest point’s speed times Δ. So if part A is at $\theta_1$ and part B at $\theta_2$, both in the arc, B at $\theta_2$ is within $v_B\Delta$ of where B was at $\theta_1$. The two parts at $\theta_1$ and $\theta_2$ are therefore at least $g(\theta_1) - v_B\Delta$ apart. The same holds with the parts exchanged, so the slower of the two speeds is the one to use. An arc is certified clear when the least gap anywhere in it exceeds that speed times the arc’s length.

The certificate clears Chebyshev’s arms from twelve arcs and Peaucellier’s pair from twenty-four, three times what the grid needed in each case. It is sound for the reason just given, and it is conservative because it assumes the fastest point of one part spends the whole arc moving straight at the other part. No point does.

At four arcs the certificate fails in two arcs. In the first, the least gap is the arms’ closest approach, 0.380, and the budget is 0.772, about twice that, so the bound cannot rule out a meeting that the grid shows does not happen. In the last it fails narrowly, a least gap of 1.267 against a budget of 1.276. The two middle arcs have least gaps well above their budgets, 1.253 against 1.111 and 1.571 against 1.276, and are certified. A mixed strategy follows directly: certify the arcs the bound can certify, and use the grid, or a finer set of arcs, only where it cannot.

The certificate and the grid fail in opposite ways, which is why the two together are worth having. The grid is sharp: it clears Chebyshev’s arms at four arcs, as soon as they are in fact clear at that partition. But it looks at sampled configurations and cells of finite size, and a sliver of overlap thinner than a cell, or a meeting between two samples, can pass it. The certificate cannot be fooled that way, because it bounds every configuration in the arc and needs no cells. It is loose: it clears only at twelve arcs. A sweep that missed nothing built the same kind of bound for a single configuration sweep, the gap between samples less the fastest point’s travel, and found it refused a twelve-sample sweep that the samples had passed. The arc-wise certificate is that bound applied to one arc at a time, with the arc playing the part the sample spacing played there.

What the arcs cost #

The arc-wise test’s cost is worth stating, because the case for a region test over a configuration test was always about cost.

A configuration test for a machine with m moving parts computes the gap between every pair of parts at every sampled configuration: m(m − 1)/2 polygon distances per configuration. A region test sweeps each part once, m sweeps, and then intersects regions: m(m − 1)/2 intersections of grids, each a pass over the cells, done once for the whole drive. The sweeps are the expensive part, and the intersections are cheap bitwise operations. That is why a region test is attractive for an assembly of many parts, and why its false alarms were a real loss.

The arc-wise test keeps the m sweeps unchanged. Every configuration is still rasterised once per part, into its arc’s grid instead of the whole drive’s. The intersections multiply by the number of arcs, which at four or eight is a small factor on a cheap step. Memory multiplies by the number of arcs too, one grid per part per arc. For eight arcs on a two-hundred-cell grid that is eight times forty thousand bytes a part, trivial on any machine that can run the sweep at all.

What the arcs are for #

They make the region test usable between moving parts. The regions overlap and the parts never meet concluded that swept regions are exact against fixed obstacles and can only be trusted as a coarse screen between two moving parts. Four or eight arcs change that. The test between moving parts becomes as decisive as the fixed-obstacle test on these machines, for the same sweeping work and a few more grids.

They show where the next arc belongs. A flagged cell is flagged by a particular arc, so a test that still flags something says where in the drive the parts visit the same ground. The natural next step is to cut only that arc, not every arc, and the counts above suggest it would converge in a few steps. A pin is not a point and free space comes in pieces both found that the interesting structure in a machine’s clearance is local in the drive, and the arcs are a way of spending effort where it is.

They do not replace the configuration test. A sampled configuration test with a Lipschitz bound, as in a sweep that missed nothing, is the arc-wise test at one configuration per arc, and it answers the collision question exactly. The arcs’ advantage is that a region can be compared with other regions, fixed obstacles and whole assemblies, at the cost of a union and an intersection, and that a clear result at four arcs is a clear result for everything the regions cover.

What this does not settle #

Machines with more freedom. Every machine here has one driven input, so the drive is an interval and arcs are intervals. A machine with two inputs has a configuration surface, and the arcs become patches of it. Whether a few patches still suffice is not measured.

Pairs that come close without crossing paths. Both pairs here raise a false alarm because their paths cross at different times. A pair that runs close alongside itself for a long stretch, a part and its neighbour in a parallel linkage, for example, visits nearby ground at nearby times, and no partition of the drive separates the visits. There the arc-wise test and the configuration test converge only as the arcs shrink towards single configurations.

Still open: arcs cut where the flags are #

The partitions above cut every arc equally, which spends sweeping and intersecting on arcs that were already clear. The flagged cells belong to particular arcs, and only those arcs need cutting.

The distinct argument there would be an adaptive partition: start from one arc, cut only the arcs that still flag something, and stop when nothing is flagged or an arc reaches the length at which the certificate clears it. The measurement would be the number of arcs the adaptive rule reaches on each pair against the uniform partition’s four and eight, and the total sweeping work. If the adaptive rule needs as few as three arcs on Chebyshev’s arms, with boundaries where the two visits separate, then the right partition is a property of the pair and can be read off the first flag, not searched for.