Max Rectangles In Any Shape
-
I am trying to develop a program to determine the max number of rectnagles in a shape. The user would draw or define any closed shape. Next the height of the rectnagle would be defined. Then the program would calculate each rectnagle that could fit in the shape. Each rectanglke must be the height provided and always try to be as wide as possible. so if we take a simple example of a circle. The rectnagles in the middle would be the longest, and the rectnagles at the top and bottom would be the shortest. But all the rectnagles would the same hieght. Any ideas on how to go about doing this would be greatly appreciated
-
I am trying to develop a program to determine the max number of rectnagles in a shape. The user would draw or define any closed shape. Next the height of the rectnagle would be defined. Then the program would calculate each rectnagle that could fit in the shape. Each rectanglke must be the height provided and always try to be as wide as possible. so if we take a simple example of a circle. The rectnagles in the middle would be the longest, and the rectnagles at the top and bottom would be the shortest. But all the rectnagles would the same hieght. Any ideas on how to go about doing this would be greatly appreciated
It sounds like you read a small paper of mine that was based on a piece of code (ellipses/circles/convex shapes) I wrote for doing exactly what you are talking about, but I only gave the paper to one person. Determining the number of rectangles for a circle or ellipse is not difficult [given the algorithm], provided that they consist of overlapping rectangles. Doing it for any shape gets a bit crazy and I have still not figured out that problem. The first thing you have to do (for any shape) is determine the boundaries, which means determining where each point on the edge will be drawn. Given the boundaries you must look for the all the horizontal lines that are adjacent to each other and of the same length, with the same starting and ending X values. It sounds fairly simple but it is way more complicated than that (for what I was trying to do). A good place to look is at algorithms for filling polygons like “Michael Abrash’s Graphics Programming”, He does not cover the subject you are asking about, but he does cover polygon edge scanning (polygon filling). I am very curious as to what purpose you are applying this too and have kept my answer as general as possible, because I do not know the why.
INTP "Program testing can be used to show the presence of bugs, but never to show their absence."Edsger Dijkstra
-
It sounds like you read a small paper of mine that was based on a piece of code (ellipses/circles/convex shapes) I wrote for doing exactly what you are talking about, but I only gave the paper to one person. Determining the number of rectangles for a circle or ellipse is not difficult [given the algorithm], provided that they consist of overlapping rectangles. Doing it for any shape gets a bit crazy and I have still not figured out that problem. The first thing you have to do (for any shape) is determine the boundaries, which means determining where each point on the edge will be drawn. Given the boundaries you must look for the all the horizontal lines that are adjacent to each other and of the same length, with the same starting and ending X values. It sounds fairly simple but it is way more complicated than that (for what I was trying to do). A good place to look is at algorithms for filling polygons like “Michael Abrash’s Graphics Programming”, He does not cover the subject you are asking about, but he does cover polygon edge scanning (polygon filling). I am very curious as to what purpose you are applying this too and have kept my answer as general as possible, because I do not know the why.
INTP "Program testing can be used to show the presence of bugs, but never to show their absence."Edsger Dijkstra
Yeah I agree for any shape (closed not open btw, but allow for holes) is a little crazy, but I think it can be done. Really the application will be filling this shape with text, but the text portion is not important to me, what is important is the rectangels that can fit in the shape. Then obvioulsy it is very easy to fill these rectangles with text. If you have some sample code of your algorithm for convex shapes, I would love to see it. Was it for all convex shapes or just circles and ellipses?
-
Yeah I agree for any shape (closed not open btw, but allow for holes) is a little crazy, but I think it can be done. Really the application will be filling this shape with text, but the text portion is not important to me, what is important is the rectangels that can fit in the shape. Then obvioulsy it is very easy to fill these rectangles with text. If you have some sample code of your algorithm for convex shapes, I would love to see it. Was it for all convex shapes or just circles and ellipses?
I am afraid that I misplaced the original source code; I may have lost it, as I can only find an older version of my library. The code was originally an experiment in clipping lines to an elliptical/circle and I never generalized it for any convex shape, although I had planed too at a latter date. What I did was break the ‘Cohen-Sutherland Line-Clipping Algorithm’ (Computer Graphics Principles and Practice, Foley et al., pp. 113-117) into a series of small inline functions, so I could pick and choose the pieces required; in this case I was only interested in the corners. Given that and a list of the horizontal lines, I was able to clip all drawing done by my old graphics library to the elliptical shape as if it was a clipping rectangle. I suspect that there are faster ways to do it, but I have not thought of, nor seen, another way to do it. If you overlay a copy of the ‘Cohen-Sutherland region outcodes’ diagram over the shape with the clipping rectangles corners touching the edges, you will see the idea behind what I was doing. Example: draw the diagram and then draw a circle around it so that the edge passes through the four corners of the clipping rectangle and you will see why I only considered the corners. Good Luck!
INTP "Program testing can be used to show the presence of bugs, but never to show their absence."Edsger Dijkstra
-
I am trying to develop a program to determine the max number of rectnagles in a shape. The user would draw or define any closed shape. Next the height of the rectnagle would be defined. Then the program would calculate each rectnagle that could fit in the shape. Each rectanglke must be the height provided and always try to be as wide as possible. so if we take a simple example of a circle. The rectnagles in the middle would be the longest, and the rectnagles at the top and bottom would be the shortest. But all the rectnagles would the same hieght. Any ideas on how to go about doing this would be greatly appreciated
You might want to check out this article[^]. (Window regions are simply lists of rectangles that cover the desired area)
----
It appears that everybody is under the impression that I approve of the documentation. You probably also blame Ken Burns for supporting slavery.
--Raymond Chen on MSDN