y = y 0 + R sina,

D i+1 [with y i+1 = y i-1] = 2x 2 i+1 +2y 2 i+1 +4x i+1 -2y i+1 +3-2R 2 = 2(x i+1) 2 +2(y i-1) 2 +4(x i+1)-2(y i-1)+3-2R 2 = D i +4(x i-y i)+10.

Now that we have obtained the recurrent expression for D i+1 via D i, it remains to obtain D 1 (the control value at the starting point.) It cannot be obtained recursively, because the previous value is not defined, but it can easily be found directly

x 1 = 0, y 1 = R Yu D 1 1 = (0+1) 2 +( R-1) 2 -R 2 = 2-2R,

D 1 2 = (0+1) 2 + R 2 -R 2 = 1

D 1 = D 1 1 + D 1 2 = 3-2 R.

Thus, the circle construction algorithm implemented in bres_circle is based on sequential selection of points; depending on the sign of the control value D i the next point is selected and the control value itself is changed as necessary. The process starts at point (0, r), and the first point placed by the sim procedure has coordinates ( xc, yc+r). At x = y the process ends.

If space is non-discrete, then why does Achilles overtake the tortoise? If space is discrete, then how do particles implement Bresenham's algorithm?

I have long been thinking about what the Universe is like as a whole and the laws of its work in particular. Sometimes descriptions of some physical phenomena on Wikipedia are quite confusing to remain incomprehensible even to a person who is not very far from this field. Moreover, I was unlucky with people like me - those who were at least very far from this area. However, as a programmer, I come across a slightly different plane - algorithms - almost every day. And one day, in the process of implementing some kind of 2D physics in the console, I thought: “But the Universe is essentially the same console of unknown dimension. Is there any reason to think that for linear motion on the screen of this console, so to speak, the particles should not implement the Bresenham algorithm? And there seems to be no reason.

Anyone who is interested in what the Bresenham algorithm is, how it can be related to physics and how this can affect its interpretation - welcome to the cat. Perhaps you will find there indirect confirmation of the existence of parallel Universes. Or even universes nested within each other.

Bresenham's algorithm

F(x) = 0
And

F(x) = x
Now imagine that the segment needs to be rotated another 10 degrees, for example. Then we get the classical homogeneous linear function:

F(x) = x * tan(55)
And drawing a graph of this function with a regular pen on a regular piece of paper is not difficult for any 7th grade student. However, what to do in the case of our supposed piece of paper, which is discrete in cells? After all, then there is a need to choose which cells to paint over when drawing a line. This is where the Bresenham algorithm comes to our aid.

This aglorythm was developed by Jack Bresenham in 1962, when he worked at IBM. It is still used to implement virtual graphics in many application and system systems, from production equipment to OpenGL. Using this algorithm, it is possible to calculate the most suitable approximation for a given line at a given level of discreteness of the plane on which this line is located.

Implementation in Javascript for the general case

var draw = (x, y) => ( ... ); // function for drawing a point var bresenham = (xs, ys) => ( // xs, ys are arrays and, accordingly, let deltaX = xs - xs, deltaY = ys - ys, error = 0, deltaError = deltaY, y = ys ; for (let x = xs; x<= xs; x++) { draw(x, y); error += deltaError; if ((2 * error) >= deltaX) ( y -= 1; error -= deltaX; ); ); );

Another indirect confirmation of the discreteness of space can be a judgment based on the above: if, with a certain reduction in the scale of the observed, it loses the ability to be described using Euclidean geometry, then it is obvious that when the minimum distance threshold is overcome, the method geometric description there must still be a subject. Let in such a geometry one parallel line may correspond to more than one other line passing through a point not belonging to the original line, or in such a geometry there is no concept of parallelism of lines or even the concept of lines at all, but there is any hypothetically imaginable method for describing the geometry of an object less than the minimum length. And, as you know, there is one theory that claims to be able to describe such geometry within a known minimum threshold. This is string theory. It presupposes the existence something, what scientists call strings or branes, in 10/11/26 dimensions at once, depending on the interpretation and mathematical model. It seems to me personally that this is approximately how things are, and to substantiate my words, I will conduct a thought experiment with you: on a two-dimensional plane, with its geometry completely “Euclidean,” the already mentioned rule works: through one point you can only draw one straight line parallel to the given one. Now we scale this rule by three-dimensional space and we get two new rules arising from it:

1. Similar - through one point you can draw only one straight line parallel to the given one
2. At a specified distance from a given line there can be an infinity-X of straight lines, and this infinity-X is Y times less than the infinity-Z of all lines parallel to a given one, regardless of the distance, where Y is, roughly speaking, possible quantity thickness of a straight line within space

Parallel and nested universes?

In other words, either Achilles will never catch up with the turtle, or we are in the Matrix, the entire observable Universe and famous physics, most likely - just a drop in the huge ocean of possible diversity of reality.

Bresenham's algorithm is an algorithm that determines which points on a two-dimensional raster need to be shaded in order to obtain a close approximation of a straight line between two given points.

The segment is drawn between two points - (x0,y0) and (x1,y1), where in these pairs the column and row are indicated, respectively, the numbers of which increase to the right and down. First we will assume that our line goes down and to the right, and the horizontal distance x1 − x0 exceeds the vertical distance y1 − y0, i.e. the inclination of the line from the horizontal is less than 45°. Our goal is for each column x between x0 and x1, determine which row of y is closest to the line and draw a point (x,y).

General formula lines between two points:

Since we know column x, row y is obtained by rounding to a whole number next value:

However, there is no need to calculate the exact value of this expression. It is enough to note that y grows from y0 and for each step we add one to x and add the slope value to y

which can be calculated in advance. Moreover, at each step we do one of two things: either keep y the same or increase it by 1.

Which of these two to choose can be decided by tracking the error value, which means the vertical distance between current value y and exact value y for current x. Whenever we increase x, we increase the error value by the amount of slope s given above. If the error is greater than 0.5, the line is closer to the next y, so we increase y by one while decreasing the error value by 1. In the implementation of the algorithm below, plot(x,y) draws a point and abs returns absolute value numbers:

function line(x0, x1, y0, y1)

int deltax:= abs(x1 - x0)

int deltay:= abs(y1 - y0)

real error:= 0

real deltaerr:= deltay / deltax

int y:=y0

for x from x0 to x1

error:= error + deltaerr

if error >= 0.5

error:= error - 1.0

Let the beginning of the segment have coordinates (X 1,Y 1), and the end (X 1,X 2). Let's denote

Dx=(X 2 -X 1),dy=(Y 2 -Y 1) . Without loss of generality, we will assume that the beginning of the segment coincides with the origin of coordinates, and the straight line has the form

Where. We believe that starting point is on the left. Let at the (i-1)th step the current point of the segment be P i -1 =(r,q) . The choice of the next point S i or T i depends on the sign of the difference (s-t). If (s-t)<0 , то P i =T i =(r+1,q) и тогда

X i +1 =i+1;Y i +1 =Y i , if (s-t)≥0, then P i =T i =(r+1,q+1) and then X i +1 =i+ 1 ; Y i +1 =Y i +1 ;

dx=(s-t)=2(rdy-qdx)+2dy –dx

Since the sign of dx=(s-t) coincides with the sign of the difference), we will check the sign of the expression d i =dx(s-t). . Since r=X i -1 and q=Y i -1 , then

d i +1 = d i +2dy -2dx(y i -y i -1) .

Let at the previous step d i<0 , тогда(y i -y i -1)=0 и d i +1 = d i +2dy . Если же на предыдущем шаге d i ≥0 , тогда(y i -y i -1)=1 и d i +1 = d i +2dx(y i -y i -1)

It remains to find out how to calculate d i. Since for i=1

Procedure Bresenham(x1,y1,x2,y2,Color: integer);

dx,dy,incr1,incr2,d,x,y,xend: integer;

dx:= ABS(x2-x1);

dy:= Abs(y2-y1);

d:=2*dy-dx; (initial value for d)

incr1:=2*dy; (increment for d<0}

incr2:=2*(dy-dx); (increment for d>=0)

if x1>x2 then (start from the point with the smaller x value)

PutPixel(x,y,Color); (first point of the segment)

While x

d:=d+incr1 (select the bottom point)

d:=d+incr2; (select the top point, y-increases)

PutPixel(x,y,Color);

26. General Bresenham algorithm.

The algorithm selects optimal raster coordinates to represent the segment. The larger of the increments, either Δx or Δy, is chosen as the raster unit. During operation, one of the coordinates - either x or y (depending on the slope) - changes by one. Changing another coordinate (to 0 or 1) depends on the distance between the actual position of the segment and the nearest grid coordinates. This distance is an error.

The algorithm is constructed in such a way that you only need to know the sign of this error. Consequently, the raster point (1, 1) better approximates the course of the segment than the point (1, 0). If the slope is less than ½, then the opposite is true. For a slope of ½, there is no preferred choice. In this case, the algorithm selects the point (1, 1). Since it is desirable to check only the sign of the error, it is initially set to -½. Thus, if the slope of the segment is greater than or equal to ½, then the error value at the next raster point can be calculated as e = -½ + Δy/Δx.

In order for the implementation of the Bresenham algorithm to be complete, it is necessary to process segments in all octants. This is easy to do, taking into account in the algorithm the number of the quadrant in which the segment lies and its angular coefficient. When the absolute value of the slope is greater than 1, y is constantly changed by one, and the Bresenham error criterion is used to decide whether to change the value of x. The choice of a constantly changing (+1 or -1) coordinate depends on the quadrant

var x,y,sy,sx,dx,dy,e,z,i: Integer;
change: boolean;
begin
x:=x1; y:=y1;
dx:=abs(x2-x1); dy:=abs(y2-y1) ;
sx:=sign(x2-x1); sy:=sign(y2-y1);
e:= 2*dy-dx;
if dy
else begin
z:=dx;
dx:=dy; dy:=z;
change:=true
end;
for i:=1 to dx+dy do begin
if dy< dx then begin
if change then y:=y+sy
else x:=x+sx;
e:=e+2*dy;
end else
if change then x:=x+sx
else y:=y+sy;
e:=e-2*dx
end;
Form1.Canvas.Pixels:=clblack; // output a point, for example
end;

27. Bresenham algorithm for generating a circle

The raster needs to be expanded as linear and other, more complex functions. The distribution of terminal cuts, such as keels, ellipses, parabolas, hyperbolas, was assigned to the number of robots. With the greatest respect, understandably, a stake has been added. One of the most efficient and easiest to understand circle generation algorithms is that of Bresenham. For the cob, it is important to generate only one eighth of a stake. These parts may be removed by successive beats. Once the first octant is generated (from 0 to 45 ° of the anti-year arrow), then the other octant can be expressed as a mirror image of the straight line y = x, which together gives the first quadrant. The first quadrant is knocked out with a straight line x = 0 to remove the supporting part of the stake from the other quadrant. The top one is knocked down straight at = 0 to complete the task.

To show the algorithm, let's look at a quarter of the stake centered on the cob of coordinates. Please note that since the algorithm starts at the point x = 0, y = R, then when generating a circle behind the year arrow in the first square, y is monotonically descending function of the arguments. Similarly, if the output point is y = 0, x == R, then when generating a circle opposite the arrow x will be a monotonically decreasing function of the argument y. In our case, the generation behind the year arrow with the cob at the point x = 0, y = R is selected. It is transferred that the center of the stake and the cob point are exactly at the raster points.

For any given point on the circle when generating behind the year arrow, there are only three options for selecting the next pixel, the closest circle: horizontally to the right, diagonally down and to the right, vertically down. The algorithm selects a pixel for which the minimum square is between one of those pixels and the circle.

28. The concept of a fractal. History of fractal graphics

In everyday life, you can often observe images (patterns) that, it would seem, cannot be described mathematically. Example: the windows freeze in winter, you can end up observing the picture. Such sets are called fractal. Fractals are not similar to well-known figures from geometry, and they are built according to certain algorithms that can be implemented on a computer. Simply put, a fractal is an image resulting from some transformation applied repeatedly to the original shape.
The first ideas of fractal geometry arose in the 19th century. Cantor, using a simple recursive procedure, turned the line into a collection of unconnected points, which were later called “Cantor Dust.” He would take a line and remove the central third and then repeat the same with the remaining sections. Peano drew a special kind of line. To draw it, Peano used the following algorithm:
He took a straight line and replaced it with segments three times shorter than the original line. Then he repeated the same action with each of the segments. Its uniqueness is that it fills the entire plane, i.e. for each point located on the plane, you can find a point belonging to the Peano line.
The founder of fractal geometry is considered Benoit Mandelbrot. Mandelbrot introduced the concept of "fractal".

A fractal is a geometric figure consisting of parts and which can be divided into parts, each of which will represent a smaller copy of the whole. The main property of fractals is self-similarity, i.e. any fragment of a fractal in one way or another reproduces its global structure. Fractals are divided into geometric, algebraic, stochastic, and systems of iterable functions.

29. The concept of dimension and its calculation

In our daily lives we constantly encounter dimensions. We estimate the length of the road, find out the area of ​​the apartment, etc. This concept is quite intuitive and, it would seem, does not require clarification. The line has dimension 1. This means that by choosing a reference point, we can define any point on this line using 1 number - positive or negative. Moreover, this applies to all lines - circle, square, parabola, etc.

Dimension 2 means that we can uniquely define any point by two numbers. Don't think that two-dimensional means flat. The surface of a sphere is also two-dimensional (it can be defined using two values ​​- angles like width and longitude).

If we look at it from a mathematical point of view, the dimension is determined as follows: for one-dimensional objects, doubling their linear size leads to an increase in size (in this case, length) by a factor of two (2^1).

For two-dimensional objects, doubling linear dimensions results in an increase in size (for example, the area of ​​a rectangle) by four times (2^2).

For 3-dimensional objects, doubling the linear dimensions leads to an eightfold increase in volume (2^3) and so on.

Geometric fractals

It was with these fractals that the history of the development of fractals in general began. This type of fractal is obtained through simple geometric constructions. Typically, when constructing geometric fractals, the following algorithm is used:

1. A set of segments is taken, on the basis of which a fractal will be constructed.
2. Certain rules are applied to this set, which transform it into some geometric figure.
3. The same set of rules apply to each part of this figure. With each step, the figure will become more and more complex and, if we carry out an infinite number of transformations, we will get a geometric fractal.

Examples of geometric fractals: Peano curve, Koch snowflake, fern leaf, Sierpinski triangle,

Rice. Snowflake Koch

Rice. Sheet

Rice. Sierpinski triangle

Algebraic fractals

Fractal- a complex geometric figure that has the property of self-similarity, that is, composed of several parts, each of which is similar to the entire figure

Algebraic fractals got their name because they are built on the basis of algebraic functions. Algebraic fractals include: Mandelbrot set, Julia set, Newton basins, biomorphs.

-Mandelbrot set: The Mandelbrot set was first described in 1905 by Pierre Fatou. Fatou studied recursive processes of the form

Starting with a point on the complex plane, you can obtain new points by successively applying this formula to them. Such a sequence of points is called an orbit under transformation

Fatou found that the orbit under this transformation shows quite complex and interesting behavior. There is an infinite number of such transformations - one for each value. (named Mandelbrot because he was the first to carry out the required number of calculations using a computer).

-Julia set: Julia set of a rational mapping - a set of points, the dynamics in the vicinity of which are, in a certain sense, unstable with respect to small perturbations of the initial position. In case f- a polynomial, we also consider a filled Julia set - a set of points that do not tend to infinity. The usual Julia set is its boundary.

-Newton pools: Regions with fractal boundaries appear when the roots of a nonlinear equation are approximately found by Newton's algorithm on a complex plane (for a function of a real variable, Newton's method is often called tangent method, which, in this case, is generalized to the complex plane).

Let's apply Newton's method to find the zero of a function of a complex variable using the procedure:

The choice of initial approximation is of particular interest. Because a function may have multiple zeros, and in different cases the method may converge to different values.

-biomorphs: abbreviated form of the Julia set, calculated by the formula z=z 3 +c. It got its name because of its similarity to single-celled organisms.

Stochastic fractals

A typical representative of this type of fractal is the so-called plasma.

To construct it, take a rectangle and determine a color for each of its corners. Next, find the central point of the rectangle and paint it with a color equal to the arithmetic mean of the colors at the corners of the rectangle + some random number. The larger this random number, the more torn the drawing will be.

Natural objects often have a fractal shape. Stochastic (random) fractals can be used to model them. Examples of stochastic fractals:

trajectory of Brownian motion on the plane and in space;

boundary of the trajectory of Brownian motion on a plane. In 2001, Lawler, Schramm and Werner proved Mandelbrot's hypothesis that its dimension is 4/3.

Schramm-Löwner evolutions are conformally invariant fractal curves that arise in critical two-dimensional models of statistical mechanics, for example, the Ising model and percolation.

various types of randomized fractals, that is, fractals obtained using a recursive procedure into which a random parameter is introduced at each step. Plasma is an example of the use of such a fractal in computer graphics.

Fractal monotype, or stochatypy, is a trend in fine art that involves obtaining an image of a random fractal.

Related information.

Read also

Farewell in German - German online - Start Deutsch Greetings in a letter in German

Graph theory Application of graph theory in chemistry

Characteristics and Applications of Tungsten

Trivial behavior. Trivial. What is it

Bioorganic chemistry Hemoglobin and its derivatives

Collective opinion of military personnel and management of collective mood The role of public opinion in the fight against deviations from socialist moral norms

Preparation of calcium saccharates and their use as corrosion inhibitors

Aromatic compounds Electrophilic substitution examples