Skip to content
/ curve-tracing Public

Tracing curve on 2D plane = drawing curve on complex (2D) plane. Curve is a field line or equipotential line of potential scalar field.

License

GPL-3.0 license
3 stars 0 forks Branches Tags Activity
Star
Notifications You must be signed in to change notification settings

adammaj1/curve-tracing

BranchesTags

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

39 Commits
images
images
 
 
src
src
 
 
LICENSE
LICENSE
 
 
README.md
README.md
 
 

Repository files navigation

2D ( time independent) scalar field ( potential). Create vector field and draw field lines and equipotential lines

TOC

equipotentials

Exterior is coloured with potential ( grayscale)

p = log(potential)/K;
color = 255* (1+cos(TwoPi*p))/2.0;

Exterior is white with black equipotential curves

Boundary using noise detection

double BoundaryMeasure = 1.15; // higher value = thinner boundary
// FindBoundary
if (NoiseMeasure> BoundaryMeasure) A[i] = 255 ;	// white

Noise pixels

double NoiseMeasureThreshold = 0.045; // arbitrary for c = 0.365000000000000  +0.000000000000000 i    period = 0 
//  FindNoisyPixels
if (NoiseMeasure> NoiseMeasureThreshold) A[i] = 255 ;	// white

field lines = external rays

here field lines are external rays

  • do not cross with each other but 2 or more lines may land on the same point ( root or Misiurewicz point)
  • are perpendicular ( normal) to equipotential lines = are gradient lines of potential ( scalar field)

Text output of the program:

memory is OK 

real	0m28,965s
user	3m47,483s
sys	0m0,092s

render image = compute and write image data bytes to the array 
File 10_89990.pgm saved. 
ClearExterior =  make exterior solid color = white
 exterior p = 0.751188 

draw equipotential curve thru point c = (0.9000000000000000; 0.0000000000000000) pixel = (1916, 1000)
 	start point
	for c = (0.900000;0.000000)	noise measure = 0.0025952006903814	potential = 0.9901006463279854
	c is inside the array : iy = 1916 iy = 1000	and outside M set
	end point	ix = 1916 iy = 1000 i = 2001916 potential = 0.9901033608952807
	curve is closed = stop ( good) after 4357 steps (pixels)


draw equipotential curve thru point c = (0.7000000000000000; 0.0000000000000000) pixel = (1805, 1000)
 	start point
	for c = (0.700000;0.000000)	noise measure = 0.0045160797467720	potential = 0.5989907665960282
	c is inside the array : iy = 1805 iy = 1000	and outside M set
	end point	ix = 1805 iy = 1000 i = 2001805 potential = 0.5989911428328348
	curve is closed = stop ( good) after 3825 steps (pixels)


draw equipotential curve thru point c = (0.5000000000000000; 0.0000000000000000) pixel = (1694, 1000)
 	start point
	for c = (0.500000;0.000000)	noise measure = 0.0111195774508909	potential = 0.2128012374973248
	c is inside the array : iy = 1694 iy = 1000	and outside M set
	end point	ix = 1694 iy = 1000 i = 2001694 potential = 0.2127903458916913
	curve is closed = stop ( good) after 3687 steps (pixels)


draw equipotential curve thru point c = (0.4000000000000000; 0.0000000000000000) pixel = (1638, 1000)
 	start point
	for c = (0.400000;0.000000)	noise measure = 0.0244119823222931	potential = 0.0632189280903892
	c is inside the array : iy = 1638 iy = 1000	and outside M set
	end point	ix = 1638 iy = 1000 i = 2001638 potential = 0.0631906592052049
	curve is closed = stop ( good) after 4125 steps (pixels)

File 10_89980.pgm saved. 
Find boundary of Mandelbrot set using  noise measure
File 10_89970.pgm saved. 
Find noisy pixels
File 10_89960.pgm saved. 
for c = (0.000000;0.000000)	noise measure = 0.0000000000000000	potential = 0.0000000000000000
for c = (0.100000;0.000000)	noise measure = 0.0000000000000000	potential = 0.0000000000000000
for c = (0.200000;0.000000)	noise measure = 0.0000000000000000	potential = 0.0000000000000000
for c = (0.250000;0.000000)	noise measure = 0.2500000000000000	potential = 0.0000000000000000
for c = (0.260000;0.000000)	noise measure = 3.1457717601949291	potential = 0.0000000019934531
for c = (0.270000;0.000000)	noise measure = 0.5572597205697883	potential = 0.0000044162911707
for c = (0.280000;0.000000)	noise measure = 0.3078640888246843	potential = 0.0000587486278177
for c = (0.290000;0.000000)	noise measure = 0.1872334952074938	potential = 0.0003708182242248
for c = (0.300000;0.000000)	noise measure = 0.1290122547411083	potential = 0.0012438403001236
for c = (0.350000;0.000000)	noise measure = 0.0457918910257952	potential = 0.0183838747379665
for c = (0.400000;0.000000)	noise measure = 0.0244119823222931	potential = 0.0632189280903892
for c = (0.450000;0.000000)	noise measure = 0.0156374406145566	potential = 0.1305368896713344
for c = (0.500000;0.000000)	noise measure = 0.0111195774508909	potential = 0.2128012374973248
for c = (0.600000;0.000000)	noise measure = 0.0066430404569894	potential = 0.3984187631443595
for c = (0.700000;0.000000)	noise measure = 0.0045160797467720	potential = 0.5989907665960282
for c = (0.800000;0.000000)	noise measure = 0.0033359942064616	potential = 0.7958924429230689
for c = (0.900000;0.000000)	noise measure = 0.0025952006903814	potential = 0.9901006463279854
for c = (1.000000;0.000000)	noise measure = 0.0020908718498594	potential = 1.1743374869011141


Parameter plane with Mandelbrot set
corners: CxMin = -2.550000	CxMax = 1.050000	 CyMin = -1.800000	 CyMax 1.800000
corners: ixMin = 0	ixMax = 1999	 iyMin = 0	 iyMax 1999
exterior = CPM/M
IterationMax = 90000
EscapeRadius = 10
iPixelRadius = ixMax* 0.002 = 1 so big pixel = 4 (small) pixels

Why real time is lower then user time ?

cases

  • dimension : 2D / 3D / ...
  • input
    • trace a curve in the array of precomputed values ( read value of new point from the array). Array = image
    • trace a curve in complex 2D plane ( compute each point)
  • curve types
  • grid
    • structured / unstructured
    • quadratic / triangular ( Coxeter-Freudenthal decomposition (triangulation))
  • pixel connectivity
  • stoping criteria
    • boundary of the Grid ( image)
    • maximal curve length
    • Maximum compute time
  • trace
    • forward / backward or clockwise/counterclockwise
    • how many seed points
    • fixed step / change
    • algorithm

algorithm

Input:

  • plane (parameter plane or dynamic plane)
  • scalar function ( potential)
  • vector function

Steps:

  • create scalar field using scalar function ( potential)
  • create vector field from scalar field using vector function ( gradient of the potential)
  • compute/draw :
    • filed lines ( stream lines )
    • contour lines ( [[Fractals/Iterations_in_the_complex_plane/equipotetential|equipotential lines]] )
    • map whole field using Line Integral Convolution (LIC)

dictionary

tracing a curve means compute successive points on the curve, one by one, until stopping criteria are met

graph TD
A[Start point] --> B(Compute next point)
B --> C{meet stop criteria ? }
C --> |No|B
C -->|Yes| D[End]
Loading

Tracing a curve on the triangular grid
Tracing a curve on the triangular grid
Image by Michael E. Henderson

"scanning means to check every pixel". Other names : detection, extraction

Gradient

  • The gradient of a scalar field is a vector that represents the magnitude and the direction of the greatest increase rate of the field

code

in other repositories

links

see also

Recursive subdivision

  • The process of subdividing an object (either geometric object, or a data structure) recursively until some criteria is met.

Image noise

Feature detection

boundary scaning

boundary tracing

contour tracing

code

Contour scanning or edge detection

streamline tracing

field lines

Visualization of Algebraic Curves - curve sketching

numerical differentiation = numerically computing the gradient of a field

gradient = "direction and rate of fastest increase". If at a point p, the gradient of a function of several variables is not the zero vector

  • the direction of the gradient is the direction of fastest increase of the function at p
  • its magnitude is the rate of increase in that direction

discrete differential geometry

1D

In 1D case derivative of the function f at point x gives the slope of the tangent line at the point x

$ f'(x) = \lim_{h\to0} \frac{f(x+h) - f(x)}{h} = \tan (\theta)$

It is aproximated by the maximal finite differnce:

$f'(x) \approx \max \lbrace \frac{f(x+h) - f(x)}{h} \rbrace$

2D

In 2D case gradient (generalization of the derivative) of function f at point (x,y) gives the slope of the plane (flat surface) tangent to the 3D surface z = f(x,y)

FED

Finite-Difference Method = FDM

$\frac{f(x_{m+1}, y_n) - f(x_{m-1}, y_n)}{2h_x} , \frac{f(xm, yn+1) − f(xm, yn−1)}{2h_y}$

Example code : "gradient direction computation based on image brightness. I've made a matrix bright[width][height] containing brightness values for every pixel of the image"

	// https://stackoverflow.com/questions/4003615/gradient-direction-computation
   double grad_x(int x,int y){
    	if(x==width-1 || x==0) return bright[x][y];
    	return bright[x+1][y]-bright[x-1][y];
    }
    double grad_y(int x,int y){
    	if(y==height-1 || y==0) return bright[x][y];
    	return bright[x][y+1]-bright[x][y-1];
    }

checking n points on the circle around center = n-th order method

Different outputs of numerical gradient function:

  • angle of the gradient vector (and the radius )
  • point directed by the gradient vector

Modifications:

  • Adaptive step size

Edge Handling

The corner cases are a problem because you don't have enough data to calculate a gradient in the same way as the other pixels. One way to deal with them is to simply not calculate the corner cases and live with a slightly smaller image.

If this is not an option you can also extrapolate the missing data. If you assume that the gradient changes smoothly it works like this:

In your x-gradient calculations you may have calculated the derivate A for pixel 1 and B for pixel 2. If you want to extrapolate a value for pixel 0 (the corner case) the value a-(b-a) could be used.

pixel1: gradient = 100 pixel2: gradient = 80

extrapolate using a-(b-a):

pixel0: gradient = 100 - (80-100)) = 120

Links:

Methods

Key words

technical notes

GitLab uses:

git ( gitlab)

cd existing_folder
git init
git remote add origin git@gitlab.com:adammajewski/curve-tracing.git
git add .
git commit -m "Initial commit"
git push -u origin master

Subdirectory

mkdir images
git add *.png
git mv  *.png ./images
git commit -m "move"
git push -u origin master

then link the images:

![](./images/n.png "description") 

gitm mv -f

Local repo : ~/c/mandel/p_e_angle/trace_last/test5

About

Tracing curve on 2D plane = drawing curve on complex (2D) plane. Curve is a field line or equipotential line of potential scalar field.

Topics

c discrete-geometry curve-tracing digital-topology

Resources

Readme

License

GPL-3.0 license
Activity

Stars

3 stars

Watchers

2 watching

Forks

0 forks
Report repository

Releases

No releases published

Packages

No packages published

Languages