[Slither] Pinch Shift Algorithm

Kip Warner kip at thevertigo.com
Wed Jun 30 15:20:55 PDT 2010

On Tue, 2010-06-29 at 11:09 +0100, Matthew Ault wrote: 
> Thanks for the info.

Hey Matt. Sorry for taking a while to respond. It's been a few years
since I designed the algorithm and I had to dig through old notes to
find the information you need.

> Could you try and explain:
> 1. The algorithm that you use (pinch shift).

It's difficult to explain without a white board or showing you a sketch,
but I will try my best as memory permits.

No matter the kind of analysis you are doing in any context, you
probably always need to know where the worms are, and at least its head
position too. Given a sequence of contiguous vertices (x,y) representing
a worm contour, PinchShiftForAnEnd() returns the nth index which is
either the head or the tail. Using some heuristics after, it makes a
reasonably reliable guess which is which (I think the head is always a
little lighter?).

If you can find either the head or tail index, you know where the other
end is because it will be about half the length of the entire worm's
perimeter away. Sketch it on paper and this will help you.

So the process must find such a "terminal" index for the head or tail.

(1) Pick an arbitrary vertex anywhere along the contour.

(2) Based on line segment formed by above and either neighbour, we can
calculate a perpendicular line pointing either inwards or out of the
worm's body.

(3) We want that "pin" to poke into the worm's body. So we alternate the
length back and forth in either direction until we find the side where
it is going through the body instead of outwards.

(4) Extend that line segment out to infinity so that it is a ray, or in
other words, for practical purposes, to image boundary.

(5) We want to find the line segment on the worm's contour that the ray
pops out on the other side of the worm. Since the ray we made may come
out and go back in and out of the worm multiple times (e.g. it's in an S
shape), we only are interested in the one that is the closest to where
we started. That will be the one we're looking for.

(6) We've finished the "pinch" part now giving us a line through the
worm's body starting on one side and coming out as close as possible on
the other side of its body.

(7) Now we "shift". The two vertices we came up with in the above steps
by incrementing one and decrementing the other so VertexA++ and
VertexB--. Like you are sliding your pinched fingers along its body.

(8) Repeat last step until VertexA == VertexB. At that point, you know
you've found a terminal end of the worm (either head or tale).

Try this on paper and it will hopefully make sense.

> 2. The key source files its located in.

I think the algorithm is declared in Worm.h as PinchShiftForAnEnd(), and
defined in corresponding Worm.cpp. To see how the whole process of worm
identification takes place, see Worm::Refresh() in the latter.

> 3. Roughly how fast it runs.

It should always run in θ(n) time, where n is number of vertices in the
worm contour. This is attactive because it scales well. I believe it
also requires θ(1) for space.

> 4. Can it be done in realtime?

There is no reason why I cannot see that being done.

> 5. If so at roughly what framerate?

As fast as your CPU can handle it. The algorithm, as mentioned above, is
very fast and thus can be used for offline analysis, as is done now, or
in realtime if you wanted to patch Slither to do so.

> Cheers,
> Matt
> _______________________________________________
> Slither mailing list
> Slither at lists.thevertigo.com
> http://lists.thevertigo.com/listinfo.cgi/slither-thevertigo.com

Kip Warner -- Software Engineer
OpenPGP encrypted/signed mail preferred
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: This is a digitally signed message part
URL: <http://lists.thevertigo.com/pipermail/slither-thevertigo.com/attachments/20100630/44d01bef/attachment.pgp>

More information about the Slither mailing list