Skip to content

Instantly share code, notes, and snippets.

@FaffyWaffles

FaffyWaffles/_UnionPolygonsController.cs

Created June 9, 2022 06:06
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save FaffyWaffles/5067210645424009e91aea3af445ed1d to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save FaffyWaffles/5067210645424009e91aea3af445ed1d to your computer and use it in GitHub Desktop.
Download ZIP
Union Polygon V2
Raw
_UnionPolygonsController.cs
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using UnityEngine;
using UnityEditor;
using Sirenix.OdinInspector;
public class _UnionPolygonsController : SerializedMonoBehaviour
{
[ListDrawerSettings(ElementColor = "FaceColor", ShowIndexLabels = true)]
public List<List<Vector2>> edgeLoops = new List<List<Vector2>>();
public List<List<Vector2>> newPolygons = new List<List<Vector2>>();
[HideReferenceObjectPicker]
public class HoleData
{
public bool hole;
public int holeDepth;
public List<int> holeParent;
public List<int> holeChildren;
public HoleData()
{
this.holeParent = new List<int>();
this.holeChildren = new List<int>();
}
}
[HideReferenceObjectPicker]
public class Polygon
{
public List<Vector2> edge;
public List<List<Vector2>> holes;
public Polygon(List<Vector2> edge, List<List<Vector2>> holes)
{
this.edge = edge;
this.holes = holes;
}
}
public List<Polygon> polygons = new List<Polygon>();
private bool done = false;
[Button]
public void Init()
{
if (Application.isPlaying)
{
newPolygons = UnionPolygon(new List<List<Vector2>>(edgeLoops));
HoleDetection(newPolygons);
done = true;
}
}
public List<List<Vector2>> UnionPolygon(List<List<Vector2>> edgeLoops)
{
List<List<Vector2>> newPolygons = new List<List<Vector2>>();
for (int i = 0; i < edgeLoops.Count; i++)
{
if (edgeLoops[i].Count == 2)
{
Vector2 point = (edgeLoops[i][0] + edgeLoops[i][1]) / 2;
edgeLoops[i].Insert(1, point);
}
}
#region Fix Winding Order
for (int i = 0; i < edgeLoops.Count; i++)
{
float sum = new float();
for (int j = 0; j < edgeLoops[i].Count; j++)
{
Vector2 a = edgeLoops[i][j];
Vector2 b = edgeLoops[i][(j + 1) % edgeLoops[i].Count];
sum += (b.x - a.x) * (b.y + a.y);
}
if (Mathf.Sign(sum) < 0)
edgeLoops[i].Reverse();
}
#endregion
int n = 0;
while (edgeLoops.Count > 0)
{
n++;
List<Vector2> newPolygon = new List<Vector2>();
int P = 0; //currentPolygon
int I = 0; //currentIndex
#region Setup First Point
Vector2 maxX = new Vector2();
for (int p = 0; p < edgeLoops.Count; p++)
{
for (int i = 0; i < edgeLoops[p].Count; i++)
{
if (edgeLoops[p][i].x > maxX.x)
{
maxX = edgeLoops[p][i];
P = p;
I = i;
}
}
}
#endregion
HashSet<int> hashedPolygons = new HashSet<int>();
while (true)
{
hashedPolygons.Add(P);
if (newPolygon.Contains(edgeLoops[P][I % edgeLoops[P].Count]))
break;
Vector2 a = edgeLoops[P][I % edgeLoops[P].Count];
Vector2 b = edgeLoops[P][(I + 1) % edgeLoops[P].Count];
newPolygon.Add(a);
Vector2 intersection = new Vector2();
int p = P;
int i = I;
if (IsLineIntersectingAnyPolygon(a, b, ref p, ref i, out intersection, edgeLoops))
{
newPolygon.Add(intersection);
if (!IsLineIntersectingAnyPolygon(intersection, edgeLoops[p][(i + 1) % edgeLoops[p].Count], edgeLoops))
{
P = p;
I = i;
}
else
{
hashedPolygons.Add(p);
while (IsLineIntersectingAnyPolygon(intersection, edgeLoops[p][(i + 1) % edgeLoops[p].Count], ref p, ref i, out intersection, edgeLoops))
{
newPolygon.Add(intersection);
hashedPolygons.Add(p);
P = p;
I = i;
}
}
}
I++;
}
if (InfiniteLoopFailsafe(n, 100))
break;
if (hashedPolygons.Count == 1)
{
newPolygons.Add(new List<Vector2>(newPolygon));
edgeLoops.RemoveAt(P % edgeLoops.Count);
continue;
}
if (hashedPolygons.Count == edgeLoops.Count)
newPolygons.Add(new List<Vector2>(newPolygon));
for (int i = edgeLoops.Count - 1; i >= 0; i--)
if (hashedPolygons.Contains(i))
edgeLoops.RemoveAt(i);
if (edgeLoops.Count > 0)
edgeLoops.Add(new List<Vector2>(newPolygon));
}
return newPolygons;
}
public static bool IsLineIntersectingAnyPolygon(Vector2 a, Vector2 b, ref int P, ref int I, out Vector2 closestIntersection, List<List<Vector2>> edgeLoops)
{
bool intersected = false;
Vector2 intersection = new Vector2();
closestIntersection = new Vector2();
float closestDistance = new float();
for (int p = 0; p < edgeLoops.Count; p++)
{
if (p != P)
{
for (int i = 0; i < edgeLoops[p].Count; i++)
{
Vector2 x = edgeLoops[p][i];
Vector2 y = edgeLoops[p][(i + 1) % edgeLoops[p].Count];
if (AreLinesIntersecting(a, b, x, y, out intersection))
{
float distance = Vector3.Distance(a, intersection);
if ((distance <= closestDistance) || (!intersected))
{
closestIntersection = intersection;
closestDistance = distance;
P = p;
I = i;
intersected = true;
}
}
}
}
}
return intersected;
}
public static bool IsLineIntersectingAnyPolygon(Vector2 a, Vector2 b, List<List<Vector2>> edgeLoops)
{
Vector2 intersection = new Vector2();
for (int p = 0; p < edgeLoops.Count; p++)
{
for (int i = 0; i < edgeLoops[p].Count; i++)
{
Vector2 x = edgeLoops[p][i];
Vector2 y = edgeLoops[p][(i + 1) % edgeLoops[p].Count];
if (AreLinesIntersecting(a, b, x, y, out intersection))
return true;
}
}
return false;
}
public static bool AreLinesIntersecting(Vector2 A, Vector2 B, Vector2 C, Vector2 D, out Vector2 intersection)
{
float buffer = 0.001f;
bool isIntersecting = false;
intersection = new Vector2();
float determinant = (D.y - C.y) * (B.x - A.x) - (D.x - C.x) * (B.y - A.y);
//Make sure the determinant is > 0, if not the lines are parallel
if (determinant != 0f)
{
float a = ((D.x - C.x) * (A.y - C.y) - (D.y - C.y) * (A.x - C.x)) / determinant;
float b = ((B.x - A.x) * (A.y - C.y) - (B.y - A.y) * (A.x - C.x)) / determinant;
//Is intersecting if a and b are between 0 and 1
if (a > 0f && a < 1f && b > 0f && b < 1f)
{
intersection = A + a * (B - A);
if (((A - intersection).sqrMagnitude >= (buffer * buffer)) && ((B - intersection).sqrMagnitude >= (buffer * buffer)) && ((C - intersection).sqrMagnitude >= (buffer * buffer)) && ((D - intersection).sqrMagnitude >= (buffer * buffer)))
isIntersecting = true;
}
}
return isIntersecting;
}
public void HoleDetection(List<List<Vector2>> edgeLoops)
{
List<HoleData> holes = new List<HoleData>();
foreach (List<Vector2> lV2 in edgeLoops)
holes.Add(new HoleData());
for (int i = 0; i < edgeLoops.Count; i++)
{
Vector2 point = edgeLoops[i][0];
for (int j = 0; j < edgeLoops.Count; j++)
{
if (i != j)
{
if (IsPointInPolygon(point, edgeLoops[j]))
{
holes[i].holeDepth++;
if (holes[i].holeDepth % 2 == 0)
holes[i].hole = false;
else
holes[i].hole = true;
holes[i].holeParent.Add(j);
}
}
}
}
for (int i = 0; i < holes.Count; i++)
{
if (holes[i].hole)
{
holes[holes[i].holeParent[holes[i].holeDepth - 1]].holeChildren.Add(i);
}
}
for (int i = 0; i < holes.Count; i++)
{
if (!holes[i].hole)
{
List<List<Vector2>> polyHole = new List<List<Vector2>>();
foreach (int n in holes[i].holeChildren)
polyHole.Add(new List<Vector2>(edgeLoops[n]));
polygons.Add(new Polygon(new List<Vector2>(edgeLoops[i]), polyHole));
}
}
}
public static bool CheckIndex(int i, int min, int max)
{
if (i >= min && i < max)
return true;
else
return false;
}
public static bool IsPointInPolygon(Vector2 point, List<Vector2> polygon)
{
int polygonLength = polygon.Count, i = 0;
bool inside = false;
float pointX = point.x, pointY = point.y;
float startX, startY, endX, endY;
Vector2 endPoint = polygon[polygonLength - 1];
endX = endPoint.x;
endY = endPoint.y;
while (i < polygonLength)
{
startX = endX; startY = endY;
endPoint = polygon[i++];
endX = endPoint.x; endY = endPoint.y;
inside ^= (endY > pointY ^ startY > pointY) && ((pointX - endX) < (pointY - endY) * (startX - endX) / (startY - endY));
}
return inside;
}
#region Debug
public bool gizmosActive = true;
private Color FaceColor(int index)
{
Color c = colors[index];
return new Color(c.r, c.g, c.b, .50f);
}
[Button]
void ColorGen()
{
DistinctRandomColors(edgeLoops.Count, out colors, RandomColor(), true);
}
[Range(.001f, .1f)] public float gizmoSize = .01f;
private void OnDrawGizmos()
{
if (gizmosActive)
{
if ((colors == null)||(edgeLoops.Count != colors.Length))
DistinctRandomColors(edgeLoops.Count, out colors, RandomColor(), true);
if (done)
{
DebugPolygonUnion();
//DebugHoleDetection();
}
else
{
DebugUVs();
}
}
}
void DebugUVs()
{
Gizmos.color = Color.green;
for (int i = 0; i < edgeLoops.Count; i++)
{
for (int j = 0; j < edgeLoops[i].Count; j++)
{
Vector3 a = edgeLoops[i][j];
Vector3 b = edgeLoops[i][(j + 1) % edgeLoops[i].Count];
Debug.DrawLine(a, b, colors[i]);
}
}
}
void DebugPolygonUnion()
{
for (int i = 0; i < newPolygons.Count; i++)
{
for (int j = 0; j < newPolygons[i].Count; j++)
{
Vector3 a = newPolygons[i][j];
Vector3 b = newPolygons[i][(j + 1) % newPolygons[i].Count];
Debug.DrawLine(a, b, colors[i]);
//Debug.DrawLine(a, b, Color.green);
//Handles.ArrowHandleCap(0, a, Quaternion.LookRotation(b - a), gizmoSize * 15, EventType.Repaint);
}
}
}
void DebugHoleDetection()
{
for (int i = 0; i < polygons.Count; i++)
{
for (int j = 0; j < polygons[i].edge.Count; j++)
{
Vector3 a = polygons[i].edge[j];
Vector3 b = polygons[i].edge[(j + 1) % polygons[i].edge.Count];
Debug.DrawLine(a, b, colors[i]);
}
for (int j = 0; j < polygons[i].holes.Count; j++)
{
for (int k = 0; k < polygons[i].holes[j].Count; k++)
{
Vector3 a = polygons[i].holes[j][k];
Vector3 b = polygons[i].holes[j][(k + 1) % polygons[i].holes[j].Count];
Debug.DrawLine(a, b, colors[i]);
}
}
}
}
private Color[] colors;
public Color RandomColor()
{
return UnityEngine.Random.ColorHSV(0f, 1f, 1f, 1f, 1f, 1f);
}
public static void DistinctRandomColors(int colorCount, out Color[] colors, Color initColor, bool shuffle = false)
{
colors = new Color[colorCount];
colors[0] = initColor;
float hue, saturation, value;
Color.RGBToHSV(initColor, out hue, out saturation, out value);
float normalizedHue = Mathf.Clamp01(hue);
for (int i = 1; i < colorCount; i++)
{
float angle = (((360 * colorCount) - (360 * i)) / colorCount);
float normalized = (angle / 360) + normalizedHue;
Color newColor = Color.HSVToRGB(normalized % 1, saturation, value);
colors[i] = newColor;
}
if (shuffle)
{
for (int i = colors.Length - 1; i > 0; i--)
{
int j = UnityEngine.Random.Range(0, i + 1);
var temp = colors[i];
colors[i] = colors[j];
colors[j] = temp;
}
}
}
public void Shuffle()
{
for (int i = colors.Length - 1; i > 0; i--)
{
//int j = Mathf.Floor(Math.Random() * (i + 1));
int j = UnityEngine.Random.Range(0, i + 1);
var temp = colors[i];
colors[i] = colors[j];
colors[j] = temp;
}
}
public bool InfiniteLoopFailsafe(int iterator, int maxAllowance)
{
if (iterator >= maxAllowance)
{
Debug.LogError("Infinite Loop Detected");
return true;
}
return false;
}
#endregion
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment