Last active
June 9, 2022 06:08
-
-
Save FaffyWaffles/9c96ae577c11aae680a75f697038b696 to your computer and use it in GitHub Desktop.
Polygon Union Algorithm V1
This file contains hidden or 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
| public class UnionPolygonController : SerializedMonoBehaviour | |
| { | |
| public static List<List<Vector2>> UnionPolygon(List<List<Vector2>> uvPolygons) | |
| { | |
| List<List<Vector2>> newPolygons = new List<List<Vector2>>(); | |
| #region Fix Winding Order | |
| for (int i = 0; i < uvPolygons.Count; i++) | |
| { | |
| float sum = new float(); | |
| for (int j = 0; j < uvPolygons[i].Count; j++) | |
| { | |
| Vector3 a = uvPolygons[i][j]; | |
| Vector3 b = uvPolygons[i][(j + 1) % uvPolygons[i].Count]; | |
| sum += (b.x - a.x) * (b.y + a.y); | |
| } | |
| if (Mathf.Sign(sum) < 0) | |
| uvPolygons[i].Reverse(); | |
| } | |
| #endregion | |
| while (uvPolygons.Count > 0) | |
| { | |
| List<Vector2> newPolygon = new List<Vector2>(); | |
| int P = 0; //currentPolygon | |
| int I = 0; //currentIndex | |
| #region Setup First Point | |
| //Make sure starting point is not in any polygons | |
| for (int p = 0; p < uvPolygons.Count; p++) | |
| { | |
| if (p != P) | |
| { | |
| if (!CheckIndex(I, 0, uvPolygons[0].Count)) | |
| break; | |
| if (IsPointInPolygon(uvPolygons[0][I], uvPolygons[p])) | |
| { | |
| p = 0; | |
| I++; | |
| continue; | |
| } | |
| } | |
| } | |
| #endregion | |
| HashSet<int> hashedPolygons = new HashSet<int>(); | |
| while (true) | |
| { | |
| hashedPolygons.Add(P); | |
| if (newPolygon.Contains(uvPolygons[P][I % uvPolygons[P].Count])) | |
| break; | |
| Vector2 a = uvPolygons[P][I % uvPolygons[P].Count]; | |
| Vector2 b = uvPolygons[P][(I + 1) % uvPolygons[P].Count]; | |
| newPolygon.Add(a); | |
| bool intersected = false; | |
| Vector2 intersection = new Vector2(); | |
| Vector2 closestIntersection = new Vector2(); | |
| float closestDistance = new float(); | |
| int tp = new int(); | |
| int ti = new int(); | |
| for (int p = 0; p < uvPolygons.Count; p++) | |
| { | |
| if (p != P) | |
| { | |
| for (int i = 0; i < uvPolygons[p].Count; i++) | |
| { | |
| Vector2 x = uvPolygons[p][i]; | |
| Vector2 y = uvPolygons[p][(i + 1) % uvPolygons[p].Count]; | |
| if (AreLinesIntersecting(a, b, x, y, out intersection)) | |
| { | |
| if (newPolygon.Contains(intersection)) | |
| continue; | |
| if (!intersected) | |
| { | |
| closestIntersection = intersection; | |
| closestDistance = Vector3.Distance(a, intersection); | |
| tp = p; | |
| ti = i; | |
| intersected = true; | |
| } | |
| else if (Vector3.Distance(a, intersection) < closestDistance) | |
| { | |
| closestIntersection = intersection; | |
| closestDistance = Vector3.Distance(a, intersection); | |
| tp = p; | |
| ti = i; | |
| } | |
| } | |
| } | |
| } | |
| } | |
| if (intersected) | |
| { | |
| newPolygon.Add(closestIntersection); | |
| P = tp; | |
| I = ti; | |
| } | |
| I++; | |
| } | |
| if (hashedPolygons.Count == 1) | |
| { | |
| newPolygons.Add(new List<Vector2>(newPolygon)); | |
| uvPolygons.RemoveAt(0); | |
| continue; | |
| } | |
| for (int i = uvPolygons.Count - 1; i >= 0; i--) | |
| if (hashedPolygons.Contains(i)) | |
| uvPolygons.RemoveAt(i); | |
| if (uvPolygons.Count > 0) | |
| uvPolygons.Add(new List<Vector2>(newPolygon)); | |
| } | |
| return newPolygons; | |
| } | |
| public static bool CheckIndex(int i, int min, int max) | |
| { | |
| if (i >= min && i < max) | |
| return true; | |
| else | |
| return false; | |
| } | |
| public static bool AreLinesIntersecting(Vector2 A, Vector2 B, Vector2 C, Vector2 D, out Vector2 intersection) | |
| { | |
| 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 u_a and u_b are between 0 and 1 | |
| if (a > 0f && a < 1f && b > 0f && b < 1f) | |
| { | |
| isIntersecting = true; | |
| intersection = A + a * (B - A); | |
| } | |
| } | |
| return isIntersecting; | |
| } | |
| 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; | |
| } | |
| } |
Author
FaffyWaffles
commented
Jun 1, 2022
Author
Author
This is an old version.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment