Voronoi: Touchable Diagrams in iOS Simulator
Posted by Jeffrey
I’ve put together another OCaml app that you can run on the iOS Simulator. It lets you make colorful pictures based on Voronoi diagrams. Although Voronoi diagrams are computationally interesting, they also just look very cool.
A Voronoi diagram is based on a set of dots on the screen. Each dot “claims” the area closest to it, and gets to say what color it should be. As you move the dots around, the shapes of the claimed areas adapt to the different layout, and the colors change. It’s hard to describe, but very enjoyable to play with.
If you don’t want to build it yourself, a prebuilt binary for Voronoi is available from Psellos. See below for how to extract and try it out in the iOS Simulator (it’s extremely easy). Otherwise you can get the sources from Psellos, compile using Xcode tools, and run the app in the iOS Simulator. This is also pretty easy. All you need for either approach is an installation of Xcode with the iOS SDK; you don’t need an iOS device or have to be a registered Apple developer.
Here are some hints for trying out the app:
Touching the screen in an open area creates a new dot that you can move around to any place you like. Touching near an existing dot allows you to move the dot to a new place.
If you move a dot on top of another dot (or almost on top), they combine into a larger dot.
If you combine three dots near the center of the screen, a large number of randomly placed dots are added to the screen. (The number of dots is doubled.)
If you combine three dots near the edge of the screen, a large number of dots are randomly removed. (The number of dots is divided in half.)
If you shake the device, you get a menu for starting over (with just one dot), or for changing the colors. To shake the phone in the iOS Simulator, use the Hardware -> Shake Gesture menu.
If you combine four dots (which is tricky to do), all four of the dots disappear. This can be useful if you want to clear randomly placed dots from an area.
The app has been built and tested with Xcode 3.2.5 and Xcode 4.0.2. It will work with any recent Xcode release.
Please note that a few of the command lines of the following discussions are too long to fit on a single line of a typical browser window. In a lot of cases there is no good place to split them into smaller lines, usually because of a long filename or URL. Take care that you enter them as a single line if you’re typing them in by hand.
Running Prebuilt Voronoi Binary
If you want to run the prebuilt Voronoi binary (to prove to yourself that it works), just download the binary for Voronoi 1.0.0 from Psellos:
$ curl -O -s http://psellos.com/pub/voronoi/voronoi-simapp-1.0.0.tgz $ ls -l voronoi-simapp-1.0.0.tgz -rw-r--r-- 1 psellos staff 165540 Jul 7 13:45 voronoi-simapp-1.0.0.tgz
To save typing, you can download it directly from this link:
$ tar -xzf voronoi-simapp-1.0.0.tgz
This creates a directory named
voronoi-simapp-1.0.0 in which you should
see the binary (
Voronoi) and a script named
runsim that runs the app
in the iOS Simulator. To run Voronoi, just
cd and run the script:
$ cd voronoi-simapp-1.0.0 $ runsim
If you don’t have Xcode installed in the usual place, you should edit the script appropriately before running it.
Note: for simplicity, this script uses an unsupported interface of the iOS Simulator. Since it’s unsupported, the interface could disappear in a future release of Xcode. There will always be a way to run the app through the Xcode IDE, of course.
My first OCaml iOS Simulator app, Gamut, shows how to compile an app using the OCamlXSim compiler that I put together, described here. It also shows how to link and execute the app in the iOS Simulator. However, the Gamut app itself is quite simple. The Voronoi app has more of the feel of a real iOS app.
It has an interactive UIKit component.
It uses the touch interface to manipulate visible objects, and responds to the shake gesture.
It does more complex graphics.
It performs some non-trivial computation.
Voronoi shows how to wrap the
UIActionSheet class, which is used to
display a menu when you shake the phone. This is interesting both for
the typing and the implementation. At the type level, you want to have
a good handling for the action sheet delegate, the object that responds
to user touches on the displayed menu. The
shows one way to define two mutually recursive classes that capture the
At the implementation level, you need to wrap the delegate object
correctly in an ObjC object to pass the menu touches from the ObjC world
to the OCaml world. This is a special case of the general problem of
handling dynamically constructed callbacks from ObjC to OCaml. The
ASDelegate class in
wrap.m shows a simple solution to the problem.
Each dot of a Voronoi diagram is called a site. The region around each site is a polygon called a cell. The code for drawing a cell seems particularly concise when written in OCaml:
val bezierpath : UiBezierPath.t = UiBezierPath.bezierPath () let polypath = function |  -> () (* Nothing to draw *) | p1 :: rest -> begin bezierpath#moveToPoint' p1; List.iter bezierpath#addLineToPoint' rest; bezierpath#closePath; end
While the Gamut app doesn’t do much interesting computation, Voronoi does quite a bit: as you move the sites, it continuously calculates the Voronoi cells to keep the picture updated. It also uses a different set of Voronoi cells (generated internally) to give an interesting color to each point of the screen. As a result, the amount of OCaml code compared to Objective C code in Voronoi is quite a bit higher than in Gamut.
The fraction of OCaml code can continue to increase as you write more complex apps. At Psellos we have a mostly fixed amount of Objective C for our iOS apps, and in fact we write our wrappers mainly in OCaml. So the amount of Objective C is relatively small and independent of the size of the project.
Building Voronoi from Source
Before starting, make sure you have installed Apple’s Xcode and iOS SDK. I used both Xcode 3.2.5 and Xcode 4.0.2 to build and test Voronoi, but any recent version of Xcode will work. You also need an OCaml compiler that conforms to the iOS Simulator ABI. You can use the one I put together—binaries and instructions for building from source are given here.
Now download the sources for Voronoi 1.0.0 from Psellos:
$ curl -O -s http://psellos.com/pub/voronoi/voronoi-1.0.0.tgz $ ls -l voronoi-1.0.0.tgz -rw-r--r-- 1 psellos staff 26915 Jul 7 13:46 voronoi-1.0.0.tgz
To save typing, you can download it directly from this link:
Now, untar and
cd into the Voronoi directory.
$ tar -xzf voronoi-1.0.0.tgz $ cd voronoi-1.0.0
Building and running Voronoi is done by a
Makefile. You may need to
change some of the specific settings in this file:
PLAT = /Developer/Platforms/iPhoneSimulator.platform SDK = /Developer/SDKs/iPhoneSimulator4.2.sdk OCAMLDIR = /usr/local/ocamlxsim
PLAT to the location of your iPhoneSimulator platform
directory, part of the Xcode iOS SDK. Change
SDK to the iOS SDK
you wish to use. Probably you want to set it to the most recent SDK
that you have installed. Change
OCAMLDIR to the location of your
OCaml compiler for the iOS Simulator.
Now you can build and run the app:
$ make ... /usr/local/ocamlxsim/bin/ocamlc -c vorocells.mli /usr/local/ocamlxsim/bin/ocamlopt -cc '/Developer/Platforms/iPhoneSimulator.platform/Developer/usr/bin/gcc-4.2' -ccopt '-arch i386 -isysroot /Developer/Platforms/iPhoneSimulator.platform/Developer/SDKs/iPhoneSimulator4.2.sdk -gdwarf-2 -D__IPHONE_OS_VERSION_MIN_REQUIRED=30200 -isystem /usr/local/ocamlxsim/lib/ocaml -DCAML_NAME_SPACE' -c vorocells.ml ... ibtool --compile Voronoi.nib Voronoi.xib echo -n 'APPL????' > PkgInfo $ make execute $
You should see the Voronoi app running in the iOS Simulator.
Note: for simplicity,
make execute uses an unsupported interface of the iOS Simulator.
Since it’s unsupported, the interface could disappear in a future
release of Xcode. There will always be a way to run the app through the
Xcode IDE, of course.
Theory of Operation
Voronoi essentially follows the MVC paradigm. The model is a list of points representing the Voronoi sites, and a value called a “color field” that associates a color with each point of the display. The view is the graphical representation of the Voronoi diagram: the colored polygons and dots. These are coordinated by the controller, an instance of the class Voronoictlr.t.
As in the Gamut app, graphics are handled through an Objective C class
ViewDelegator. It’s a subclass of the Cocoa Touch
class, and its instances delegate their GUI methods to a specified
delegate object. In particular, instances delegate touch events, motion
events, and the drawing method
participates in this
ViewDelegate protocol, and thus the controller
receives notifications of touch, motion, and drawing events. The
controller also participates in the
UIApplicationDelegate protocol to
receive notifications of changes in the application state.
When you touch the screen, Cocoa Touch calls a method in the
Voronoictlr (inverse) wrapper class, which is translated directly into
an OCaml method call to the controller. The controller determines
whether the touch is near an existing site or is in an open area. In
the first case, the existing site is moved to the beginning of the site
list. In the second case, a new site is created at the touch point and
added at the beginning of the list. Thus, the site to be moved is
always first in the list.
While the touch is active, the controller moves the first site to follow
it. After each incremental move, the voronoi cells are recalculated and
redisplayed. Calculations of the Voronoi cells are handled by the
Vorocells module, and colors for the cells are chosen using the
Colorfield module. The
Vorocells module uses a straightforward
(quadratic) algorithm to calculate the cells. The
goes to a fair amount of work to choose colors that look good together.
When you shake the phone and ask to change the colors or the sites, the controller updates the appropriate part of the model accordingly. The controller then recalculates and displays the view.
The startup of an iOS app is controlled by a nib file, generated by
Interface Builder. For Voronoi, the file is
Voronoi.nib. This file
says to create three objects: the main window; an instance of
ViewDelegator that covers the whole screen; and an instance of
Voronoictlr.t. The action sheet (an instance of
UiApplicationSheet.t) is created dynamically when the app is launched,
and so does not appear in the nib file.
In versions of Xcode prior to 4.0, Interface Builder was a separate
utility. In Xcode 4.0, it has been integrated as one of the many
specialized editors for project components. If you’re using an older
version of Xcode, you should be able to open the source file
Voronoi.xib directly with Interface Builder. For those using Xcode 4,
I created a small project named
Voronoi.xcodeproj whose only purpose
is to examine and modify the
Voronoi.xib file. If you double-click on
Voronoi.xcodeproj in the Finder, it will start Xcode on the project.
You can then navigate to the
Voronoi.xib file and examine its
contents. (Hint: to see the detailed properties of objects, open the
Utility window at the right of the screen.)
In either case, you’ll see that
Voronoi.xib is pretty simple. There
are only three interesting objects: the main window, a
instance that occupies the whole window, and an instance of
There is a connection to the controller from the
delegate outlet of
the application (represented by File’s Owner). This supports the
application startup notification.
There is a connection from the
delegate outlet of the
to the controller, and a connection from the
delegator outlet of the
controller back to the
ViewDelegator. These support the notifications
for touches, motion, and drawing.
Since Interface Builder (IB) doesn’t know anything about OCaml (at least not yet), it gets its information from the header files for your wrapper classes. In earlier Xcode versions, you may need to manually tell IB to load the wrapper header files. To load header files into earlier versions of IB, click on the File -> Read Class Files menu item, and navigate to your ObjC header files, i.e., to the wrapper files for your OCaml classes. Note that you need wrappers only for OCaml classes that are accessed from ObjC, which should be just a few of them.
Although I’ve packaged up Voronoi to run in the iOS Simulator, it will naturally also run directly on iOS devices (iPhone, iPod Touch, iPad) with no changes to the code. The only changes required for iPhone and iPod Touch are to the building environment. For iPad, the nib file will also need to change. The code is written to be independent of the screen resolution, so it ought to run nicely as a native iPad app, in fact.
Feel free to send me any cool looking pictures that you create using the Voronoi app. If you modify the app to make even cooler pictures, please let me know about it so I can give you credit.
If you’re interested in learning more about Voronoi diagrams as
mathematical and computational geometric objects, a good place to start
is the Wikipedia article. An interesting project would be to
replace the simple algorithm in the
Vorocells module with a more
sophisticated one, such as Fortune’s Algorithm, and see if this
makes the app more responsive when there are many cells.
Compiling OCaml to run directly on iOS is described in an accompanying note here. I’ve also put together two apps that are packaged to run on iOS devices. There is a simple app named Portland that tracks the device’s orientation (portrait or landscape), and a slightly more complicated app named Slide24 that plays (and solves) the classic 5x5 sliding tile puzzle.
I’d be very happy to explain any part of Voronoi in more detail. The only thing stopping me is my natural shyness. If you have questions, comments, or corrections please email me at email@example.com.