## Image-order algorithm wanted!

### Image-order algorithm wanted!

This is more of a math puzzle than anything else.
I have a blob created out of a list of circles of various colors. The
information is present in a file structure like this:
e.g.:
2 5 8 10 4 255
12 34 23 10 120
Given this information, I have to create the final image. (Assume: the
bounding box is known).
A trivial way to solve this is to scan-fill each and every circle.
Pixels that belong to several circles can be allotted to the one that's
center is closest to it.
This approach would be of order(n), n = number of circles. I would like
something that makes it dependent on the area of the final image, and
not on the number of circles present. I.e., I would like the processing
to be image order, instead of object order.
Suggestions, anyone?

Sent via Deja.com http://www.deja.com/

### Image-order algorithm wanted!

> I have a blob created out of a list of circles of various colors. The
> information is present in a file structure like this:
> <centerX> <centerY> <centerZ> <radius> <color>

That doesn't make much sense. There is no clearly defined 'circle'
with a given 3D center and radius. You either have to specify the
direction of the plane the circle is meant to lie in, or you must mean
spheres, not circles. If you really meant circles, the problem
translates into a 2D simplified version, directly, if you are talking
about the screen image of the blob.

Quote:> A trivial way to solve this is to scan-fill each and every circle.
> Pixels that belong to several circles can be allotted to the one that's
> center is closest to it.

If you're speaking about the 3D case, that doesn't make much sense:
you cannot see the interior of spheres anyway, and the surface will
only have isolated mathematically-precise points that belong to more
than one sphere surface. Those can generally be ignored.

For the 2D case, you'ld have to store the circle number it was
previously filled by, for each pixel, so you can later check wether
the center of another circle covering the same pixel is closer or not.

Quote:> This approach would be of order(n), n = number of circles. I would like
> something that makes it dependent on the area of the final image, and
> not on the number of circles present. I.e., I would like the processing
> to be image order, instead of object order.

object order. The algorithm is O(N) with N the sum of numbers of
pixels covered by all circles, actually, not just O(n), i.e.  if you
increase the resolution of the output image (or the radii of all
circles, by a common factor, equivalently), your circle scan
conversions will create more pixels, and increase time consumption.
This means the O(N) translates into an O(n*r^2), with r the resolution
of the output image.

Unless you make assumptions like in the usual z-buffer complexity
analysis (i.e. the more triangles there are, the smaller they'll
'obviously' be, which makes the number of covered pixels independent
of the number of triangles), I don't think you can ever get an
algorithm that is not object-order, as you call it, i.e. whose runtime
only depends on the output size, not on the number of circles in the
input. Every pixel of the output images can possibly be covered by all
input circles, so they all have to be tested. That means worst-case
complexity will always be O(n), at least.

--

Even if all the snow were burnt, ashes would remain.

### Image-order algorithm wanted!

Hi!
I propose to rearrange circles with increasing centre coordinate.
If You have multiple circles, covering the same point - you can use
some kind of hash table
Then going through image coordinate - you need only check the closest
circles - not all of circles
This rearrangement maybe should be repeated for each Y coordinate,
but this also can be reduced (not all circles cover given Y value at any
point)
The 3d representation  - ??? - in any case screen is 2d - so You can
make projections of circles before drawing

More details need more than 5 min
Good luck

> This is more of a math puzzle than anything else.
> I have a blob created out of a list of circles of various colors. The
> information is present in a file structure like this:
> <centerX> <centerY> <centerZ> <radius> <color>
> e.g.:
> 2 5 8 10 4 255
> 12 34 23 10 120
> Given this information, I have to create the final image. (Assume: the
> bounding box is known).
> A trivial way to solve this is to scan-fill each and every circle.
> Pixels that belong to several circles can be allotted to the one that's
> center is closest to it.
> This approach would be of order(n), n = number of circles. I would like
> something that makes it dependent on the area of the final image, and
> not on the number of circles present. I.e., I would like the processing
> to be image order, instead of object order.
> Suggestions, anyone?

> Sent via Deja.com http://www.deja.com/