# Convex Hull in Mathematica

Published on 18 January 2023 (Updated: 18 January 2023)

Welcome to the Convex Hull in Mathematica page! Here, you'll find the source code for this program as well as a description of how the program works.

## Current Solution

``````(* Code *)

(* Convex hull option convexHull1 is based on the built-in ConvexHullMesh: *)

convexHull1 = Function[{ps},
Module[{mesh = ConvexHullMesh[ps]},
Round /@ Part[
MeshCoordinates[mesh],
First[First[MeshCells[mesh, 2]]]]]];

(* If that is considered cheating, then option convexHull2 implements it directly using Jarvis' algorithm: *)

convexHull2 = Function[{inputList},
Module[{orientation, l = inputList, i, j},
(* compute the direction in which three vertices are oriented *)
orientation = Function[{a, b, c}, Det[{a - b, c - b}]];

(* keep sorting the convex hull vertices to the beginning of the list;
'i' is the index of the last vertex in the convex hull;
'j' is the index of the next vertex selected to be permuted to the front *)
For[
(* initially *)
i = 0; (* no vertices selected into the convex hull *)
j = First[OrderingBy[l, First, 1]], (* find the first vertex by minimum x-coordinate *)

(* continue as long as the next selected vertex is not already in the convex hull *)
j > i,

(* iteration done in the body *),

(* permute the next selected vertex to the front of the list *)
i++;
l = Permute[l, If[i != j, Cycles[{{i, j}}], {}]];

(* find the next vertex that is clockwise to all other vertices *)

j = Mod[i + 1, Length[l], 1];
Do[ (* for all vertices *)
(* if 'k' is such that 'i', 'j', 'k' are counterclockwise, let 'k' become the new 'j' *)
If[orientation @@ l[[{i, j, k}]] > 0, j = k],
{k, Length[l]}];
];
(* return only the front part of the list containing the convex hull *)
Take[l, i]]];

(* The outer function provides the 'user interface' (e.g., the string parsing): *)

convexHullMain = Function[{lx, ly},
Module[{e = "Usage: please provide at least 3 x and y coordinates as separate lists (e.g. \"100, 440, 210\")"},
Catch[
convexHull2[
Transpose[
If[MatrixQ[#] \[And] Length[First[#]] >= 3,
#, Throw[e]] &[
Map[
(* convert string to integer, or throw *)
s \[Function] If[StringMatchQ[s, DigitCharacter ..],
FromDigits[s],
Throw[e]],
(* construct two arguments to convexHull: list of x coordinates, list of y coordinates *)
{StringSplit[lx, ", "], StringSplit[ly, ", "]},
{-1} (* at each leaf *)]]]]]]];

(* Valid Tests *)

Print /@ Apply[convexHullMain] /@ {
{"100, 180, 240", "220, 120, 20"},
{"100, 140, 320, 480, 280", "240, 60, 40, 200, 300"},
{"260, 280, 300, 320, 600, 360, 20, 240",
"160, 100, 180, 140, 160, 320, 200, 0"}
};

(* Invalid Tests *)

convexHullMain["100, 180", "240, 60, 40, 200, 300"]
convexHullMain["100, 180, 240", "240, 60, 40, 200, 300"]
convexHullMain["100, 180, 240", ""]
convexHullMain["100, 1A0, 240", "220, 120, 20"]

``````

Convex Hull in Mathematica was written by:

• Ben Hekster

If you see anything you'd like to change or update, please consider contributing.

## How to Implement the Solution

No 'How to Implement the Solution' section available. Please consider contributing.

## How to Run the Solution

No 'How to Run the Solution' section available. Please consider contributing.