This blog features small programs using Metapict to draw figures and images.
Write to Jens Axel Søgaard at jensaxel@soegaard.net with comments and wishes for new topics.
2. Arrows
First let’s work on images of size 200x200 and let us keep the default
user window which has an \(x\)-range from -1 and 1 and an \(y\)-range from -1 to 1.
The default behavior is to draw an arrow head at the end of the curve.
Use
draw-double-arrow
to draw arrow heads at both at the beginning and end
of the curve.
The discussion below goes into detail with the shape of the default arrow head,
but let’s demonstrate that there are alternative arrow heads available.
The parameters are convenient to use to set the appearance of all arrows in a figure.
If you need special values for a few arrows, then pass the settings as keyword arguments.
We see that the default user coordinates has an \(x\)-range
\[\text{from } x_\text{min}=-1 \text{ to } x_\text{max}=1, \]and an \(y\)-range given by
\[\text{from } y_\text{min}=-1 \text{ to } y_\text{max}=1. \]We will stick with this default window for now.
We can manually draw a regular polygon with \(n=3\) sides:
The rule used to determine whether a point \(P\) is in the interior:
Given a point \(P\), consider a ray from \(P\) towards infinity.
For each intersection between the ray and the curve(s),
determine whether the curve crosses right-to-left or left-to-right.
Each right-to-left crossing counts as +1 and each left-to-right crossing as -1.
If the total sum of the counts is non-zero, then the point will be filled.
If we alter the orientation of the curve
c2
(the second circle) then the points
in the intersection of the two disks will sum to zero - so they won’t be filled.
In this example, we will take the following diagram of the passes
in Racket and turn it into a block diagram.
\[\begin{align}
\textrm{Source} & \xrightarrow{\texttt{read}} \textrm{Syntax Object} \\\\
& \xrightarrow{\texttt{expand}} \textrm{Syntax Object} \\\\
& \xrightarrow{\texttt{compile}} \textrm{Compiled Expression}\\\\
& \xrightarrow{\texttt{eval}}
\end{align} \]
Let’s make a 800 by 100 picture and set the user coordinates of the window
to an \(x\)-range from 0 to 800 and the \(y\)-range from -50 to 50.
With this choice we can use \(y=0\) for center position of our nodes.
The block diagram consists of a number of nodes connected by arrows.
We will need nodes for “Source”, “Syntax Object”, “Syntax Object” and “Compiled Expression”.
to place nodes.
This doesn’t look too good – the nodes are drawn on top of each other.
Instead of manually placing all nodes, let’s just place the first node
and then place each following node relative to the node on its left.
By default the rectangular path of a rectangle node is drawn with no
separation between the path and its contents. This looks cramped, when
the contents is a text, so we need to increase that inner separation.
This can be done with
#:inner-separationamount
when the
node is created. However we need to set this for all our nodes,
so instead we set the parameter
To set set the label gap size for a single edge, you can use
the keyword arguement
#:label-gap
.
We see at least two problems: the arrow head size is so small,
we can’t see it – and the labels are placed on top of the edges.
The first problem is fixed by setting the arrow head
length with
ahlength
. The second problem is that
the default gap size between labels and edges is too small,
so we set the parameter
The astute reader has noticed that we are missing the last edge.
The last edge needs an end node, so we make an “invisible” node
(a text node that shows the empty string).
Along this circle, we will make a mark for every 12 minutes.
The hour marks will be slightly larger. When arguments are named \(d\),
they will be in degrees. To make later drawings simpler, we let \(d\) denote
the angle measured from 12 \(o'clock\) in the clock-wise direction. The helper
function
point
computes the point on the outer that corresponds
to a clock angle \(d\).
In this section, we will tackle the problem of computing the convex hull of a set
of points \(𝕊=\{P_1,P_2,\ldots,P_n\}\). Imagine the points as nails. If you stretch
a rubber band around the nails, the rubber band will contract and assume the shape
of the convex hull.
In a convex set, the line segment between any two points is entirely within the set.
A convex set doesn’t have any “indentations”.
Intuitively we are looking for the smallest, convex polygon that encloses the points.
For now, we will ignore special cases such as the case where all points lie on the
same line (in which case the convex hull becomes a line segment).
Without the nails our initial example looks like this:
The output of a convex hull algorithm is a polygon.
We will represent a polygon as a list of points in clockwise order.
There are several algorithms that compute the convex hull, but let’s begin with the simplest.
It builds on a simple observation:
We are going in the clockwise direction around the polygon, so the other
points lie to the left. Had we used the counter clockwise direction,
the other points would lie to the right.
The line segment between two points \(P\) and \(Q\) from 𝕊 is an edge of the convex hull,
if all other points lie to the left of \(PQ\).
For two arbitrary points \(P\) and \(Q\) from 𝕊, we can thus test whether \(PQ\) is
an edge, by determining whether all other points \(R\) lie to the left of \(PQ\).
The sign of the determinant of the vector pair \((\overrightarrow{a}, \overrightarrow{b})\)
has the same sign as the orientation from \(\overrightarrow{a}\) to \(\overrightarrow{b}\).
To implement this algorithm, we need a way to test whether a point \(R\) lies
to the left of the edge \(PQ\). We could compute the angle
between \(\overrightarrow{PQ}\) and \(\overrightarrow{PR}\), but it is faster to compute their determinant.
Looks great. There is however a case we did not consider
in
(all-lie-to-the-left?PQ𝕊)
. If \(R\) is a point
on the extension of the line segment between \(P\) and \(Q\),
then \(R\) is not to the left of the line segment - but \(PQ\)
is still an edge. If however \(R\) lies directly on the line segment \(PQ\),
then \(PQ\) is not an edge (chances are that \(PR\) and \(RQ\) are edges).
is \(O(n^3)\).
In the next section, we will improve this.
7.2 Convex Hull - An incremental algorithm
This time we will find the edges of the convex hull polygon
in order. If we sort the points of \(𝕊=\{P_1,P_2,\ldots,P_n\}\),
after their \(x\)-coordinate (and break ties with the \(y\)-coordinate),
then the left-most point must be a vertex of the polygon.
We will then add one point at a time until we get to the right-most point.
Given a vertex point \(P\), we will thus test the following points \(Q\) in turn
until we find an edge \(PQ\). This will give us the lower half of the convex hull.
