A Unity C# implementation of the Gift Wrapping algorithm

README.md

A Unity C# implementation of the Gift Wrapping algorithm

This is an implementation of the Gift-Wrapping algorithm for calculating the convex hull of a set of points in 2D space. This example is for Unity C#. The code is listed below this readme.

Usage

To compute the convex hull of a list of points (List<Vector3>), it's super easy:

var convexHull = ConvexHull.compute(points);

If you want to the convex hull to loop back to the beginning (duplicate vertex at the end of the hull), you can additionally pass a second parameter:

var convexHull = ConvexHull.compute(points, true);

Then, to render it, it's as easy as something like:

for(var i = 1; i < convexHull.Count; i++)
  Gizmos.DrawLine(convexHull[i-1], convexHull[i]);

ConvexHull.cs

/*
This is free and unencumbered software released into the public domain.
Anyone is free to copy, modify, publish, use, compile, sell, or
distribute this software, either in source code form or as a compiled
binary, for any purpose, commercial or non-commercial, and by any
means.

In jurisdictions that recognize copyright laws, the author or authors
of this software dedicate any and all copyright interest in the
software to the public domain. We make this dedication for the benefit
of the public at large and to the detriment of our heirs and
successors. We intend this dedication to be an overt act of
relinquishment in perpetuity of all present and future rights to this
software under copyright law.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
OTHER DEALINGS IN THE SOFTWARE.

For more information, please refer to <https://unlicense.org>
*/

/**
 * @file   ConvexHull.cs
 * @author Benjamin Williams <bwilliams@lincoln.ac.uk>
*/

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using System.Linq;

public static partial class ConvexHull
{   
    /// <summary>
    /// Computes the convex hull of a list of points.
    /// </summary>
    /// <param name="points">Points.</param>
    /// <param name="loop">If set to <c>true</c> loop.</param>
    public static List<Vector3> compute(List<Vector3> points, bool loop = false)
    {
        //The points which will be returned
        var returnPoints = new List<Vector3>();

        //Find left-most point on x axis
        var currentPoint = lowestXCoord(points);

        //The endpoint to compare against
        Vector3 endpoint = Vector3.zero;

        while (true)
        {
            //Add current point
            returnPoints.Add(currentPoint);

            //Set endpoint back to the first point in the list of points
            endpoint = points[0];

            for(var j = 1; j < points.Count; j++)
            {
                //Run through points -- if the turn from this point to the other is greater, set endpoint to this
                if ((endpoint == currentPoint) || (ccw(currentPoint, endpoint, points[j]) < 0))
                    endpoint = points[j];
            }

            //Set current point
            currentPoint = endpoint;

            //Break condition -- if we've looped back around then we've made a convex hull!
            if (endpoint == returnPoints[0])
                break;
        }

        //If we want to loop, include the first vertex again
        if (loop)
            returnPoints.Add(returnPoints[0]);

        //And finally, return the points
        return returnPoints;
    }

    /// <summary>
    /// Finds the lowest x value.
    /// </summary>
    /// <returns>The X coordinate.</returns>
    /// <param name="array">Array.</param>
    private static Vector3 lowestXCoord(List<Vector3> array)
    {
        return array.Where(p => p.x == (array.Min(y => y.x))).First();
    }


    /// <summary>
    /// Swap two elements in an array, given two indices
    /// </summary>
    /// <param name="array">Array.</param>
    /// <param name="idxA">Index a.</param>
    /// <param name="idxB">Index b.</param>
    private static void swap(ref Vector3[] array, int idxA, int idxB)
    {
        //temp = a
        var temp = array[idxA];

        //a overwritten with b
        array[idxA] = array[idxB];

        //b overwritten with temp
        array[idxB] = temp;
    }


    /// <summary>
    /// Determines if three points are in a counter-clockwise turn. Returns:
    /// n < 0: If clockwise
    /// n > 0: If counter-clockwise
    /// n = 0: If collinear
    /// </summary>
    /// <param name="p1">P1.</param>
    /// <param name="p2">P2.</param>
    /// <param name="p3">P3.</param>
    public static float ccw(Vector3 p1, Vector3 p2, Vector3 p3)
    {
        // Determinant
        return Mathf.Sign((p2.x - p1.x) * (p3.z - p1.z) - (p3.x - p1.x) * (p2.z - p1.z));
    }
}

Hi, what license is this code available under? Thank you!