Various Topics on Programming

..x ..enda..

Hi,

I am looking for algorithms to layout rectangles underneath each other in a
sidebar. All rectangles have different heights as well as an ankor point.
The rectangle can have scrollbars, but should be as large as possible and as
close to the ankor as possible.

As an example, I am talking about sth like the comment functionality in word
processors.

Any known algorithms for such a problem in the field of computer science?

Best regards
Max

.... ..

Max Odendahl wrote:
> Hi,
>
> I am looking for algorithms to layout rectangles underneath each other in a
> sidebar. All rectangles have different heights as well as an ankor point.
> The rectangle can have scrollbars, but should be as large as possible and as
> close to the ankor as possible.
>
> As an example, I am talking about sth like the comment functionality in word
> processors.
>
> Any known algorithms for such a problem in the field of computer science?
>
> Best regards
> Max
>
>
You won't get any help until you phrase the problem clearly. Sidebars
and scrollbars are irrelevant here-- explain the algorithmic requirements.

..x ..enda..

Hi,

ok, trying again:

I have an ankor position (aX,aY) in a plane as well as rectangles, which
should be layout on the right side of the plane, therefore, their layout
position rX is always the same for them. All rectangles have a different
height, but can be made smaller if neccessary. The goal is it now to layout
them so that rY is as close as possible to aY and as much height from the
rectangles is used as possible. There is always only one rectangle
horizontally, and they are not allowed to overlap vertically (but height can
be reduced if neccessary)

Does this make more sense now?

Regards
Max

.... ..

Max Odendahl wrote:
> Hi,
>
> ok, trying again:
>
> I have an ankor position (aX,aY) in a plane as well as rectangles, which
> should be layout on the right side of the plane, therefore, their layout
> position rX is always the same for them. All rectangles have a different
> height, but can be made smaller if neccessary. The goal is it now to layout
> them so that rY is as close as possible to aY and as much height from the
> rectangles is used as possible. There is always only one rectangle
> horizontally, and they are not allowed to overlap vertically (but height can
> be reduced if neccessary)
>
> Does this make more sense now?
>

Closer... but I still don't understand. It sounds like you want to
stack the rectangles vertically. If so, I don't see why the width of
the rectangles matters at all-- it seems like a 1D problem involving
line segments. I also don't understand what the anchor (that's how you
spell it, btw) is used for. Can you give an example input and explain
what output you would like.

Mark

..x ..enda..

Hi,


> Closer... but I still don't understand. It sounds like you want to stack
> the rectangles vertically.
Yes

> If so, I don't see why the width of the rectangles matters at all

It doesn't, it is the same width for all of them

> Can you give an example input and explain what output you would like.

Input is a list of rectangles with a specific, best case heigth, as well as
anchor position x,y
Output position should be the y position of the rectangles as well as their
height

Height should be as large as possible, y position of rectangle should be as
close to the y position of the anchor


Regards
Max

..devnu.. ..hoo.c..

Max Odendahl wrote:
> Hi,
>
> I am looking for algorithms to layout rectangles underneath each other in a
> sidebar. All rectangles have different heights as well as an ankor point.
> The rectangle can have scrollbars, but should be as large as possible and as
> close to the ankor as possible.
>
> As an example, I am talking about sth like the comment functionality in word
> processors.
>
> Any known algorithms for such a problem in the field of computer science?

My guess is that you want something akin to the dynamic layout
algorithms described by Knuth in the book Digital Typography (but use
vertical instead of horizontal boxes/glue). Tough to tell without a
rigorous problem specification, but if you can find a copy of that
book it's probably worth a look.

.... ..

Max Odendahl wrote:
> Hi,
>
>
>> Closer... but I still don't understand. It sounds like you want to stack
>> the rectangles vertically.
> Yes
>
>> If so, I don't see why the width of the rectangles matters at all
>
> It doesn't, it is the same width for all of them
>
>> Can you give an example input and explain what output you would like.
>
> Input is a list of rectangles with a specific, best case heigth, as well as
> anchor position x,y
> Output position should be the y position of the rectangles as well as their
> height
>
> Height should be as large as possible, y position of rectangle should be as
> close to the y position of the anchor
>

What is the significance of the x coordinate of the anchor? From your
descriptions, all x values should be the same.

Is the y coordinate of the anchor the desired location for the base of
the rectangle or does the rectangle merely have to overlap that location?

***uming that you cannot place all rectangles at their anchor location
with their desired heights, how do you measure the quality of the
layout. It seems that you want to optimize something but you haven't
precisely defined what is begin optimized. For example, I could place
every rectangle exactly at its anchor location, truncate its height if
necessary to avoid overlapping the rectangle above it, and that would be
/a/ solution. Is that not satisfactory? If not, why not?

You need to specify a metric.

..x ..enda..

Hi,


> What is the significance of the x coordinate of the anchor? From your
> descriptions, all x values should be the same.

Anchors have different x and y, but only y is relevant. x position for the
rectangles is the same for all rectangles, which is fixed and not related to
the x position of anchors.


> Is the y coordinate of the anchor the desired location for the base of the
> rectangle

yes

> For example, I could place every rectangle exactly at its anchor location,
> truncate its height if necessary to avoid overlapping the rectangle above
> it, and that would be /a/ solution. Is that not satisfactory? If not,
> why not?

It is not satisfactory, as the height of the rectangles should be as large
as possible.

So if there is one large rectangle before a short one (before in terms of y)
but nothing coming afterwards, the first one should not be trucated, but the
second one pushed down instead. Of course, there could be a hundred little
ones, or a large one coming up at 5th place, or or or, so all rectangle's y
position as well as their height is based on *all* other rectangles

Regards
Max

.... ..

Max Odendahl wrote:
> Hi,
>
>
>> What is the significance of the x coordinate of the anchor? From your
>> descriptions, all x values should be the same.
>
> Anchors have different x and y, but only y is relevant. x position for the
> rectangles is the same for all rectangles, which is fixed and not related to
> the x position of anchors.
>
>
>> Is the y coordinate of the anchor the desired location for the base of the
>> rectangle
>
> yes
>
>> For example, I could place every rectangle exactly at its anchor location,
>> truncate its height if necessary to avoid overlapping the rectangle above
>> it, and that would be /a/ solution. Is that not satisfactory? If not,
>> why not?
>
> It is not satisfactory, as the height of the rectangles should be as large
> as possible.
>
> So if there is one large rectangle before a short one (before in terms of y)
> but nothing coming afterwards, the first one should not be trucated, but the
> second one pushed down instead. Of course, there could be a hundred little
> ones, or a large one coming up at 5th place, or or or, so all rectangle's y
> position as well as their height is based on *all* other rectangles
>
> Regards
> Max
>
>

I give up. If you can't provide a clear and complete description of the
problem there's no helping you. According to your last message, if "the
height of the rectangles should be as large as possible" then the
solution is to make all rectangles their full height and move any
interfering rectangles out of the way.

You need to learn how to specify a problem. Try looking at, for
example, http://en.wikipedia.org/wiki/Dijkstra's_algorithm and read the
paragraph that begins, "The input of the algorithm consists of... " and
continues with, "the algorithm finds..." Until you provide a precise
specification of the problem, clearly defining the input and output,
there's no helping you.

Mark