A simple way to calculate the intersection point of two polygons in C #

Question

I have two polygons, defined as a list of vectors, I was able to write procedures for converting and intersecting these two polygons (see box 1 below). Using the intersection of the line, I can find out if they collided, and wrote the working function Collide ().

This should be used in a time-varying game with a variable pitch and therefore (as shown below) in frame 1, the right polygon does not collide, it is absolutely normal for frame 2 so that the polygons are to the right of each other, the right polygon is moved to the left.

My question is: what's the best way to figure out the moment of intersection? In the example, suppose that in frame 1, the right polygon is at X = 300, Frame 2 it has moved -100 and is now at 200, and that all I know from Frame 2 time is that it was 300, now it's 200 What I want to know is when he really came across, at a value of X, there were probably around 250 here.

I prefer to find the C # source code to solve this problem. Maybe there is a better way to approach this for games?

Answer 1

I would use the dividing axis theorem as described here:

• Metanet Tutorial
• Wikipedia

Then I would test the sweep or use multisampling , if necessary.

GMan here on StackOverflow wrote an example implementation on gpwiki.org .

This may be redundant for your use case, but it handles polygons of any order. Of course, for simple bounding rectangles this can be done much more efficiently by other means.

Answer 2

I'm also not a mathematician, but one possible, although a rude decision is to run a mini-simulation.

We call a moving polygon M and a stationary polygon S (although for S it is not required that it is actually stationary, the approach should work equally independently). Let us also name two frames that have F1 for the previous one, and F2 for the later one, according to your diagram.

If you were to move the polygon M back to its position in F1 with very small increments until they no longer intersect, then you will have a place for M in which it “just” intersects, that is, the previous location before they will cease to overlap in this simulation. The intersection in this “just” intersecting place should be very small - small enough so that you can see it as a point. Call this intersection polygon I.

To treat me as a point, you can select its vertex closest to the center point M in F1: this vertex has the best chance of being outside S during a collision. (There are many other possibilities for interpreting I as a point from which you could experiment, which might have better results.)

Obviously, this approach has some disadvantages:

• The simulation will be slower for high speeds M, since the distance between its locations in F1 and F2 will be greater, additional modeling steps will be required. (You could solve this by having a fixed number of simulation cycles regardless of the speed M, but this would mean that the accuracy of the result will differ for faster and slower moving bodies.)
• The “step” size in the simulation should be small enough to get the required accuracy, but smaller step sizes will obviously have higher calculated costs.

Personally, without the necessary mathematical intuition, I would first go with this simple approach and try to find a mathematical solution as an optimization later.

Answer 3

If you have the ability to determine if two polygons overlap, one idea might be to use a modified binary search to determine where these two hits are. Start by dividing the time interval in half and viewing if two polygons intersect at a midpoint. If so, recursively search the first half of the range; if not, find the other half. If you specify a certain tolerance level at which you no longer need small distances (for example, at the pixel level), then the execution time of this approach is O (log D / K), where D is the distance between the polygons and K is the cutoff threshold. If you know which point will ultimately go into the second polygon, you can quickly detect this collision.

Hope this helps!

Answer 4

For a fairly general solution and assuming ...

• no polygons intersect at time = 0
• at least one polygon intersects another polygon at time = t
• and you are happy to use the C # clipping library (e.g. Clipper )

then use the binary approach to get the intersection time with ...

double tInterval = t; double tCurrent = 0; int direction = +1; while (tInterval > MinInterval) { tInterval = tInterval/2; tCurrent += (tInterval * direction); MovePolygons(tCurrent); if (PolygonsIntersect) direction = +1; else direction = -1; } 

Answer 5

Well, you can see that this is always the point of one of the polygons, which falls in the direction of the other first (or another point - but this is almost the same) - a possible solution would be to calculate the distance of the point from other lines in the direction of movement. But I think it would end up pretty slow.

I suppose that the normal distances between frames are so small that they don’t import and really know exactly where he got in - some small intersections will not be visible, and yet there will be a rebound or explosion in any case - isn’t that? :)