An Efficient Algorithm to Generate Grids Using a Modified Transformation Method

Student: Yunseo Jeong
Table: COMP1904
Experimentation location: Home
Regulated Research (Form 1c): No
Project continuation (Form 7): No

Display board image not available

Abstract:

Many combinatorial mathematicians have studied the patterns of SFCs(Space Filling Curves. Also many algorithms about those patterns have been developed. Peano, Cantor, and Hilbert proposed a geometric generation principle for the construction of the Space Filling Curves.
Basic building block of the curves is an open square formed by connected lines.
A complex process made by the mathematicians needs to be analyzed to simplify the procedure recursively converting each point on 1 dimensional domain to coordinate values on 2 dimensional domain. Thereafter, a simplified and efficient recursive procedure can be employed for a smaller version of the original open square on 2 dimensional domain to perform filling out the whole domain. The relationship between points on a line segment and points in a square is displayed by the SFCs, which shows the mapping between those points.
Based on the studies of the SFCs, a new efficient alignment or algorithm can be formed to create different grids, patterns and designs by using unconventional mathematical and computational SFC methods.

Grids developed using the presented method can be applied to develop a digital image processing, numerical finite element methods, combinatorial optimization and solar cell engineering(grid generation).

Bibliography/Citations:

1. Space-Filling Curves (Springer-Verlag), Sagan, Hans (1994), ISBN-13: 978-0387942650

2. Cannon, James W.; Thurston, William P. "Group invariant Peano curves", Geometry & Topology, 

3. Mandelbrot, B. B. "Ch. 7: Harnessing the Peano Monster Curves"The Fractal Geometry of Nature, W. H. Freeman.

4. Peano, G. (1890), "Sur une courbe, qui remplit toute une aire plane", Mathematische Annalen (in French), 36 (1): 157–160, 

5. marcin-chwedczuk.github.io/iterative-algorithm-for-drawing-hilbert-curve

6. www4.ncsu.edu/~njrose/pdfFiles/HilbertCurve.pdf

 

 

 

 

 

 


Additional Project Information

Project website: -- No project website --
Project web pages: -- No webpages provided --
Additional Resources: -- No resources provided --
Project files:
Project files
 

Research Plan:

First, we define [x,y] as order(n) that shows the vector coordinates[x1, x2, x3, ... ] and [y1, y2, y3, ...] of the points on the n-th order of a curve on the 2-D domain. The lines of each of the small squares are then converted to even smaller squares, and so on. After second iterations, we can have four smaller separate squares, and the vertices of each square are connected to form the next pattern formed by a single continuous line. 

To plot output, for example to see the 5th order curve, smaller versions of the original open square undergo 4 iterations. A complex pattern is made by the presented procedure recursively converting each line to a smaller version of the original open square. 

Finally, the mathematical and computational iteration fill out a two dimensional domain. To find the level or quality of SFC, an accurate distribution of black and white color pixels is found by the Histogram. Using a simplified algorithm, create subintervals that can be mapped continuously onto the sub-squares using mathematical and computational analysis. Using pattern iterations, this procedure introduces alternative recursive concepts on SFCs, defining a new sequence of functions f(n):[0,1]→[0,1]^2 that converges to a surjective function.

 

 

 

Questions and Answers

1. What was the major objective of your project and what was your plan to achieve it? 

       a. Was that goal the result of any specific situation, experience, or problem you encountered?  

       b. Were you trying to solve a problem, answer a question, or test a hypothesis?

 

--> Answers to (a) and (b)

The objective of this research project is developing an alternative method that can be efficiently used in grid generation or Space Filling Curve analysis, which can be applied to engineering, digital image processing(DIP), and commercial design fields. 

Compared to other SFC methods, such as Peano and Hilbert curves, the presented research method showed efficiency in computer running time. Using simplified complex numbers and mathematical notations, less operations such as less matrix multiplications were observed to create unconventional images.

 

 

2. What were the major tasks you had to perform in order to complete your project?

       a. For teams, describe what each member worked on.

--> 

First I have studied a few algorithms about those patterns suggested by Peano, Cantor, and Hilbert who proposed a geometric generation principle for the construction of the Space Filling Curves.  And constructed the basic building block of the curves with an open square formed by connected lines using computer programming.

I have tried to study to find an alternative way and procedure: recursively converting each point on 1 dimensional domain to coordinate values on 2 dimensional domain. Thereafter, a simplified and efficient recursive procedure can be employed for a smaller version of the original open square on 2 dimensional domain to perform filling out the whole domain.

 

3. What is new or novel about your project?

       a. Is there some aspect of your project's objective, or how you achieved it that you haven't done before?

       b. Is your project's objective, or the way you implemented it, different from anything you have seen?

       c. If you believe your work to be unique in some way, what research have you done to confirm that it is?

--> Answers to (a), (b) and (c):

It is confirmed that the regular space-filling curves such as the Hilbert curves never self-intersect. The curves completely covered a rectangular region of the plane if the recursion is infinite.  The way they fill the region, however, was entirely decided by their elemental shape and the recursion rule. In a section in this project, a descriptive and computational experiment to find new curves that do not self-intersect was experimented by adjusting the widths and other dimensions which are not even causing a self-intersecting curve.

Finally, 6 different cases(up to ”Curve With Slight Intersect And Incomplete Filling the Space”) were all experimented and compared to each other for their performances: modified curves forming self-intersect, no self-intersect, with/without forming SFC, etc. are all developed and tested.  

Also the data showed that the proposed curve analogues would completely cover a rectangular region of the plane if the recursion increases. In this project, a regular space-filling curve than never self-intersects was set as the control target.

 

4. What was the most challenging part of completing your project?

      a. What problems did you encounter, and how did you overcome them?

      b. What did you learn from overcoming these problems?

--> Answers to (a) and (b) :

Since the way they fill the region was entirely decided by their elemental shape and the recursion rule, a descriptive and computational experiment to find new curves that do not self-intersect was the most challengeable part.

I learned that there are other dimensions available which are not even causing a self-intersecting curve through computational experiment by adjusting the widths and height of the initial geometry.

 

5. If you were going to do this project again, are there any things you would you do differently the next time?

--> Besides the 6 different cases I have tried, ”Curve With More Intersect And Incomplete Filling the Space” can be experimented and compared to each other for their performances: modified curves forming self-intersect, no self-intersect, with/without forming SFC, etc.   

6. Did working on this project give you any ideas for other projects? 

--> We can extend the current theory, SFC, to apply to DIP(digital image processing) combinatorial optimization and solar cell engineering such as grid generation.
 

7. How did COVID-19 affect the completion of your project?

I understand the COVID-19 has severely damaged social structure and  parts of the economy, especially those who own small businesses and were not allowed by law to stay open. For the research project, many types of research are based on wet lab and experimental research, social distancing and travel restrictions have led to problems research activities as well. Fortunately, my project was not affected by the situation since my research was about using computer programming and developing algorithms.