Thesis (MSc (Mathematical Sciences))--Stellenbosch University, 2008. / In this thesis we consider the modelling of a particular layout optimisation problem,
namely, the LEGO construction problem. The LEGO construction problem, in short,
concerns the optimal layout of a set of LEGO bricks to represent a given object.
Our goal is to develop a software package which LEGO enthusiasts can use to construct
LEGO sculptures for any real-world object.
We therefore not only consider the layout optimisation problem, but also the generation
of the input data required by the LEGO construction problem. We show that by using
3D geometric models to represent the real-world object, our implemented voxelisation
technique delivers accurate input data for the LEGO construction problem.
The LEGO construction problem has previously been solved with optimisation techniques
based on simulated annealing, evolutionary algorithms, and a beam search approach.
These techniques all indicate that it is possible to generate LEGO building
instructions for real-world objects, albeit not necessarily in reasonable time.
We show that the LEGO construction problem can be modelled easily with cellular
automata, provided that cells are considered as clusters which can merge or split during
each time step of the evolution of the cellular automaton. We show that the use of
cellular automata gives comparable layout results in general, and improves the results
in many respects. The cellular automata method requires substantially less memory
and generally uses fewer LEGO bricks to construct the LEGO sculpture when using
comparable execution times.
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:sun/oai:scholar.sun.ac.za:10019.1/2288 |
| Date | 12 1900 |
| Creators | Smal, Eugene |
| Contributors | Van Zijl, Lynette, Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences. |
| Publisher | Stellenbosch : Stellenbosch University |
| Source Sets | South African National ETD Portal |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Rights | Stellenbosch University |
Page generated in 0.0064 seconds