This is a brief research project during my Bachelor graduate design. I worked on several derivatives of Binary Tree algorithm, which was implemented to generate grid system of diversity for my project “GAP+”(https://yufanxie.com/gap/). This research well covered several controlling methods for binary system, including the model of “K-D Tree”.
1. Simple Binary Tree
- Setting area for division
- Computing ratio of dimension
- Divide along short axis on long axis
- Restore the divided results in two nodes of structure(Left is0, and right is 1).
- Back to *Step1
2. Ratio Based
In stage 2, the the percentage and location of division is defined as a variable – by which we can control the ratio of left branch to right branch. The form will be largely effected by the ratio, showing different density and shape varying from derivatives of standard rectangle grids to K-D Tree.
The deviation of division will produce complex grid systems. Any trivial change of parent class will obviously change its child classes.
As iteration goes, differences of micro units will lead to diversified result in a macro level.
The fixed mathematical logic of parent and child makes fractal structures between levels highly similar – though ratio changes lead to different distribution, the topology of binary tree is fixed.
ps* Divisions showed above are all divided within the dimension of every single grid. If the division goes by absolute value rather than percentage, which means division will not happen if the value is out of range – the final result will not be a full K-D Tree(unaverage/not every parent node has 2 children/not every parent node has the same level depth of child data structure.
3. Gray-Value Based
The 3rd stage is based on grey value of image. By iteration, according to pixels inside the area, the avarage point is computed. Then the division goes in the same manner.
In this stage, to speed up every search in interations, the density of sampling decrease along iterations. But as a result, the locations of division are not evenly precise.
4. Point Based(K-D Tree)
The final stage of research used the logic of K-D Tree – which is based on a given point cloud. At the same time, 2D division can be also applied to 3D space – whih means we can generate binary tree using a 3D model.
