14.1. Basics of Computational Geometry¶
Computational geometry (CG) is a sub-area of computer science that studies data structures and algorithms for solving geometric problems, which are common in computer vision, metallurgy, manufacturing, forestry, and navigation.
Those problem as we know them from the high school, often have a “continuous” nature, so the main task of computational geometry is to reduce them to familiar abstractions, in terms of the data structures that we have already studies. In this last chapter of this course, we will take a look at some basic constructions of CG and will learn how to represent them graphically, as well as how to compute some of their intrinsic properties.
14.1.1. Working with graphics in OCaml¶
There is not much fun in talking about geometric problems without being able to visualise them.
To render the shapes and the results of the algorithms, we will employ
Graphics package, which provides very primitive (yet
sufficient for our needs) support for rendering two-dimensional
The detailed instructions on how to install and run the functions from
Graphics package are given in this demo repository.
It is quite easy to start working with graphics. For instance running the following command opens a window that is 800 pixels wide and 600 tall:
open Graphics;; open_graph " 800x600"
The axes of the window start in the bottom left corner, and go right
and up. It is more convenient to have our layout “centered” around the
actual center of the image, so we could make us of the negative parts
of the axes as well. This is why, when rendering our figures, we will
always shift them with respect to a certain origin, which we choose to
be the center of our
800x600 pixels window:
let origin = (400, 300) let go_to_origin _ = let x = fst origin in let y = snd origin in moveto x y; set_color black
In the function
go_to_origin, the command
moveto transfeers the “invisible” pointer to the origin, and sets the default drawing color to be
Graphics.black (other colours are possible and can be set up using the RGB scheme).
Using the following function we can draw a “grid” of the two axes, to help the orientation:
let draw_axes _ = let x = fst origin in let y = snd origin in set_color green; moveto 0 y; lineto (x * 2) y; moveto x 0; lineto x (y * 2); moveto x y; set_color black
Using it, we can create a new window with the axes already drawn:
let mk_screen _ = open_graph " 800x600"; draw_axes ()
Finally, we can remove everything but the axes by running the following function:
let clear_screen _ = clear_graph (); draw_axes ()