> 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.
Actually, your given approach already *is* image order, as well as
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.
by