procedure to procedure

[alan2here]

Say one has a procedure that describes the placement of objects in some number of dimensions, such as pixels on a grid in a raster image, or nodes in a vector image.

 

Lets say that for example the procedure describes the drawing of a filled in a circle, in the raster example for a larger circle completion takes longer as more pixels need to be set as inside and in the vector version a smoother circle takes longer as more edge nodes are required.

 

In all cases for a generic "any algorithm of this type" the image may need to be rendered entirely before it's possible to know what any one part of the image looks like. This sort of procedure is sometimes refered to as generating data and then "push"ing it onto an image.

 

Given the details of this procedure such as it's computer code, equation etc..., but no additional knowledge of the problem such as how a circle is supposed to work, can the representation of the problem (code\equation) be reworked algorithmically (not requiring a person) into a form where a "pull" request can be made, by this I mean a request on a location of the image for the state of that location, such as weather it is inside or outside the shape that doesn't require the computing of the entire image.

 

 

A less trivial example could be one of the many different ways of drawing the Sierpinski triangle known as the chaos game into a form where a position could be queried for it's distance from the nearest part of the shape.

 

The chaos game involves repeating an action N number of times where the larger N is the greater accuracy the shape is, in order to convert this algorithm N may have to be made infinite, the same would apply to the circle example.

 

 

Below are two equivalent functions. At the end of both functions "result" is taken as the result, in the first case "detail" represents the level of detail and a set of coordinates are returned, in the 2nd case the detail is infinite and only one point can be queried at a time, this point is "target_x" and "target_y".

 

"
ang = 0
[b]result[/b] = {}
while (ang < 10)
{
 ang += [b]detail[/b]
 x = sin(ang)
 y = cos(ang)
 [b]result[/b].∪=({x, y}) // add the set {x, y} to the end of the set
}
"

=

"
[b]result[/b] = sqrt([b]target_x[/b] ^ 2 + [b]target_y[/b] ^ 2)
"

 

 

lets now suppose that we had a problem we didn't know in such detail but we have the "push" form of the problem. In this case it is the chaos game.

 

"
p = {0, 0} // the point that moves around
corners = {{0, 0}, {0, 1}, {1, 0}} // the three corners of the triangle, sorry it's not equilateral
[b]result[/b] = {}
n = 0
while (n < [b]detail[/b])
{
 n += 1
 p = half_way_between(p, corners.at(random_integer_0_1_or_2())
 result.∪=(p) // add p to the end of the set
}
"

=

"
?
"

 

I'm not as intrested in a solution to this one problem as a generic solution.

Edited April 22, 2010 by alan2here

[khaled]

using an algorithm to generate a picture is not useful, pictures we know are no pattern

but, chaos algorithm is good to simulate cosmic unreachable events ...

it's because we may give initial conditions (sometimes random),

because the random chaos simulation is the best choice for anonymous events,

 

but about what you mentioned of "repeating N times can go infinite",

 

it means a computer can run infinite, means you won't be able to wait until it stops

 

but like the non-terminating decimal numbers, you round up to some level

 

and when the N algorithm is running on a computer, it shows current results at the moment,

you study current to its past,

 

like a doctor who diagnoses a patient ...

 

that's all i can guess,

[insane_alien]

i'd imagine it depends on the algortihm used to generate the image.

 

if you have one that calculates a pixel independant of the surrounding pixels then it is trivial, just feed it the proper seed and coordinates and it should pop out.

 

as the pixels start to depend on the surrounding pixels then this will become more complex. with these you'd need to run it it until that desired pixel is generated.

 

and i suppose you could get even more complex ones where it applies an iterative approach, then you may need to generate the picture several times over to find out the value.

 

i'm not sure if there can be a generic solution that is efficient.

[khaled]

let's say for example you draw pixels through iterations from the left-side of the screen to the right side,

 

simple example:

void pixelIterator(integer X, integer Y, integer colorIndex)
{
     if(Y >= screen-width) return; // STOP

     drawPixel(X,Y,colorIndex);

     pixelIterator(X+1, Y, colorIndex+1);
}

output:
|-------------------| itr 1
|-------------------| itr 2
|-------------------| itr 3

 

complex example:

 

void pixelRecursive(integer X, integer Y, integer factor)
{
     if(Y >= screen-width OR X >= screen-height) return; // STOP

     drawPixel(X,Y, getPixelColorIndex()+factor); // color = color + 1

     pixelRecursive(X+1, Y, factor+1);
     pixelRecursive(X+1, Y+1, factor);
     pixelRecursive(X, Y+1, factor-1);
}

 

this last example will create gradiant depending on parameters and initial conditions,

[the tree]

if you have one that calculates a pixel independant of the surrounding pixels then it is trivial, just feed it the proper seed and coordinates and it should pop out.

 

as the pixels start to depend on the surrounding pixels then this will become more complex. with these you'd need to run it it until that desired pixel is generated.

In general I'd say that'd probably be the case. But say you wanted to look at one cell in Conway's Game of Life after a few thousand iterations with certain initial conditions - there would be some circumstances that you could prove the cell would never be alive or never be dead or give it it's status a probability without having to calculate the entire image up until that point.

[alan2here]

i'm not sure if there can be a generic solution that is efficient.

How does the inefficient one work?

 

Can you apply it to the code examples I gave?

 

 

Here is a simpler example in 1 dimension.

"
n = -[b]detail[/b]
result = {}
while (n < ([b]detail[/b] * 2))
{
 n++
 result.∪=(n)
}
"

=

"
result = modulo([b]target[/b], 1)
"