联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-23:00
  • 微信:codehelp

您当前位置:首页 >> Java程序Java程序

日期:2020-12-15 10:55

Project of C/C++ 2011 Spring, CS, HIT
1
Interactively Exploring the Mandelbrot Set
The exercise in a nutshell
You will write a program to draw the Mandelbrot Set; you will be able to
interactively select a region of the Mandelbrot Set to zoom in on, to view it in greater
detail.
This lab only requires the use of very simple C. You will be writing some
mathematical expressions and some control structures, manipulating some variables,
and calling functions that have been provided for you, in a library called OpenCV.
You will need the skills you picked up in the lab classes to compile, link and execute
your program.
The instructions for this exercise come in three parts: first comes a general
introduction and background to the lab, and you are expected to read this thoroughly
before you attend your scheduled lab session; the second part is a ‘manual’ for the
library functions you have been provided with, and you should make sure you are
familiar with this as well before turning up; the third and final part is a detailed
description of the individual tasks that comprise the lab. Again it is important that you
read all of this at least once before you turn up for your lab, so that there are no
surprises when you sit down at your machine. (Some of the tasks—such as planning
the mappings between co-ordinate systems—are much easier to figure out on paper
than they are to do when you are sitting in front of a computer.)
Part 1: Introduction
Before your scheduled lab session, you should spend some time reading, in
conjunction with your lecture notes, the following description of the Mandelbrot Set.
It is very important that you do this: the time allocated for this lab assumes you are
ready to start on the programming part of the exercise as soon as you turn up.
Project of C/C++ 2011 Spring, CS, HIT
2
About the Mandelbrot set
The Mandelbrot Set – named after the mathematician Benoit Mandelbrot, who
discovered it on 1st March 1980 – is a graph of a mathematical formula. It is also a
fractal, the name given to shapes that have a property known as ‘self similarity’.
Examining fractals at different levels of detail reveals similar characteristics. A good
example of this is a piece of yummy broccoli: if you divide a head of broccoli into
individual florets, you’ll see that they look pretty much the same as the whole head.
Many natural phenomena such as mountains or coastlines have self-similar properties.
Self-similarity in the natural world, however, has its limits – you can only split a
broccoli floret up a certain number of times before the little bits of green vegetable
you are left with bear no relationship to their original shape. The Mandelbrot Set
however, being a purely mathematical concept, has no such limits, and you can
examine it at ever-increasing levels of detail and it will always look intricate. (In
purely practical terms, the only limit to the level of detail at which you can explore
the Mandelbrot Set is the precision level of the real numbers of your computer.)
In order to complete this exercise, you will need to know a little about the
mathematics of the Mandelbrot Set itself, since you will be writing some code to
calculate it. First, you need to know a little about complex numbers.
Complex numbers
A complex number comprises a pair of values: a real part and an imaginary part.
The real part is an ordinary number, for example, -3. The imaginary part is a real
number multiplied by a special number called i and written, for example, as 2i. An
example of a complex number would be -3 + 2i. The number i was invented to make
it possible to manipulate expressions that involve the square root of negative numbers;
i is defined as being the square root of –1, so i2 is equal to –1, and the square of, (for
example) 3i is –9 (3 * 3 * i * i).
By the way, don’t worry about trying to understand what the square root of a
negative number actually means.
Real numbers can quite easily be represented on a one-dimensional line (called,
not surprisingly, the real number line). Negative numbers are plotted on the left of the
zero origin, and positive numbers are plotted to the right. Complex numbers have two
components (real and imaginary), so need to be plotted on a two-dimensional plane
instead, with the real values along the x axis, and the imaginary values on the y axis,
as we can see in Figure 1. This is called the complex plane.
Project of C/C++ 2011 Spring, CS, HIT
3
Figure 1: The Complex Plane
The mathematics of the Mandelbrot Set
Figure 2 shows a visualization of the Mandelbrot Set.
Figure 2: The Mandelbrot Set
The Mandelbrot Set is a set of complex numbers. To determine whether a given
complex number C belongs to the set or not, we need to perform a simple test on it.
This test involves plugging C into the following equation:
Zn+1 = Zn
2 + C
Here, Zn is another complex number, which starts off as Z0 = 0 + 0i (this is the
complex number equivalent to the real number 0). The above equation is an iterative
equation; in other words, after computing the equation we get a new value of Z, which
we then plug back into the equation, and repeat the process.
To illustrate, let’s look at how this equation behaves, for some value of C (we’ll
choose C = 1.3 + 0.4i, as a random example). Remember we always initialise Z0 to be
Project of C/C++ 2011 Spring, CS, HIT
4
0 + 0i:
Z0 = 0 + 0i
Z1 = Z0
2 + C
= Z0
2 + (1.3 + 0.4i)
= 0 + 1.3 + 0.4i
= 1.3 + 0.4i
Z2 = Z1
2 + (1.3 + 0.4i)
= (1.3 + 0.4i) 2 + (1.3 + 0.4i)
= 1.53 + 1.04i + (1.3 + 0.4i)
= 2.83 + 1.44i
Z3 = Z2
2 + (1.3 + 0.4i)
= 7.2353 + 8.5504i
As you can see, the value of Z changes each time we iterate the function. This
doesn’t seem to be very interesting, but in fact this simple equation behaves in a rather
unexpected way. We can see this, if we examine what happens to the modulus of Z,
after each iteration. The modulus (sometimes also called magnitude, or absolute value)
of a complex number Z = a + ib, is written as |Z|, and is defined as the distance of Z
from the origin (0, 0) of the complex plane. It’s easy to calculate: |Z| = sqrt (a2 + b2
) –
it’s just the Pythagoras rule.
As we iterate the function, a number of things could potentially happen to the
value of |Z|:
1) it could jump around chaotically
2) it could get bigger and bigger without limit
3) it could tend to zero or stabilize at some other constant value
It turns out that it is the particular value of C which is the deciding factor for the
behavior of |Z| (remember, Z always starts off as Z = 0 + 0i).
And this leads to the definition of the Mandelbrot Set: Values of C that cause |Z|
to tend to some fixed value, or to jump around chaotically, are members of the
Mandelbrot Set; values of C that cause |Z| to get bigger and bigger and tend towards
infinity are not members of the Mandelbrot Set.
In fact, when we iterate our equation, it turns out that one of only two specific
things happens to the value of |Z|: it either stays equal to or below 2 forever, or it
eventually becomes greater than 2, and will then continue to tend to infinity. This
might seem a little odd, and indeed it is, but we don’t need to worry about why for the
purposes of this exercise.
In case you’re wondering, in the example above, the successive values of |Z| were
(to 2 decimal places): 0, 1.36, 2.32, and 4.21. So in this case, the complex number C =
1.3 + 0.4i was not a member of the Mandelbrot Set. This may give you a clue as to
why the Mandelbrot Set didn’t become an object of interest until the computer age –
the calculations required are long and tedious to do by hand!
So, now we can turn our attention to visualizing the Mandelbrot Set. All we need
to do is to test enough complex numbers in the complex plane, and for each we shall
note whether it is in the Mandelbrot Set or not. If it is, we shall plot a pixel for it; if it
isn’t, we won’t.
Project of C/C++ 2011 Spring, CS, HIT
5
Part 2: Drawing the Mandelbrot Set
Coordinate systems and pixels
The first thing to note is that the complex plane is a two-dimensional space, so
this will map very conveniently onto a two-dimensional window on our desktop
display.
Further, we can easily find a mapping between every point in our screen window
(we’ll call these points ‘pixels’ for now), and the corresponding complex number in
the complex plane, as Figure 3 shows.
Figure 3: mapping from complex numbers to pixels
In order to display the Mandelbrot Set, we therefore have three main tasks:
1. find some way of drawing to our screen
2. choose a range of complex numbers and to calculate whether they belong to
the Mandelbrot Set or not; the range of values we will choose is the square
region of the complex plane defined by (–2, –2i) to (2, 2i)
3. map between our set of values and the screen co-ordinates
The first of these tasks—that of getting the entire infrastructure in place to create
a window on the screen—turns out to be a fairly complex job, so we have provided
you with a library of functions that simplifies this, called the OpenCV library.
One of your tasks will be to understand how to link your code that you have
written in C with the library we have provided. The main body of this exercise
revolves around writing your own code to evaluate the Mandelbrot Set and to map
your data structures onto the library we have provided in order to make the set appear
on the screen.
You are provided with functions to:
create the window –cvNamedWindow
create image- cvCreateImage
show image in the window-cvShowImage
(0, 0)
(0, 0) (0, 0)
The pixel window, where the
origin is on the top left corner.
The pixel window, where the origin
is the middle of the window.
The complex plane, where
complex numbers live
Pixel (i, j)
Pixel (i, j) Complex number (re, im)
Project of C/C++ 2011 Spring, CS, HIT
6
set the color of the pixel-cvSet2D
save image-cvSaveImage
copy image-cvCloneImage
Using the OpenCV library
Here, we’ll describe each of the data structures, constants and functions OpenCV
have provided you with. You don’t need to understand how these functions actually
work internally – you just need to understand what they do, and how to use them.
First the handy data structures:
typedef struct CvPoint
{
int x;
int y;
}CvPoint;
typedef struct CvScalar
{
double val[4];
}CvScalar;
typedef struct _IplImage
{
int nSize; /* sizeof(IplImage) */
int ID; /* version (=0)*/
int nChannels; /* Most of OpenCV functions support 1,2,3 or 4
channels */
int alphaChannel; /* ignored by OpenCV */
int depth; /* pixel depth in bits: IPL_DEPTH_8U,
IPL_DEPTH_8S, IPL_DEPTH_16S,
IPL_DEPTH_32S, IPL_DEPTH_32F and
IPL_DEPTH_64F are supported */
char colorModel[4]; /* ignored by OpenCV */
char channelSeq[4]; /* ditto */
int dataOrder; /* 0 - interleaved color channels, 1 - separate color
channels. cvCreateImage can only create
interleaved images */
int origin; /* 0 - top-left origin,1 - bottom-left origin
(Windows bitmaps style) */
int align; /* Alignment of image rows (4 or 8).OpenCV
ignores it and uses widthStep instead */
int width; /* image width in pixels */
int height; /* image height in pixels */
Project of C/C++ 2011 Spring, CS, HIT
7
struct _IplROI *roi; /* image ROI. if NULL, the whole image is
selected */
struct _IplImage *maskROI; /* must be NULL */
void *imageId; /* ditto */
struct _IplTileInfo *tileInfo; /* ditto */
int imageSize; /* image data size in bytes
(==image->height*image->widthStep
in case of interleaved data)*/
char *imageData; /* pointer to aligned image data */
int widthStep; /* size of aligned image row in bytes */
int BorderMode[4]; /* ignored by OpenCV */
int BorderConst[4]; /* ditto */
char *imageDataOrigin; /*pointer to very origin of image data (not
necessarily aligned) -needed for correct
deallocation */
}/*here, the items in grey font color will not be used in this work*/
Now the functions:
cvCreateImage
The function cvCreateImage creates the header and allocates data.
IplImage* cvCreateImage (CvSize size, int depth, int channels)
size
Image width and height
depth
Bit depth of image elements. Can be one of:
IPL_DEPTH_8U - unsigned 8-bit integers
IPL_DEPTH_8S - signed 8-bit integers
IPL_DEPTH_16U - unsigned 16-bit integers
IPL_DEPTH_16S - signed 16-bit integers
IPL_DEPTH_32S - signed 32-bit integers
IPL_DEPTH_32F - single precision floating-point numbers
IPL_DEPTH_64F - double precision floating-point numbers
channels
Number of channels per element (pixel).Can be 1, 2, 3 or 4.The channels are
interleaved, for example the usual data layout of a color image is:b0 g0 r0 b1 g1
r1...
Although in general IPL image format can store non-interleaved images as well
and some of OpenCV can process it, this function can create interleaved images
only
cvRectangle
The function cvRectangle draws a rectangle with two opposite corners pt1 and pt2.
void cvRectangle (CvArr*img, CvPoint pt1, CvPoint pt2, CvScalar color,int
thickness=1, int line_type=8, int shift=0 )
img
Project of C/C++ 2011 Spring, CS, HIT
8
Image,
pt1
One of the rectangle vertices
pt2
Opposite rectangle vertex
color
Line color (RGB) or brightness (grayscale image)
Thickness
Thickness of lines that make up the rectangle. Negative values, e.g.
CV_FILLED, make the function to draw a filled rectangle
line_type
Type of the line, see cvLine description
shift
Number of fractional bits in the point coordinates
cvCloneImage
The function cvCloneImage makes a full copy of the image including header, ROI
and data
IplImage* cvCloneImage( const IplImage* image );
image
Original image.
cvNamedWindow
The function cvNamedWindow creates a window which can be used as a
placeholder for images and trackbars. Created windows are referred by their names.
If the window with such a name already exists, the function does nothing.
int cvNamedWindow( const char* name, int flags=CV_WINDOW_AUTOSIZE );
name
Name of the window which is used as window identifier and appears in the
window caption
flags
Flags of the window. Currently the only supported flag is
CV_WINDOW_AUTOSIZE. If it is set, window size is automatically
adjusted to fit the displayed image, while user can not change the window
size manually.
cvShowImage
The function cvShowImage shows the image in the specified window. If the window
was created with CV_WINDOW_AUTOSIZE flag then the image is shown with its
original size, otherwise the image is scaled to fit the window.
void cvShowImage( const char* name, const CvArr* image );
name
Name of the window
image
Image to be shown
cvSaveImage
The function cvSaveImage saves the image to the specified file. The image format is
Project of C/C++ 2011 Spring, CS, HIT
9
chosen depending on the filename extension. Only 8-bit single-channel or
3-channel (with 'BGR' channel order) images can be saved using this function. If
the format, depth or channel order is different, use cvCvtScale and cvCvtColor to
convert it before saving, or use universal cvSave to save the image to XML or YAML
format.
int cvSaveImage( const char* filename, const CvArr* image );
filename
Name of the file
image
Image to be saved
cvDestroyWindow
The function cvDestroyWindow destroys the window with a given name.
void cvDestroyWindow( const char* name );
name
Name of the window to be destroyed
cvReleaseImage
The function cvReleaseImage releases the header and the image data
void cvReleaseImage( IplImage** image );
image
Double pointer to the header of the deallocated image
Part 3: The lab exercise
We’re finally at the point where we can detail your tasks in the laboratory
exercise.
Task 1
Create a file called ‘mandelbrot.c’ or ‘mandelbrot.cpp’ using whichever editor
you prefer. Write and compile yourself a ‘main’ function that prints out the name of
your favorite root vegetable just to be sure that everything is working ok.
Task 2
Add the following function:
int mSetTest(doublec_re, doublec_im)
{
/*your stuff goes here*/
}
This function will take the complex number C, whose real part is c_re, and whose
imaginary part is c_im, and will determine whether or not C is a member of the
Mandelbrot Set. As you will recall from the discussion above, this will involve
Project of C/C++ 2011 Spring, CS, HIT
10
iterating the following equation, where Z0 is defined to be (0 + 0i):
2
n+1 n Z = (Z ) + C
Let’s recall the definition of the Mandelbrot Set given above: if, during all the
function iterations, |Z| stays less than 2.0, then C is in the Mandelbrot Set; but as soon
as |Z| exceeds 2.0, we immediately know that C is not in the Mandelbrot Set.
This immediately leads to a practical programming problem. Suppose we are
testing a particular C that just happens to be a member of the Mandelbrot Set. Then,
no matter how many iterations we do, |Z| will always be less than 2.0 (by definition).
So, should we continue iterating the function forever…? Obviously that would be silly.
What we will do is to make a pragmatic decision, and say that if, after 200 iterations,
|Z| is still less than 2.0, then it’s a pretty good bet that C is a member of the
Mandelbrot set. In such a case, your function should return a value of 0.
But what if a particular C is not in the Mandelbrot Set? In this case, |Z| will soon
exceed 2.0, after which there is no point doing any further iterations. In this case, your
function should return a value which corresponds to the number of iterations
performed before |Z| exceeded 2.0. Of course, this value will always lie between 1 and
200.
Once you have written this function, you must test it on the following values of
C:
C Result
(2.0, 2.0) 1
(0.0, 0.0) 0
(-1.0, -1.0) 3
(1.0, 1.0) 2
Task 3
Now you’re ready to draw the Mandelbrot Set, so you’ll need to link your
program with the OpenCV library we’ve given you:
http://cms.hit.edu.cn >>I Can C You>>"Share Your Code" Event--2>> OpenCV
A. Create an image and show it in a window
In your main function, add the following lines.
You will also need to add the #include directive to the top of the file to get the
IplImage *pImg =
cvCreateImage (/*size*/cvSize (IMAGE_SIZE, IMAGE_SIZE), /*depth*/ 8, /*n
Channels*/3);
cvNamedWindow (/*name of the window*/"mandelbrot", 1);
cvShowImage ("mandbrot", pImg);
cvWaitKey (/*delay*/0);
cvDestroyWindow ("mandlbrot");
cvRelease(&pImg);
Project of C/C++ 2011 Spring, CS, HIT
11
prototype for this function from the header file (cv.h, highgui.h), and you’ll need to
link your compiled executable with the OpenCV library. Compile this program, and
run it. A grey window should appear on the screen. You’ll have to cause the program
to exit by pressing any key (act by cvWaitKey).
B. Mapping from pixels to complex numbers
You’re now going to actually color in the Mandelbrot Set. You will need two
nested ‘for’ loops, one that iterates over ‘x’ dimension pixels and another that iterates
over ‘y’ dimension pixels. For the time being, vary both these values from 0 to
IMAGE_SIZE in both dimensions. Within the loops, you will have to map from
these pixel co-ordinates to the coordinates of the Mandelbrot Set. Remember your
pixel values are being varied between 0 and IMAGE_SIZE, and your Mandelbrot Set
values vary between –2 and +2 in both the real and imaginary dimensions.
C. Color the Mandelbrot Set
Once you’ve written an expression for the mapping, you can plug the real and
imaginary co-ordinates into your mSetTest function and get a value representing
whether the co-ordinate is part of The Set. The library function, cvSet2D (cxcore.h), is
usually used to set the color of a pixel in an image. You can use this function to color
the whole set.
Task 4
You’re now going to start making the program interactive, and you’ll start by
allowing the user to get the coordinate by repeatedly clicking the mouse on a point
// an example of black/white color scheme
CvScalar sca;
if the coordinate of pixel( i,j) in complex plane is in the Mandelbrot Set
{
sca.val[0]=0; //blue
sca.val[1]=0; //green
sca.val[2]=0; //red
cvSet2D(pImg,j,i,sca);
}
else
{
sca.val[0]=255;
sca.val[1]=255;
sca.val[2]=255;
cvSet2D(pImg,j,i,sca);
}
Project of C/C++ 2011 Spring, CS, HIT
12
that is to become the new origin. Remember, we are currently drawing the set
centered on the imaginary number (0 + 0i) … in this task you are allowing the user to
choose a new point to centre our drawing around.
At first, you have to assign the callback function on_mouse which will be used to
deal with the mouse message from our system. In you program, you don’t have to call
on_mouse function, and it will be called by the system.
The on_mouse function will wait for the user to click on a point in the drawing
window, and will get the position of this point via x and y in pixel window
co-ordinates (i.e. NOT in Mandelbrot Set co-ordinates.)
You have to work out what these values mean in Mandelbrot co-ordinates (this is
the inverse of the calculation you did previously to turn screen co-ordinates into Set
co-ordinates of course!) and use these new values as the new centre of your plot.
Task 5
The final bit of interactivity is to allow the user to zoom in on their favorite part
of the Set to see that it really is a fractal that goes on forever and ever (or, at least,
until our floating point calculations run out of precision.). It allows the user to draw a
square box on the Mandelbrot Set, and returns the top left and bottom right
co-ordinates of that box.
Your program works by allowing the user to click a point on the screen that is to
be one corner of the square and then—whilst holding down the mouse button—to
drag out a box. The function returns when the user lets go of the mouse button.
Remember, all that you are doing is selecting a new origin around which to centre
your calls to mSetTest, and now also changing the distance between the values you
are passing to mSetTest.
cvSetMouseCallback("mandelbrot",on_mouse,0); // put where you want to deal with the
//mouse event
void on_mouse( int event, int x, int y, int flags,void* param)
{
// you have to implement this function
switch (event)
{
case CV_EVENT_RBUTTONDBLCLK:
break;
case CV_EVENT_LBUTTONDOWN:
break;
case CV_EVENT_MOUSEMOVE:
if((flags & CV_EVENT_FLAG_LBUTTON))
{}
break;
}
}
Project of C/C++ 2011 Spring, CS, HIT
13
*Task 6(optional)
You’ll notice that some parts of the Set aren’t actually very interesting… there are
big smooth areas, that if you zoom into them turn into… well, big smooth areas. The
real beauty of the set lies in the lovely intricate crinkly bits around the edges.
Automate the process of finding these more chaotic (crinkly!) bits, and ‘steer’
your zoom function so that it continuously selects an interesting area and zooms
slowly into it. Very hypnotic. Also, very hard.
Marking Scheme
The project is an optional one for you. Once you decide to do it, please do it
entirely (Task 6 may not included). And we may have your code or demo being
showed in due course and proper manner.
This lab is designed to get tougher as it goes on. There is very little room for
‘subjectivity’ in the marking scheme… things either work (in which case you get a
mark), or they don’t (in which case you don’t get a mark!)
The one subjective mark is given for ‘good coding style’. Any decent, consistent,
clear coding style is fine, with any good choices of variable names – we are not
looking to penalized you unnecessarily here (though you wont get this mark if your
code is a mess, if any of the variables have dreadful names, or if you have made
something work but in a completely mad way.)
The following mark rules are for your information.
100 marks for must-do + no marks for optional
?10
marks for getting the mSetTest function to work [Task 2]
?10
marks for linking with the library and getting a window to appear [Task 3-A]
?10
marks for drawing the Set in white and black [Task 3-B]
?15
marks for coloring the Mandelbrot Set [Task 3-C]
?15
marks for response the mouse event [Task 4-A]
???
marks for redrawing the Set with the new centre designated by mouse [Task 4-B]
?15
marks for getting the zoom to work [Task 5]
?10
marks for decent coding style, good variable names etc.
?optional:
the automated interesting-area zoom function [Task 6]
Acknowledgment:
The original script of the project is kindly provided by Dr. Aphrodite Galata, Manchester,
U.K.

版权所有:留学生编程辅导网 2021,All Rights Reserved 联系方式:QQ:99515681 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。