## The scallop eight-way cell

Thursday, January 15th, 2009 at 7:24 pm

I am trying to knuckle down for some machining work for a change, faced with yet more scallop algorithm problems obstructing getting on with anything more productive. It appears that my independent income (if I eventually get any) is likely to be the only source of funding for projects like publicwhip and undemocracy.com since all the supposed public interest funding bodies appear not to give a damn.

Here’s a set of offset contours that are linking up incorrectly. You can see it in that sliver of a rectangle turned to an isometric view instantly. It’s impossible to subdivide the cell in the XY plane to reduce the complexity (the number of entries into the cell) below eight because they are all on a vertical wall. This comes with offsetting a set of contours that bounded the horizontal areas outwards by several milimetres so that they were all on the wall, and then attempting to offset them back inwards (as done in the mother of all scallop bugs).

You have to offset them both ways and then discard the pieces that are on the side you don’t want, because the condition of which side the contour is is often very difficult to determine locally — something I finally concluded for sure at the end of 2007. If I examined the code for anyone else’s constant scallop algorithm, I would look for this characteristic. You can tell the sidedness of the offset in almost all cases, but the final cases where it fails are entirely unsolvable; the information is not available locally.

So that’s the explanation for why the contours need to be so complex — they are doubled up at this stage, before the ones on the wrong side are discarded.

Here are two ways to connect up eight incoming paths in a single cell with four contours. The example on the left could be coded as [(0,7), (1,6), (2,3), (4,5)] and the one on the right could is [(0,7), (1,6), (2,5), (3,4)].

In the example above I am getting the pieces connecting like the right hand cell (which is why there is that annoying disconnection in the upper branch of the main picture), when I really want the left hand version.

How many ways can you connect these eight edges?

Well, four edges can be connected in two different ways.

[(0,1), (2, 3)]
[(0,2), (1, 3)]

Six edges have five ways:

[(0,1), (2, 3), (4,5)], [(0,1), (2,5),(3,4)]
[(0,3),(1,2),(4,5)]
[(0,5),(1,2),(3,4)], [(0,5),(1,4),(2,3)]

The grouping should give an idea of how I’m counting them. When you get to eight ways you can either start with (0,1) or (0,7), leaving a six-way, or you can start with (0,3) or (0,5) which divides the area into a four-way and a two-way, which gives a total of 14 ways.

I’m sure someone has worked out the general formula that counts the number of ways for each 2*n, so I’ll resist spending the rest of the day proving it.

But here’s the issue. When I created the algorithm I expected only to deal with four-way cells, because I thought I could always subdivide the cell enough to get rid of anything more complicated.

Then along came the six-way cells, which is only one step up. I changed the record of the cell connection to work with a three bit integer that could encode the five options.

For higher order cells (eight, ten and twelve — offsetting three contours on the same wall) I encoded only some of the options, the ones I called “striped”. The connecting diagram on the right is striped because you start with (0,7) enclosing nothing, and crawl outwards along both sides until you get to (3,4). Or you could start with (0,1), or (1,2), or (2,3) — four options.

The one on the left, which is correct for this case, is not striped, so I can’t encode it. What am I going to do about this?

If I decide it’s important, I’m probably going to have to create an exceptional connecting case. In the eight-way cell where the data structure can only encode for the 4 striped connections (out of the possible 14), I’ll add in a fifth one which says to the function: “Go look up this cell’s coordinates in another data structure where the connection is recorded in its full list of pairs, rather than encoded into a three bit number.”

I don’t expect there to be more than two such exceptional cells in the whole subdivided surface, so the speed implications are negligable. However, carrying around some special decoding thing in place of a simple integer code requires a heck of a lot of messing around with function calls that were previously simple and self-contained (operating only on the cell itself). I don’t have a way of referencing the cells of one of the structures while it is being subdivided — the indexing is applied to them later when it becomes read-only. So my look-up table is going to have to use the actual floating point XY coordinates of the corner of the cell as the reference index. This is normally not done, because floating point values are considered approximate. But if the number doesn’t change (it’s stored in absolute form in a list), it’s like a bit-patterned reference, which isn’t going to shift if cells further to the left of it get subdivided and its integer value cell-number increases. This is critical, because the cell subdividing of the surface is done with multiprocessors running in parallel. The only limitation is that cells subject to this simultaneous subdividing operation can’t share the same row or column, because it’s not safe for two concurrent threads to change the size of the same array at the same time.

Update: I couldn’t stop myself looking at the n-connection problem. I’ve reduced it to a recursion relation in the following way:

Define c(n) as the number of ways to connect all the corners of a fixed n-sided polygon with curves inside the shape that don’t cross each other.

Set c(0) = 1, c(1) = 0, c(2) = 1

Then

c(n) = SUM{ c(i – 1) c(n – 1 – i) | i = 1, 2, …, n – 1 }

Results are: c(4) = 2, c(6) = 5, c(8) = 14, c(10) = 42, and c(2i + 1) = 0

Some extra notes. If you’re allowed to rotate the polygon, then the numbers are smaller because the two cases in c(4) are the same, but rotated by a quarter, and the c(6) case would only give 3 unique shapes. It’s a different question, and I don’t know the recursion formula.

It’s easy to see that odd values are zero, since you can’t connect the lines up without leaving one spare. The zero value is one — one valid solution. These are always like the initial conditions of any recursion, and there’s no justification for deciding how they should be, other than to make the equations easier. You can try and make a recursion equation for c(2n) but it gets really complicated because you have to take account of whether n itself is odd or even.

If you look at the problem hard enough, it starts to look like it’s counting binary trees, where the first connection cuts the area in two, and the next connection cuts those two areas in two (when possible), and so on. If I could prove this problem was equivalent in some way to counting partitions, then it would be answered. It probably isn’t, but it gives a flavour of its potential for very hardness that this could be.

Someone on the maths.newsgroup can deal with this, and come back with which Paul Erdos theorem answers it. I’ll erase it from my mind by thinking instead about the tensioned thread algorithm.

Also, there’s the one-line Python program that gives you all the numbers you need:

c = [1, 0]
while len(c) < 5000: c.append(sum([ c[i - 1] * c[len(c) - i - 1] for i in range(1, len(c)) ])) print len(c) - 1, c[-1] # prints values as they are created

Cripes! New scary feature in Python: thousands of digits in a single long integer, as if by magic.

• 1. lezdep replies at 16th January 2009, 5:11 am :

Not related to latest post, but I thought you would like to know – I’ve done first machining
using toolpath generated by Adaptive Clearing algorithm. It has done a good job, imho.

Pictures are on following page – http://lezdep.dyndns.org:8080/f1/CNC/R25/public/

• 2. Freesteel&hellip replies at 14th April 2009, 12:45 pm :

[…] to do now? There are a lot of advanced scallop bugs/deficiencies which would take reams of new code to solve properly. It’s difficult to justify doing this […]

• 3. Freesteel&hellip replies at 23rd November 2009, 12:21 am :

[…] constant stepover algorithm, which has received a considerable amount of work and can handle 8-way cells (and more recently the 12-way cell), the area detection function is not so well […]