= An algorithm for computing a convex hull in R*2 =

<<TableOfContents>>

In an Euclidean Space the Convex Hull of a set '''''I''''' is defined as the intersection of all convex sets containing '''''I'''''.

The problem of finding convex hulls finds its practical applications in '''pattern recognition''', '''image processing''', '''statistics''' and '''geographic information system'''. It also serves as a tool, a building block for a number of other computational-geometric algorithms.

For ''planar objects'', i.e., lying in the plane R^2^, the convex hull may be easily visualized by imagining an elastic band stretched open to encompass the given object; when released, it will assume the shape of the required convex hull.


.

== Graphical example ==
{{attachment:Convexhull.png}}

If the set '''''I''''' is a set of points in R^2^, then the convex hull is the smallest convex polygon which encloses '''''I''''' .

.
== Gift wrapping algorithm ==

Many convex hull algorithms had been proposed  for finding the points lying on the convex polygon.

Here a dynamic  function is presented that implements a ''gift wrapping algorithm''.

It follows a suggestion from Lars Strand <<MailTo(Lars.Strand AT skogoglandskap DOT NONSENSE no)>>, written in an email to <<MailTo(programming AT jsoftware DOT com)>> at Jan 11, 2008.

A number of points in R^2^ are given.

The problem is to determine the smallest convex region which includes all of the points.

The solution starts with the point '''p0''' having the smallest x-value. The next point '''p1''' will be the point which together with the first point defines a line having the smallest angle to the x-axis. Using this point '''p1''' as vertex, the task is to find a third point '''p2''' so that a line from the vertex has the largest angle to the line '''p0-p1'''.

Three points in the solution are now determined.

The procedure is repeated after a shift of  '''p1''' to '''p0''', '''p2''' to '''p1''', and a new point '''p2''' is found in the same way. 

The procedure stops when the new point '''p2''' is the same as the starting point.

The solution contains the coordinates of the points of the hull.

This Dfn calls another dynamic function for computing the polar phase of all points with respect of a previously chosen point lying on the hull.

The iteration is implemented by means of primitive '''power operator'''.

.

== The D function ==

{{{

ConvexHull←{
⍝ ⍵: matrix (2 rows) of points - first row:abscissae  second row:ordinates
⍝ return: matrix (2 rows) of points of convex hull

⍝ try:  ConvexHull ⍉9 2⍴1 0,1 ¯10,3 3,2 1,6 3,1 6,3 1,6 1,9 0
⍝
     ⎕IO←0
     pts←(⊂⍋⊃↓⍵)⌷[1]⍵                        ⍝sort by x-values:first point←→start vertex
     phs←{                                   ⍝ 12○⍵ polar phase ○¯1>≥○1.  see DFNS
         x y←⊂[1↓⍳⍴⍴⍵]⍵                      ⍝ x and y coordinates.
         x0 xn←1 0=⊂0=x                      ⍝ points on/off y axis.
         top←(x0×○0.5)+xnׯ3○(|y)÷x+x0       ⍝ upper quadrants.
         (0∨.≠⍵)×(1-2×y<0)×top+○x<0          ⍝ other quadrants.
     }
     angles←phs(0 1↓pts)-[0]0⌷[1]pts         ⍝phases(radians) of the vectors
     ixStart←0,1+⊃angles⍳⌊/angles            ⍝start with indexes of first segment
     ixHull←{
         ix0 ix1←¯2↑⍵                        ⍝ix1: index of last point←→last vertex
         v←{⍵+(⍵<0)×○2}phs pts-[0]ix1⌷[1]pts ⍝phases with respect to the last vertex
         other←(⍳1↓⍴pts)~ix0 ix1             ⍝indexes of other points
         angles←|(ix0⊃v)-(⊂other)⌷v              ⍝       _______/\_______
         angles←{f←⍵>○1 ⋄ (⍵×~f)+f×-⍵-○2}angles  ⍝angles (p0-p1)  (p1-px)
         ⍵,(angles⍳⌈/angles)⊃other           ⍝new vertex is where angle is largest
     }⍣{
         0=⊃⌽⍺                               ⍝repeat until first and last vertex coincide
     }ixStart
     (⊂ixHull)⌷[1]pts
 }
}}}

-----
Author: GianluigiQuario
----
CategoryDyalog CategoryDyalogDfns CategoryMaths