Last active
June 30, 2020 15:03
-
-
Save thebne/4ed6af35767717fc544c64fec91025cf to your computer and use it in GitHub Desktop.
Expand fill of convex polygon - Unity (C#)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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