Re: Algorithm advice needed

Jeff Godfrey wrote:
> Now, I don't really expect someone to provide an algorithm for me to
> accomplish the above, but maybe someone is familiar with this type of
> problem to tell me how to "search" for what I'm after. In other words, is
> this a particular class of mathematical problem that if I knew proper
> search terms for, I might find info on the net?
>
> Thanks for any input.
>
> Jeff Godfrey

Several years ago, I spent some time on a pet project in computational
geometry. (Of course, I used Tk for the visualization; I probably
would not have done it without it.)

>>From what I have gathered, a lot depends on how you choose to represent
or model the task rather than on algorithms. So I offer this approach
in the hope that you may find it useful:

1) Start from one edge of your surface and sweep towards the other
edge. At this point, your surface is just one singular block (with a
bunch of cutouts). Maintain x,y coordinates for all objects.

2) As you come across a cutout, identify its bounding box. For
simplicity, you can treat the bounding box as a rectangular shape.
(You can always optimize it later.)

3) Once you you have identified the coordinates of the bounding box,
replace the original surface object with (up to) 4 new objects. For
analogy, imagine a piece of paper, with a square hole in the middle of
it. Now, using a pair of scissors, cut along the edges of the hole in
the middle to create four smaller pieces of paper. None of the
resulting pieces should have the hole.

4) Except for the first piece (i.e., the one where your sweep covered
already), repeat the above steps for all other objects you created
above.

When you are done, what you are left with is a bunch of smaller
surfaces with no cutouts in them. Now, for each one, see if the
surface area (square feet, etc.) matches one of the suction cups. Keep
the matching ones in your solution set. Combined, they will give you
all potential solutions. Since you are interested in center of gravity
and peeling off effect, you may choose a solution set that balances the
object. (I.e., choose the ones that are on opposing sides so the
suction cups balance the object.)

As I indicated earlier, you may optimize this by treating the binding
box of cutouts as irregular shapes instead of rectangular shapes.
Depending on the actual cutout shapes you encounter, you may even find
further optimization unnnecessary.

.