I have a list of coordinates (in [x,y] format), and they define the perimeter of a shape. I can't quite work out an algorithm for drawing round the perimeter of this shape, without crossing the shape. Google has failed me, and my A-level in maths is all but a hazy memory now... Algorithm gods, your time is now!
I apologise in advance for the length of this question, but it's quite a specific problem, and it's causing multiple headaches for me... :(
I alredy run a sudoku website
, and am working on adding killer sudoku to it. I'm trying to write a hunk of Flash that will draw the cages
required in a Killer Sudoku
. The cages are the dotted lines that run around several cells in the puzzle. In normal sudoku, you have to have the numbers 1-9 once in each row, column and 3x3 block. In a killer sudoku, the numbers in the cages must add up to the number show in each cage (for example the top left cage with 16 can only be 9 and 7, or 7 and 9, as they're the only possible combinations that add up to 16).
In my code, I represent each of the cages as a list of cells, and their sum. The first few cages in that puzzle would be:
The cell numbering schema is that the top row are cells 0, 1, 2, 3, 4, 5, 6, 7, 8, and the next row are cells 9, 10, 11, 12, 13, etc. Using this notation, I build a complete list of cages, and their cells. Now, I ask the flash code to build each cage in turn.
The current method I'm using works like this:
1. Calculate all the coordinates of every corner of each cell in the cage.
(eg, the cage 16=0,9 will have corners at [0,0][0,1][1,0][1,1][2,1][2,2])
2. Remove any coordinates that are shared between four cells. If any point is shared by four cells then it is an internal point, not one on the perimeter of the shape.
(eg in an example cage 22=0,1,9,10 there is a point at [1,1] that is shared by cells 0, 1, 9 and 10. It has four cells touching it, therefore it is a point inside the shape, not on the perimeter, so we ignore it)
3. Now we have a list of points that are on the perimeter of the shape. Here I get stuck.
How do I now work out what order to join the points together in? One possible solution is to start at any given point and move to any other point that is a distance of '1' away, and we haven't visited before. This should work round the shape of the puzzle but what happens is that it cuts off corners of shapes.
For example, in the cage 16=0,9, starting at [0,0], the program may draw a line to [1,0], then [1,1], then [0,1], then [0,2]. Each of those points are '1' unit away from each other, so the algorithm sort of works, but not as intended.
I basically need to trace round the perimeter of the shape, without crossing the shape at any point. I'd prefer not to use a recursive function to exhaustively find the right solution, as that runs really slowly in flash.
The second problem is with indenting. If you look at the cages, they're just slightly inside the cells the cover, rather than running along the grid lines. If the code is going to draw the cages inside the cells, then it needs to have some concept of what 'inside' means for each cage. I think this is something to do with calculating the normal for each point on the perimiter, then adjusting the coordinates slightly at the point of drawing the line, but I haven't got to that part yet.
I've googled for suitable algorithms, but have not turned up anything of use. I hope that somebody has done this before and can share some insight. This is the third time I've tried to refactor this code, and it still doesn't quite work properly.