Covering a bitmap with (minimal) boxes/rectangles.

graphics

Next

• 1. Chazelle linear time algorithm for constructing intersection of convex polyhedra
Hi All, I am waiting to obtain a copy of Chazelle's article on constructing the intersection of convex polyhedra in linear time (SIAM Journal of Computing, 1992) and I was wondering a) whether anyone is aware of an implementation of this algorithm and b) whether this is one of those algorithms that is theoretically viable but impractical to implement (i.e., in contrast to the Muller and Preparata algorithm). Thanks, Evan
• 2. Combining image maps for objects with holes
Hello I have some code which extracts closed polylines defining the boundary of arbitrary objects. For objects that have holes in them the code produces separate nested polylines. In my app I test if a point is inside the object by counting the number of polylines it's inside -an odd number puts it inside the object, an even number puts it outside. Now I want to use these polylines for HTML image maps but I discovered a problem. HTML scans the polylines for each object and returns true as soon as it finds a polyline that contains the point. Consequently if I have (for example) an annular region defined by two concentric circles, then the HTML applet will consider all points within the first circle to be inside the region - which is not what is required. To avoid this problem, I need to combine my nested polylines into single polylines - by means of vanishingly thin corridors connecting the outer polylines to the inner polylines. Does anyone have any tips for doing this - or (even better) know of existing code which solves this problem? Many Thanks Jeff
• 3. left handed systems
I trying to export scene data between some different 3d applications. I quick checked 3dsmax, XSI and maya axis. I found that XSI and maya both have the same axis layout, and 3dsmax changed the planes (what XSI calls top, is front in 3dsmax). But all of them have a right-handed coordinate system, so for example, an opengl exporter is just a raw export for all platforms (taking care of the camera up vector) I never wrote a directx exporter, but i read everywhere that directx is lefthand. So, every directx exporter ever wrote must change not only the up vector, but flip some axis on all vertex, and all transformations. am i wrong? it sounds extrange to me that every D3D game use a different "hand" that all 3d applications... Thank you very much for your time!
• 4. distance between point and a triangle
I've read and studied the solution for this problem given in "Geometric Tools for Computer Graphics" and later, I've implemented the proposed method in Visual Basic with success (until now). Nevertheless, I'd like to understand what I am programming and there is a little fragment that worries me. It's referring to the solution of finding the point of minimum distance when the global minimum lays in region 2. The minimum has to be on edge s=0 or edge s+t=1. That's clear. But in the text it is said that at least one of the directional derivatives (in the directions of these two posible edges) has to be positive. Why? Then, the election of the edge is based on the signs of these two directional derivatives. In the code part of the discussion, only one of these derivatives is taking into account. Is it coherent with what is said on the text? Why only one of them is considered? Thanks in advance for your help and sorry for my poor english.

Covering a bitmap with (minimal) boxes/rectangles.

```Hello,

I have this idea to try and describe the area of a bitmap with
boxes/rectangles.

Like covering a bitmap with boxes/rectangles.

The only catch is that only pixels that are not transparent/black should be
covered.

So only the pixels which actually consists out of colors should be covered.

Furthermore the mission is to try and describe the bitmap with as little
boxes/rectangles as possible.

So this is an optimization problem.

I can imagine that different solutions might exist... some might be better
than others.

1. To what category does this problem belong ? (Covering ? Packing ?)

2. Is there already an algorithm which does this ?

If not what can you think of ? ;)

I am not really looking for a "solver model" an algorithm will do just
fine... even heuristics which give sub optimal might be fine...

It reminds me a bit of the "bin packing" problem for texture mapping.

Except this time some parts of the texture map are already taken and thus
some areas remain free to pack.

So in other words... the black/transparent colors are already taken in
area... for those parts it probably doesn't matter how they are taking away
from the remaining solution space.

Hmmm...

Bye,
Skybuck.

```

Re: Covering a bitmap with (minimal) boxes/rectangles.

```Hmm..

Ok... I think I have a nice algorithm in my little big heady... but for now
I will keep it secret LALALALAL LOL.

But I am curious what you can come up with if you willing to share that is
?! Unlike me ?! I am so {*filter*} LOL.

But if it's already know then you can share can't you ?! ;) :)

If it turns out that my algo sux then I will get back to you...

Maybe I will turn it into a competition.

It would work as follows:

1. I give you a bitmap and you must turn it into rectangles/boxes with your
algorithm.

Then we simply count boxes and compare the results.

That way we don't have to reveal our algorithms and we can simply compare
the results instead... to see which algorithm is actually better...

That would be cool ! ;) =D

I like this idea a lot !

I am going to make a website for it and turn it into a little programming
contest !

JAWHOLE ! :) =D LOL.

Bye,
Bye,
Skybuck.

```

Re: Covering a bitmap with (minimal) boxes/rectangles.

```On Sat, 11 Dec 2010 05:26:23 +0100, "Skybuck Flying"

What about reinventing the wheel? Or light bulb?

A.L.
```

Re: Covering a bitmap with (minimal) boxes/rectangles.

```

Hihihihihihihi.

Big words you speak of ! (Yoda says) ;) :)

You self-pro-claimed-jedi will get your chance to prove yourself in combat
soon enough ! ;) :)

See the next/new posting for contest details ! ;) :)
(Subject: "Programming Contest: BoxifyMe" )

I shall keep a close eye on you ! ;) =D

Bye,
Skybuck ;) =D

```

Re: Covering a bitmap with (minimal) boxes/rectangles.

```>

I'll put a small rectangle around every single bit on your bitmap.

```

Re: Covering a bitmap with (minimal) boxes/rectangles.

```

Hmm ok you do that... then your entry will be 100x100 = 10000 boxes.

I already completed my first algoritm idea... and it only produces 306
boxes.

So you are already defeated by me by a big margin ! ;) :)

The results/outputs still need to be verified... but so far it's looking
pretty good/reliable/correctly...

See here and be jealous hahahahahahahahaha:

http://www.**--****.com/

Me pointing a big colorized pictured gun at you and asking you the following
question:

"Can you do better punk ?" ;) :)

Bye,
Skybuck ;) =D

```

Re: Covering a bitmap with (minimal) boxes/rectangles.

```On Sat, 11 Dec 2010 06:14:00 +0100, "Skybuck Flying"

Somehow you were not in my kill file...

A.L.
```

Re: Covering a bitmap with (minimal) boxes/rectangles.

```

I trust that's now been corrected?

/Paul
```

```

Shame on you..

```

Re: Covering a bitmap with (minimal) boxes/rectangles.

```

LOL, If you can't even straighten out your killfile... then what possible
hope could you have for this contest ?! ;) =D

Be seeing you ! LOL.

Bye,
Skybuck ;) =D

```

Re: Covering a bitmap with (minimal) boxes/rectangles.

```

That's a good start.

Next: join rects of "equal" color (with some formula to compare two
slightly different colors -- the parameters for that are not given).

Since you are talking about *boxes*, you must next check how much each
single rectangle can grow in either or both x and y direction. All you
have to do is to keep track of the largest area -- for when an increase
in y means a decrease in x and a net smaller rectangle area.

Since you want "as little boxes as possible", you could add a fuzziness
parameter: how much would you gain by covering one single lousy pixel of
a 'bad' color? How much by covering two? Three? Eigh{*filter*}? This can
probably given a rational score by comparing the number of 'false'
coverings to the total number of pixels covered in the entire rectangle.
That way, a 10x10 rectangle that covers one wrong pixel is worse than a
100x100 rectangle that covers 10 wrong pixels.

After that, you'd probably have millions of possible box arrangements;
picking the optimal solution could be done with some kind of network
optimizer (the name of which escapes me for the mo').

[Jw]
```

Re: Covering a bitmap with (minimal) boxes/rectangles.

```

Thanks great idea. (I think you mean a bigger rectangle area here but ok)

The mission is not to create "very little boxes" but the opposite to create
"as few boxes as possible" so an implementation will want to make big boxes
because they describe more and reduce the number of needed boxes, probably
;)

Your idea of doing an "area" calculation for grow direction possibilities is
nice.

I might give this area heuristi (growth decision moment) an implementation
try in the near future.

Therefore if I do implement it... I will call that version: "area".

Perhaps even "edge+area" ;) :)

Bye,
Skybuck =D

```

Re: Covering a bitmap with (minimal) boxes/rectangles.

```Perhaps you were correct and smallest box should be found first by greedy
algorithm...

I think I might give that idea a try to see if you on to something ;) :)

Bye,
Skybuck.

```

Re: Covering a bitmap with (minimal) boxes/rectangles.

```Hi, maybe mu suggestion will help you.

I suppose you're able to create bitonal mask (pixmap) for pixels of
interest.
Then you should perform seed fill on this mask, identifying connected
components.
(This process also called morphological reconstruction, see
http://www.**--****.com/ )
When filling, you are maintaining a stack of pixels, say pairs of
integers {x,y}.

For solution I propose you to maintain additional array of {x,y}
pairs.
Sorting this array by x than by y, and removing adjacent pixels will
produce
a vertical run-length representation of your raster spot (changing
order comparing y first
will give you horizontal run-length representation). With run-length
representation
I understand array of triples {x,y,run} where x,y are seed point
coordinates and
run is the length of single-pixel line. This triples can be converted
to rectangles
with width (height if horizontal) equal to 1.

Having this array of runs you can find adjacent runs with same run
length, producing
single rectangle instead of few thin ones (sorting trick is applicable
too!).

Some notes on implementation:
1. Sorting can be done very fast by using counting sort
(lsd-radix sort), 2 bytes for each coordinate (or 4 bytes for pair
{x,y}) are enough
in most of applications.
2. It is not necessary to compute pixmap to perform seed filling, see
grayscale seed-fill.
3. You can find contours of yours objects of interests, convert them
into chain code, etc
and turn your problem into "optimal rectilinear polygon partition by
rectangles", which
is NP-hard. My suggestion is a one of heuristics.

Cheers.

```

Re: Covering a bitmap with (minimal) boxes/rectangles.

```

Yes, ok.

Anything is possible yes.

I can maintain anything but ok.

Why sort ?

In other words, largest height per pixel.

In other words, largest width per pixel.

How ? Only pixels next to it might have same length etc but ok.

I guess this is simply trying to grow the rectangle.

Again what does sorting have to do with it ?

I am not interested in sorting algorithms, just keep the description of the
algorihm basic ;)

I also don't need details about bytes and such... just keep it simple...
I'll figure out the rest.

What you call pixmap... I call a 2D array of boolean indicating if pixel is
on or off.

mPixelEnabled[vX,vY] := true or false;

Counters ok, what is chain code ? you mean growing them ?

Ok, I'll google this and read up on it... if I can make any sense of it and
have any questions I'll get back to you assuming you know it ?

Bye,
Skybuck.

```

```Hello,

I have this idea to try and describe the area of a bitmap with
boxes/rectangles.

Like covering a bitmap with boxes/rectangles.

The only catch is that only pixels that are not transparent/black should be
covered.

So only the pixels which actually consists out of colors should be covered.

Furthermore the mission is to try and describe the bitmap with as little
boxes/rectangles as possible.

So this is an optimization problem.

I can imagine that different solutions might exist... some might be better
than others.

1. To what category does this problem belong ? (Covering ? Packing ?)

2. Is there already an algorithm which does this ?

If not what can you think of ? ;)

I am not really looking for a "solver model" an algorithm will do just
fine... even heuristics which give sub optimal might be fine...

It reminds me a bit of the "bin packing" problem for texture mapping.

Except this time some parts of the texture map are already taken and thus
some areas remain free to pack.

So in other words... the black/transparent colors are already taken in
area... for those parts it probably doesn't matter how they are taking away
from the remaining solution space.

Hmmm...

Bye,
Skybuck.

```

```Hi,

I have a problem and I hope somebody can put some light on it. Suppose
there is a big rectangle, 'A', and suppose that I put several smaller
rectangles over 'A'. The small rectangles can be overlapped, but they
are all inside 'A'. The question is, is it possible to know whether
'A' is totally covered? In other words, it is possible to know if all
points inside 'A' are also inside of, at least, one small rectangle?

Example:
'A' is the rectangle with coordinates (down-left corner and upper-
right corner) <0, 0> <100, 200>
There are two smaller rectangles: '1' is <0, 0> <50, 100>; '2' is <50,
100> <200, 200>.
In this case, 'A' is not totally covered because, for example, point
<70, 20> is not in any of the smaller rectangles.

Does this problem is solvable?

Thanks

```

```Given n points in the plane and a fixed rectangle r. How can one find a
translation of r that covers as many of these n points as possible?

This translation clearly can be found in O(n^2) by trying all reasonable
locations for r. Is there any faster algorithm known?
```

```Using PM 6.5  I've got a multipage document with header in master
page. I don't want to print header on first 2 pages. In the past, I've
drawn a box around header using no line and paper fill. That's not
working this time. Any suggestions?

Leo aka Charlie

Yahoo is spam trap      XXXX@XXXXX.COM  is real
```