I’ve written a Polygon Union algorithm, and this is an excerpt from it:
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;
}
}
}
}
}
I feel like it is a bit clunky, and am wondering if there is a better way to write it?
I assume you have one or two more nested loops around this iterating over vertices in other polygon. This will scale badly as number of vertices increase. Brute force approach like this might be fine for <100 vertices. But for anything bigger you will probably need an appropriate algorithm.
Polygon intersection problem can be solved using sweep line algorithm. Note that it’s actually single algorithm but a an approach which can be used in a couple of different problems (line intersection, polygon intersection, Voronoi diagram and others) . Sweep line based algorithms solving specific problems often have their own name. But it’s a good starting point when starting to search for information. So don’t be confused if you search for it and it seems that results are unrelated to what you are looking for.
It is a moderately complex algorithm. Quite a bit more difficult to implement than good A*. So unless you are a very good programmer or average programmer with experience in implementing complex algorithms, you might want to consider looking for appropriate asset or C# library.
