Hi everyone.I’ve drained my brain work on the polygon detection these days.
Finally, I failed. The following is my research result.
First, the biggest rumor:
When a point of a polygon is inside another polygon, they must be intersected and vise versa.
A picture to beat this down
So, it was a joke.
Then I move to step 2.
As the upon situation.We may think if the lines were intersected, they should be intersected!
Let’s verify its correction by picture
See, lines were intersected, but the polygons were not!
You may say: what? this is special. The intersection point was on the boundary.
So, just except it should work!
So the conclusion should be:
If the lines were intersected and the intersected point were all not just on the boundary.The polygon intersected.
Yeah seems the conclusion is right.But not enough to verify all the polygon insection
Because this conclusion excluded a right situation.
For example
So, This time, line intersection was on the boundary. And as the upon conclusion.We can not sure whether it was
intersected or not intersected. Because they are totally the same situation but totally the different result.
So I don’t think there is an easy way to differentiate these two situations.
But some people start to say:
Hey, dude. I found the difference of these two situations. The second situation has " rect area collided"
Take a look at this situation, the rect area even the grid area of both polygon were all intersected.
But they are complete damn has no intersection.
And also they got line intersection and point on the boundary.
So Let’s give up to judge polygon intersect or not by line intersection for a while.
Let’s just try to detect some special first.
First,all point inside another polygon. they intersected
Then I faced the same problem
When the intersected points were on boundary, no way to judge whether is inside(pic 2) or just include(pic 3)
So upon all, I think it was really extremely hard to judge polygon intersection by point and lines
Here are several algorithms are used for the upon testing
This is check line intersection
public static int GetIntersection(Vector2 a, Vector2 b, Vector2 c, Vector2 d, ref Vector2 intersection)
{
if (Mathf.Abs(b.x - a.y) + Mathf.Abs(b.x - a.x) + Mathf.Abs(d.y - c.y) + Mathf.Abs(d.x - c.x) == 0)
{
if (c.x - a.x == 0)
{
//Debug.Log("ABCD not same！");
}
else
{
//Debug.Log("AB same，CDsame，AC different！");
}
return 0;
}
if (Mathf.Abs(b.y - a.y) + Mathf.Abs(b.x - a.x) == 0)
{
if ((a.x - d.x) * (c.y - d.y) - (a.y - d.y) * (c.x - d.x) == 0)
{
//Debug.Log("A、Bsame,on CD！");
}
else
{
//Debug.Log("A、Bsame not On CD");
}
return 0;
}
if (Mathf.Abs(d.y - c.y) + Mathf.Abs(d.x - c.x) == 0)
{
if ((d.x - b.x) * (a.y - b.y) - (d.y - b.y) * (a.x - b.x) == 0)
{
//Debug.Log("C、Dsame,on AB");
}
else
{
//Debug.Log("C、Dsame not on AB");
}
}
if ((b.y - a.y) * (c.x - d.x) - (b.x - a.x) * (c.y - d.y) == 0)
{
//Debug.Log("parrall");
return 0;
}
intersection.x = ((b.x - a.x) * (c.x - d.x) * (c.y - a.y) - c.x * (b.x - a.x) * (c.y - d.y) + a.x * (b.y - a.y) * (c.x - d.x)) / ((b.y - a.y) * (c.x - d.x) - (b.x - a.x) * (c.y - d.y));
intersection.y = ((b.y - a.y) * (c.y - d.y) * (c.x - a.x) - c.y * (b.y - a.y) * (c.x - d.x) + a.y * (b.x - a.x) * (c.y - d.y)) / ((b.x - a.x) * (c.y - d.y) - (b.y - a.y) * (c.x - d.x));
if ((intersection.x - a.x) * (intersection.x - b.x) <= 0 && (intersection.x - c.x) * (intersection.x - d.x) <= 0 && (intersection.y - a.y) * (intersection.y - b.y) <= 0 && (intersection.y - c.y) * (intersection.y - d.y) <= 0)
{
if (intersection != a && intersection != b && intersection != c && intersection != d)
{
Debug.Log("Intersect at" + intersection.x + "," + intersection.y + ")！");
return 1; //'intersect
}
else
{
Debug.Log("Intersect at(" + intersection.x + "," + intersection.y + ")！but on endpoints");
return 0;
}
}
else
{
//Debug.Log("on extended place(" + intersection.x + "," + intersection.y + ")！");
//print("A:" + a);
//print("B:" + b);
//print("C:" + c);
//print("D:" + d);
return -1; //'intersect but not on the segment
}
}
This is check whether dot is inside a polygon.
This function got a problem.When the dot is on the boundary.The result can be yes can be no.
There is no nice way I found to solve this boundary problem.
public static bool PositionPnpoly(int nvert, List<Vector2> vert, float testx, float testy)
{
int i, j, c = 0;
for (i = 0, j = nvert - 1; i < nvert; j = i++)
{
if (((vert[i].y > testy) != (vert[j].y > testy)) && (testx < (vert[j].x - vert[i].x) * (testy - vert[i].y) / (vert[j].y - vert[i].y) + vert[i].x))
{
c = 1 + c;
}
}
if (c % 2 == 0)
{
return false;
}
else
{
return true;
}
}
OKOKOK.
This is all my research report.As I said, I failed finally.
So anyone can help me to give some idea to write a polygon intersection check.
Thanks!