Skip to content

Instantly share code, notes, and snippets.

@thebne
Last active June 30, 2020 15:03
Show Gist options
  • Save thebne/4ed6af35767717fc544c64fec91025cf to your computer and use it in GitHub Desktop.
Save thebne/4ed6af35767717fc544c64fec91025cf to your computer and use it in GitHub Desktop.
Expand fill of convex polygon - Unity (C#)
// this is an adaptation to Unity of the algorithm described
//. in https://stackoverflow.com/questions/3749678/expand-fill-of-convex-polygon/3897471
using UnityEngine;
using System.Linq;
using System.Collections.Generic;
static class ConvexHull
{
public static Vector2[] ExpandConvexHull(Vector2[] poly, float distance)
{
var expanded = new List<Vector2>();
var isCw = PolyIsCw(poly);
for (var i = 0; i < poly.Length; ++i)
{
// get this point (pt1), the point before it
// (pt0) and the point that follows it (pt2)
var pt0 = poly[(i > 0) ? i - 1 : poly.Length - 1];
var pt1 = poly[i];
var pt2 = poly[(i < poly.Length - 1) ? i + 1 : 0];
// find the line vectors of the lines going
// into the current point
var v01 = pt1 - pt0;
var v12 = pt2 - pt1;
// find the normals of the two lines, multiplied
// to the distance that polygon should inflate
var rot01 = isCw ? Rot90CCW(v01) : Rot90CW(v01);
var rot12 = isCw ? Rot90CCW(v12) : Rot90CW(v12);
var d01 = rot01.normalized * distance;
var d12 = rot12.normalized * distance;
// use the normals to find two points on the
// lines parallel to the polygon lines
var ptx0 = pt0 + d01;
var ptx10 = pt1 + d01;
var ptx12 = pt1 + d12;
var ptx2 = pt2 + d12;
// find the intersection of the two lines, and
// add it to the expanded polygon
expanded.Add(Intersect(ptx0, ptx10, ptx12, ptx2));
}
return expanded.ToArray();
}
private static Vector2 Intersect(Vector2 line1A, Vector2 line1B, Vector2 line2A, Vector2 line2B)
{
var a1 = line1B.x - line1A.x;
var b1 = line2A.x - line2B.x;
var c1 = line2A.x - line1A.x;
var a2 = line1B.y - line1A.y;
var b2 = line2A.y - line2B.y;
var c2 = line2A.y - line1A.y;
var t = (b1 * c2 - b2 * c1) / (a2 * b1 - a1 * b2);
return new Vector2(
x: line1A.x + t * (line1B.x - line1A.x),
y: line1A.y + t * (line1B.y - line1A.y)
);
}
private static Vector2 Rot90CW(Vector2 v)
{
return new Vector2(x: v.y, y: -v.x);
}
private static Vector2 Rot90CCW(Vector2 v)
{
return new Vector2(x: -v.y, y: v.x);
}
private static bool PolyIsCw(Vector2[] p)
{
return Vector2.Dot(
Rot90CW(p[1] - p[0]),
p[2] - p[1]
) >= 0;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment