Flash perimeter algorithm
December 22, 2005 2:25 PM Subscribe
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:
16=0,9
9=1,10
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.
Hyalp!
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:
16=0,9
9=1,10
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.
Hyalp!
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])
I think this example is for cage 16=0,1.
More importantly, it looks like you got the list of six corners by generating a list of the eight corners of the two cells (four corners per cell), and then discarding two of the four corners (coordinates) as duplicates. But it is precisely those two corners that are interior. (In other words, if you start with a complete set, then discard ALL corners which appear twice or more in your list, you'll end up with only four corners, and you're done, yes?)
posted by WestCoaster at 2:56 PM on December 22, 2005
I think this example is for cage 16=0,1.
More importantly, it looks like you got the list of six corners by generating a list of the eight corners of the two cells (four corners per cell), and then discarding two of the four corners (coordinates) as duplicates. But it is precisely those two corners that are interior. (In other words, if you start with a complete set, then discard ALL corners which appear twice or more in your list, you'll end up with only four corners, and you're done, yes?)
posted by WestCoaster at 2:56 PM on December 22, 2005
Best answer: Finding a convex hull is overkill here. You're asking how to compute the topology of the cages, but if all you want is to display them, that's not necessary.
Given a pair of adjacent squares sharing an edge, it seems like you draw two dotted lines on either side of the edge if they're in a different cage and no dotted lines if they're in the same cage.
Say you're looking at square 1. If square 10 is in a different cage, then you know you have to draw a line at the bottom of square 1. When you get to square 10, you'll see that square 1 is in a different cage, so you have to draw a line at the top of square 10.
So, can you just go through each square, see if its 8 neighbors are in same/different cages and choose which dotted lines you have to draw for that square? Store these lines and calculate them for each square, then send them all to the display when you're done.
For squares on the boundaries, they always have dotted lines on the perimeter of the puzzle, so you can handle them as special cases.
posted by driveler at 2:56 PM on December 22, 2005
Given a pair of adjacent squares sharing an edge, it seems like you draw two dotted lines on either side of the edge if they're in a different cage and no dotted lines if they're in the same cage.
Say you're looking at square 1. If square 10 is in a different cage, then you know you have to draw a line at the bottom of square 1. When you get to square 10, you'll see that square 1 is in a different cage, so you have to draw a line at the top of square 10.
So, can you just go through each square, see if its 8 neighbors are in same/different cages and choose which dotted lines you have to draw for that square? Store these lines and calculate them for each square, then send them all to the display when you're done.
For squares on the boundaries, they always have dotted lines on the perimeter of the puzzle, so you can handle them as special cases.
posted by driveler at 2:56 PM on December 22, 2005
Best answer: Draw on the boundaries using XOR.
Or, don't collect the coordinates. Write a routine that takes a cell as an argument and which sides to draw in a cage. Get the list of cells, for each cell figure out if there is a neighboring cage cell also to be drawn. If so, don't draw a border on that side.
posted by fleacircus at 6:56 PM on December 22, 2005
Or, don't collect the coordinates. Write a routine that takes a cell as an argument and which sides to draw in a cage. Get the list of cells, for each cell figure out if there is a neighboring cage cell also to be drawn. If so, don't draw a border on that side.
posted by fleacircus at 6:56 PM on December 22, 2005
Response by poster: Westcoaster: yes, my bad. It does refer to a cage 16=0,1.
fleacircus, driveler: I can see that I'm thinking about this from the perspective of a single cage, and drawing it's outline, rather than how the cages interact with each other. This approach makes more sense, and feels a bit easier to implement.
My current approach involves working in a clockwise manner around the edge of the shape, and seeing if the cage can be extended in that direction. Your proposed methods seem much simpler.
I'm currently working with the set of cells and seeing if there are cage cells to either side of them, then drawling lines and working in a clockwise manner.
posted by gaby at 3:16 AM on December 23, 2005
fleacircus, driveler: I can see that I'm thinking about this from the perspective of a single cage, and drawing it's outline, rather than how the cages interact with each other. This approach makes more sense, and feels a bit easier to implement.
My current approach involves working in a clockwise manner around the edge of the shape, and seeing if the cage can be extended in that direction. Your proposed methods seem much simpler.
I'm currently working with the set of cells and seeing if there are cage cells to either side of them, then drawling lines and working in a clockwise manner.
posted by gaby at 3:16 AM on December 23, 2005
This thread is closed to new comments.
posted by kcm at 2:33 PM on December 22, 2005