How can I create an internal spiral for a polygon?

Question

For any shape how can I create a spiral inside it of a similar shape. This would be a similar idea to bounding (using Minkowski sum). Rather than creating the same shape inside the shape though it would be a spiral of same shape.

I found this - http://www.cis.upenn.edu/~cis110/13su/lectures/Spiral.java

It creates a spiral based on the parameters passed so it can be for any regular shape.

I want the above for all shapes i.e. irregular polygons too.

I am not hugely familiar with geometric terminology but I have looked up Involutes and an Internal Spiral Search Algorithm too but haven't been useful to me.

Does anyone have any idea where I'd find an algorithm such as this or at least ideas of how I'd come up with one?

Answer 1

I worked on something like this using offsets from the polgyon based on medial axis of Voronoi diagram. It's not simple. I can't share the code as it belongs to the company I worked for and it may not exactly fit your needs.

But here are some similar things I found by other people:

http://www.me.berkeley.edu/~mcmains/pubs/DAC05OffsetPolygon.pdf

http://www.cosy.sbg.ac.at/~held/teaching/seminar/seminar_2010-11/hsm.pdf

Answer 2

this task is extremly hard to do.

1. need to have the boundary polygon you want to fill with spiral

   I think you have it already

2. create new smaller polygon by shifting all lines inwards by the step.

   It is similar to create stroke line around polygon. Step is the screw width so at start of polygon it is 0 and on the end it is d

3. remove invalid lines from the newly generated screw

   Some lines on corners and curvatures will intersect. This is very hard to detect/repair reliably see

   • this for basics

4. repeat (do next screw) ... until no space for screw found

   But now after the first screw the step is always d this will not necessarily fill the whole shape. For example if you have some thinner spot on shape it will be filled much more faster then the rest so there can still be some holes left.

   You should detect them and handle as you see fit see

   • Finding holes in 2d point sets

   Be aware detection if the area is filled is also not trivial

This is how this approach looks like:

[Notes]

If you forget about the spiral and want fill the interior with a zig zag or similar pattern then this is not that hard.

Spiral filling makes a lot of hard geometric problems and if you are not skilled in geometry and vector math this task could be a too big challenge for beginner or even medium skilled programmer in this field to make it work properly. That is at least my opinion (as I done this before) so handle it as such.