An Efficient Algorithm to Generate Grids Using a Modified Transformation Method
Abstract:
Studies on the design patterns and rendering techniques require adequate computational or statistical algorithms to develop the images. Design patterns are useful since they can be reusable in the commonly occurring problems in industrial and computer design. Due to the iterative nature of product design progression in the modern User Experience Design process, the refined simple units and terms with fractal geometry are essential.To make this recursion technique possible to solve complex and diverse design or space-filling problems, a concise program was developed and used in this project. Using the rotations and translations of the proposed starters, algorithmically and path-efficient codes were used. The presented alternative curves were able to generate diverse conventional space-filling curves as well as non-space-filling curves.
Bibliography/Citations:
1. D. Hilbert: Über die stetige Abbildung einer Linie auf ein Flächenstück. Mathematische Annalen 38 (1891), 459–460.
2. G.Peano: Sur une courbe, qui remplit toute une aire plane. Mathematische Annalen36 (1890), 157–160.
3. Bourges, Pascale. "Chapitre 1: fractales", Fractales et chaos. Accessed: 9 February 2019.
4. Moon, B.; Jagadish, H.V.; Faloutsos, C.; Saltz, J.H. (2001), "Analysis of the clustering properties of the Hilbert space-filling curve", IEEE Transactions on Knowledge and Data Engineering, 13 (1): 124–141, CiteSeerX 10.1.1.552.6697, doi:10.1109/69.908985.
5. "Mapping the whole internet with Hilbert curves". blog.benjojo.co.uk. Retrieved 2021-01-02.
6. Thiadmer Riemersma (1998-12-01). "A Balanced Dithering Technique". C/C++ User's Journal. Dr. Dobb's.
7. I. Kamel, C. Faloutsos, Hilbert R-tree: An improved R-tree using fractals, in: Proceedings of the 20th International Conference on Very Large Data Bases, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1994, pp. 500–509.
8. Eavis, T.; Cueva, D. (2007). A Hilbert space compression architecture for data warehouse environments. Lecture Notes in Computer Science. 4654. pp. 1–12. doi:10.1007/978-3-540-74553-2_1. ISBN 978-3-540-74552-5.
9. Lemire, Daniel; Kaser, Owen (2011). "Reordering Columns for Smaller Indexes". Information Sciences. 181 (12): 2550–2570. arXiv:0909.1346. doi:10.1016/j.ins.2011.02.002. S2CID 15253857.
10. A. Ansari and A. Fineberg. Image data compression and ordering using peano scan and lot. IEEE Transactions on Consumer Electronics, 38(3):436–445, August 1992.
11. T. Cormen, C.E. Leiserson, and R.L. Rivest. Introduction to Algorithms. McGraw-Hill book Company, 1990. submitted to EUROGRAPHICS 2000.
Additional Project Information
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.