Divide shape into sub-rects
BlitzMax Forums/BlitzMax Programming/Divide shape into sub-rects
| ||
| This is conceptual, and I know I've seen an implementation before but I don't know what to search for to find it... I have an array of points that conform to a grid and define the outside edge of a shape in a clockwise rotation. e.g. x,y 0,0 1,0 1,-2 0,-2 that would define a 2 square tall, 1 square wide rectangle. I need to find a way to fill the shape with sub-rectangles. Shapes always conform to a grid layout (will always form squares, no angled sides), but can have any number of points, and create negative space. Examples would be Tetris blocks (T and L blocks specifically...). Any references or examples would be much appreciated. |
| ||
| floodfill, row by row? Are you looking for a grid-array or shape-rectangles? Can your shape have angles? |
| ||
| Would that be triangulation? Then, I know two methods: Delauney (posted it in archive) and cutting ears (there is archive code for that as well). At first, I would use the cutting ears route. However, it might be a bit overkill for this, since it concerns grid-aligned squares. Is the shape closed? Then is could suffice to just see which squares are on the inside of the shape. If you iterate through the centerpoints of possible squares (get shape bounding box, divide it into squares), then some point-in-polygon routine could help, maybe? edit: ah, i understood you needed squares, not rectangles. Then, additionally, you could collapse the squares, when they are neighbours. Last edited 2011 |
| ||
| Actually I don't need squares, rectangles would be better. Technically triangles will work since it's actually for making tris to fill a surface in opengl to cap the top of a mesh... just trying to keep it hypothetical as much as possible so it can be applied to what I need (and I can learn something from it :0) as well as be generic enough for other people to apply in other ways. I've tried implementing an ear clipping routine I found on the forums here but I think it's confused by the rectangular nature of things in some way... or maybe just has a glitch. Will look for the Delauney method as well as possibly another ear cutting implementation that might be better. |
| ||
| I've got it working right. I tore down the applet at http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/applet1.html and built it from that with a few optimizations. The approach it uses made a lot more sense to me than the other examples I found. Hope the link helps someone else later. |
   |