Digital Geometry

Digital_Geometry.rar

Intro to Topology

Planar Machines' web site. An invitation to Topology.

Limits.h

#define CHAR_BIT 8 /* number of bits in a char */
#define SCHAR_MIN (-128) /* minimum signed char value */
#define SCHAR_MAX 127 /* maximum signed char value */
#define UCHAR_MAX 0xff /* maximum unsigned char value */

#ifndef _CHAR_UNSIGNED
#define CHAR_MIN SCHAR_MIN /* mimimum char value */
#define CHAR_MAX SCHAR_MAX /* maximum char value */
#else
#define CHAR_MIN 0
#define CHAR_MAX UCHAR_MAX
#endif /* _CHAR_UNSIGNED */

#define MB_LEN_MAX 5 /* max. # bytes in multibyte char */
#define SHRT_MIN (-32768) /* minimum (signed) short value */
#define SHRT_MAX 32767 /* maximum (signed) short value */
#define USHRT_MAX 0xffff /* maximum unsigned short value */
#define INT_MIN (-2147483647 - 1) /* minimum (signed) int value */
#define INT_MAX 2147483647 /* maximum (signed) int value */
#define UINT_MAX 0xffffffff /* maximum unsigned int value */
#define LONG_MIN (-2147483647L - 1) /* minimum (signed) long value */
#define LONG_MAX 2147483647L /* maximum (signed) long value */
#define ULONG_MAX 0xffffffffUL /* maximum unsigned long value */
#define LLONG_MAX 9223372036854775807i64 /* maximum signed long long int value */
#define LLONG_MIN (-9223372036854775807i64 - 1) /* minimum signed long long int value */
#define ULLONG_MAX 0xffffffffffffffffui64 /* maximum unsigned long long int value */

#if _INTEGRAL_MAX_BITS >= 8
#define _I8_MIN (-127i8 - 1) /* minimum signed 8 bit value */
#define _I8_MAX 127i8 /* maximum signed 8 bit value */
#define _UI8_MAX 0xffui8 /* maximum unsigned 8 bit value */
#endif

#if _INTEGRAL_MAX_BITS >= 16
#define _I16_MIN (-32767i16 - 1) /* minimum signed 16 bit value */
#define _I16_MAX 32767i16 /* maximum signed 16 bit value */
#define _UI16_MAX 0xffffui16 /* maximum unsigned 16 bit value */
#endif

#if _INTEGRAL_MAX_BITS >= 32
#define _I32_MIN (-2147483647i32 - 1) /* minimum signed 32 bit value */
#define _I32_MAX 2147483647i32 /* maximum signed 32 bit value */
#define _UI32_MAX 0xffffffffui32 /* maximum unsigned 32 bit value */
#endif

#if _INTEGRAL_MAX_BITS >= 64
/* minimum signed 64 bit value */
#define _I64_MIN (-9223372036854775807i64 - 1)
/* maximum signed 64 bit value */
#define _I64_MAX 9223372036854775807i64
/* maximum unsigned 64 bit value */
#define _UI64_MAX 0xffffffffffffffffui64
#endif

#if _INTEGRAL_MAX_BITS >= 128
/* minimum signed 128 bit value */
#define _I128_MIN (-170141183460469231731687303715884105727i128 - 1)
/* maximum signed 128 bit value */
#define _I128_MAX 170141183460469231731687303715884105727i128
/* maximum unsigned 128 bit value */
#define _UI128_MAX 0xffffffffffffffffffffffffffffffffui128
#endif

#ifndef SIZE_MAX
#ifdef _WIN64
#define SIZE_MAX _UI64_MAX
#else
#define SIZE_MAX UINT_MAX
#endif
#endif

A Useful site to understanding B-Spline Curve

Spline Curves and Surfaces
Introduction
This tutorial is designed to help students learn about spline curves and surfaces. It is not designed to be a full lesson; it is more suited to those who have already learnt the basics and would like to reinforce their knowledge.
The tutorial consists of a combination of writing, java applets, VRML worlds and links to other pages. These links are there because the descriptions given elsewhere are likely to be a great help to those learning this material from scratch, as I only give a brief account of the mathematics involved here. The java applets are essentially interactive diagrams. They are there for you to learn by experience, so do experiment!
A note about viewing these pages
In order to see diagrams as large as possible, please maximise your browser window. All of the diagrams on these pages are sized in relation to your window size; if this is too small, the diagrams will be too. It should be possible to resize the window during browsing these pages, but I believe some versions of Netscape do not resize the applets correctly, so choose your window size before you move on.
For some basic notes on how to use the Java applets see the introduction to spline curves. For notes on how to use the VRML worlds see the surface introduction.
Table of Contents
1. Introduction to spline curves
2. Explicit curves
3. Parametric curves
4. Bezier curves
5. B-Spline curves
6. Introduction to surfaces
7. Bezier surfaces
8. B-Spline surfaces
This tutorial was written as an individual project, a required part of the MSc Computing Science degree at Imperial College, by Andy Salter.

Error with MSVCR80.DLL !!!!!!!!!!!!

Encoutered this error, I had to spend 4 hours to fix it. Until now, I have never understand how the "magic codes" could resolved this error. ^_^, but at least we'll never get stuck in it. Oh my god, Thanks!

You must read following articles:



Concretely, I cut & paste the vital code here:

Error Message
This application has failed to start because MSVCR80.dll was not found. Re-installing the application may fix this problem.


Typically this error occurs because you are mixing retail and debug components. A very common scenario is a debug build of a application which is pulling in a retail version of a static library. The scenario could be the exact reverse and the error message in this case would reference msvcr80d.dll

Solution
This can be worked around by adding reference to retail CRT in the application manifest manually. Or by adding the following to a header.

#pragma comment(linker, "\"/manifestdependency:type='Win32' name='Microsoft.VC80.CRT' version='8.0.50608.0' processorArchitecture='X86' publicKeyToken='1fc8b3b9a1e18e3b' language='*'\"")

Note: Proceed with caution when providing this solution.

Bless you.

Hausdorff distance between convex polygons

Normand Grégoire and Mikael Bouillot

1. Introduction 2. What is Hausdorff distance ? 3. Computing Hausdorff distance 3.1 Assumptions 3.2 Lemmas 3.3 Algorithm 3.4 Complexity 3.5 Interactive applet 4. Application examples Glossary References

---

Web project presented to Mr. Godfried Toussaint for the course CS 507 Computational Geometry McGill University, fall 1998

Fractals and the Fractal Dimension

Fractals and the Fractal Dimension

Mandelbrot and Nature

"Clouds are not spheres, mountains are not cones, coastlines are not circles, and bark is not smooth, nor does lightning travel in a straight line."(Mandelbrot, 1983).

The Concept of Dimension

So far we have used "dimension" in two senses:

• The three dimensions of Euclidean space (D=1,2,3)
• The number of variables in a dynamic system

Fractals, which are irregular geometric objects, require a third meaning:

The Hausdorff Dimension

If we take an object residing in Euclidean dimension D and reduce its linear size by 1/r in each spatial direction, its measure (length, area, or volume) would increase to N=r^D times the original. This is pictured in the next figure.

We consider N=r^D, take the log of both sides, and get log(N) = D log(r). If we solve for D. D = log(N)/log(r) The point: examined this way, D need not be an integer, as it is in Euclidean geometry. It could be a fraction, as it is in fractal geometry. This generalized treatment of dimension is named after the German mathematician, Felix Hausdorff. It has proved useful for describing natural objects and for evaluating trajectories of dynamic systems.

The length of a coastline

Mandelbrot began his treatise on fractal geometry by considering the question: "How long is the coast of Britain?" The coastline is irregular, so a measure with a straight ruler, as in the next figure, provides an estimate. The estimated length, L, equals the length of the ruler, s, multiplied by the N, the number of such rulers needed to cover the measured object. In the next figure we measure a part of the coastline twice, the ruler on the right is half that used on the left.

Measuring the length of a coastline using rulers of varying lengths.

But the estimate on the right is longer. If the the scale on the left is one, we have six units, but halving the unit gives us 15 rulers (L=7.5), not 12 (L=6). If we halved the scale again, we would get a similar result, a longer estimate of L. In general, as the ruler gets diminishingly small, the length gets infinitely large. The concept of length, begins to make little sense.

The "Richardson Effect"

Lewis Fry Richardson first noted the regularity between the length of national boundaries and scale size. As shown next, the relation between length estimate and length of scale is linear on a log-log plot.

The Richardson Effect.

Mandelbrot assigned the term (1-D) to the slope, so the functions are:
log[L(s)] = (1-D)log(s) + b where D is the Fractal Dimension.
For Great Britain, 1 - D = -.24, approximately. D = 1-(-.24) = 1.24, a fractional value.The coastline of South Africa is very smooth, virtually an arc of a circle. The slope estimated above is very near zero. D = 1-0 = 1. This makes sense because the coastline is very nearly a regular Euclidean object, a line, which has dimensionality of one. In general, the "rougher' the line, the steeper the slope, the larger the fractal dimension.

Examples of geometric objects with non-integer dimensions

Koch Curve

We begin with a straight line of length 1, called the initiator. We then remove the middle third of the line, and replace it with two lines that each have the same length (1/3) as the remaining lines on each side. This new form is called the generator, because it specifies a rule that is used to generate a new form.

The Initiator and Generator for constructing the Koch Curve.

The rule says to take each line and replace it with four lines, each one-third the length of the original.

Level 2 in the construction of the Koch Curve.

Level 3 in the construction of the Koch Curve.

We do this iteratively ... without end. The Koch Curve.

What is the length of the Koch curve?

The length of the curve increases with each iteration. It has infinite length. But if we treat the Koch curve as we did the coastline, ...

The relation between log(L(s)) and log(s) for the Koch curve ...

we find its fractal dimension to be 1.26. The same result obtained from D = log(N)/log(r) D = log(4)/log(3) = 1.26.

Cantor Dust

Iteratively removing the middle third of an initiating straight line, as in the Koch curve, ...

Initiator and Generator for constructing Cantor Dust. ...

this time without replacing the gap...

Levels 2, 3, and 4 in the construction of Cantor Dust.

Calculating the dimension ... D = log(N)/log(r) D = log(2)/log(3) = .63 We have an object with dimensionality less than one, between a point (dimensionality of zero and a line (dimensionality 1).

Sierpinski Triangle

We start with an equilateral triangle, connect the mid-points of the three sides and remove the resulting inner triangle.

Constructing the Sierpinski Triangle.

Iterating the first step.

Constructing the Sierpinski Triangle.

The Sierpinski Triangle.

Calculating the dimension... D = log(N)/log(r) = log(3)/log(2) = 1.585. This time we get a value between 1 and 2.

The dimensionality of a strange attractor

1. The trajectory of a strange attractor cannot intersect with itself. (Why?)
2. Nearby trajectories diverge exponentially. (Why?)
3. But the attractor is bounded to the phase space.
4. The trajectory does not fill the phase space.

A strange attractor is a fractal, and its fractal dimension is less than the dimensions of its phase space.

Self-similarity

An important (defining) property of a fractal is self-similarity, which refers to an infinite nesting of structure on all scales. Strict self- similarity refers to a characteristic of a form exhibited when a substructure resembles a superstructure in the same form.

Mandelbrot Set

Found by iterating
z_n+1 = z_n² + c.
where z is a complex number. z₀=0.
For different values of c, the trajectories either: stay near the origin, or "escape".
The Mandelbrot set is the set of points that are not in the Escape Set.

The Mandelbrot set. The points in the set are painted black.

The Escape Set differs in rate of escape, graphically depicted with different colors or altitudes ...

Constructed using the computer program "The Beauty of Fractal Lab", by Thomas Eberhardt.

So, what is a fractal?

An irregular geometric object with an infinite nesting of structure at all scales.

Why do we care about fractals?

• Natural objects are fractals.
• Chaotic trajectories (strange attractors) are fractals.
• Assessing the fractal properties of an observed time series is informative.

Next Section: Nonlinear Statistical Tools