Math Question Triangles

[rifter1818]

Didnt know what section to post this in (i know it really isnt .net related at all) but someone on here has to be sufficiantly stronger at math than me and know this.

Say i have two triangles (in 2d in this case), both of which have known position,dimension,and velocities, how can i detect if they collide over a given time range. I tried to find a solution but i got lost

Triangle one

P0 P1 P2 moving at V0

Triangle two

P3 P4 P5 moving at V1

(P,P0-P5 are all points V0,V1 are velocity vectors)

closest i could realise is that with x being the time range i was looking for if there is a P such that

P = ((P1-P0)*v) + (P0 + xV0) + ((P2-P0)*u) = ((P4-P3)*w) + ((P5-P3)*z) + P3 + xV1

such that v,u,w,z,v+u,w+z are all (floats) between 0 and 1

really no idea how to solve this since there could be 0 or infinite P's (not quite infinite due to limited percision but you know what i mean) and there are 4 free variables and one range.

just going on a wild guess but im way off track any pointers?

[Iceplug]

Do you actually have a picture of the triangles that you are using?

Are the triangles of the same shape and size?

[rifter1818]

its more of a theoretical collision detection, so the triangles could be any shape,...

[Iceplug]

Well, if the triangles can be any shape, you'll probably have an easier time detecting if any of the segments forming the sides of the triangle intersect with any side on the other triangle. You know how to tell if two segments intersect, right?

[rifter1818]

Well' date=' if the triangles can be any shape, you'll probably have an easier time detecting if any of the segments forming the sides of the triangle intersect with any side on the other triangle. You know how to tell if two segments intersect, right?[/quote']

I suppose, you could break it down to if any of the points of one triangle are within the other triangle or if any of the sides intersect... That would be general enough right? (i can't think of any two intersecting triangles that dont fit that) (have to have the point check incase one triangle is contained compleatly within the other) thanks.

[Iceplug]

Checking where the points are probably won't help you out much. See the attachment: the triangles intersect, but neither triangle contains points from the other.

[Talyrond]

Hi guys, I hope you don�t mind me dropping in on this thread, as I will soon have to perform a similar task. My task is to see if Polygon A is completely within polygon B

 

The issues are similar, so here is my take on your problem.

 

Use a brut force algorithm to check if any intersections occur with the all sides of the triangles.

 

If no intersection occur, there are two possible situations:

 

1) One triangle is completely inside the other

2) Or one triangle is completely outside the other

 

So to check if one is inside the other:

 

Choose an arbitrary end point of one of the triangle sides and test if that point is inside or outside the other triangle. This could be accomplished by firing a ray from this point and checking the parity of the number of intersections, or compute winding numbers.

 

So now:

If there are any intersections, collision has occurred

If there are no intersections, but any arbitrary end point from a triangle is inside the other, collision has occurred.

 

Comments appreciated

[Iceplug]

Actually, an interesting point. I forgot that one triangle could be totally inside another.

 

Talyrond: That looks like a fine way of testing if a triangle is in another.

[Talyrond]

Actually, an interesting point. I forgot that one triangle could be totally inside another.

 

Talyrond: That looks like a fine way of testing if a triangle is in another.

 

 

Thanks for the reply Iceplug.

 

I found this excellent link that I shall use to implement the point test

 

http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm

 

Talyrond