# Drawing convex hull (Pic)

The convex hull of a set of points Q is the smallest polygon that embraces every point in Q. This article explains how to draw a convex hull diagram using pic. The exact steps to convert a pic document into a graphic format is available at Hello World (Pic).

## Plotting random points

Thirteen random points in a 2-D plane.

We first choose thirteen points and scatter them to a 2-dimensional plane.

``` P1: ( 1,  3)
P2: ( 2,  7)
P3: ( 9, -2)
P4: (-5,  7)
P5: (-7,  2)
P6: (-1,  3)
P7: ( 4,  6)
P8: (-3, -4)
P9: ( 6,  0)
P10: (-2,  8)
P11: ( 0, -5)
P12: ( 5,  8)
P13: (-4, -1)
```

We draw a circle at each coordinate. Note that we need the label for each point for later use.

```<<points>>=
P1: circle fill at (1, 3)
P2: circle fill at (2, 7)
P3: circle fill at (9, -2)
P4: circle fill at (-5, 7)
P5: circle fill at (-7, 2)
P6: circle fill at (-1, 3)
P7: circle fill at (4, 6)
P8: circle fill at (-3, -4)
P9: circle fill at (6, 0)
P10: circle fill at (-2, 8)
P11: circle fill at (0, -5)
P12: circle fill at (5, 8)
P13: circle fill at (-4, -1)
```

We place the name of each point at every coordinate. Note that special `pic` commands such as `below`, `above`, `ljust`, and `rjust` really come in handy.

```<<names>>=
"\$p_1\$" at P1  below ljust
"\$p_2\$" at P2  below ljust
"\$p_3\$" at P3  below ljust
"\$p_4\$" at P4  below ljust
"\$p_5\$" at P5  below rjust
"\$p_6\$" at P6  below ljust
"\$p_7\$" at P7  below ljust
"\$p_8\$" at P8  below rjust
"\$p_9\$" at P9  below ljust
"\$p_{10}\$" at P10 below ljust
"\$p_{11}\$" at P11 below ljust
"\$p_{12}\$" at P12 above ljust
"\$p_{13}\$" at P13 below ljust
```

Embedding the information on points and names completes a whole `pic` document. We could reduce the size of `pic` document by adjusting `scale` variables. The `circlerad` variable defines the default radius of every circle in a document.

```<<Scattered_points.pic>>=
.PS
scale = 8
points
names
.PE
```

## Drawing convex hull

The convex hull of a set of given points.

In addition to points and names, we need to draw a polygon embracing every points in a graph.

```<<Scattered_points.pic>>=
.PS
scale = 8
points
names
lines
.PE
```

The convex hull is drawn in dashed line. The `pic` command for dashed pattern is `dashed`.

```<<lines>>=
line dashed from P11 to P3
line dashed from P3  to P12
line dashed from P12 to P10
line dashed from P10 to P4
line dashed from P4  to P5
line dashed from P5  to P8
line dashed from P8  to P11
```