   2D Collision between two polygons
  I'm trying to write a little vector based game and I am getting quite stuck on the collision. I've essentially created my own 3D space in my game (using c#, yes, c#!), defined my own 3D vector, 3D world space all for the camera movement to allow for zooming in and out and panning. The actual game takes place in 2D even though all sprites have 3D world coordinates.The problem I'm facing is that I have polygons that serve as IMMOVABLE objects (map boundary and obstacles) in the game. The player controls a single "ship" and it needs to collide with these objects. The sides of the polygon can be straight lines or angled and I need to detect a collision and have the "ship" bounce back depending on the slope of the polygon edge and the angle at which the ship collides with the polygon.All I know at the moment is the change in velocity along the x and y axis of the ship travelling in a certain direction (angle of movement).I could do with some serious help!! I know I need to determine normals and use dot products, etc. A whole lot of stuff I know about but can't seem to figure out how to string it all together in code. Any help will be greatly appreciated.   
  How is your polygon represented?And what do you mean with angled instead of straight line? Archs?The simple way would be to split it up into lines between 2 vertices.You should have a 2D vector class too. That would make some equationssimpler and more efficient.;  Thanks for the reply Spynacker.The polygons are stored as a list of points. My polygons don't have curved edges. All edges are straight lines but the edges of the polygons may be sloped (see example attempt at drawing :)):  /\_______ /    |____/|\    ___________| \  /  \/I also have a 2D point class that I can use as my 2D vector.   ;  The attempt to draw a polygon in my previous reply didn't turn out so well. Just keep in mind that the polygons only have straight edges that can be vertical along the x axis, or along the y axis or they could be sloped where point1.x != point2.x and point1.y != point2.y. I hope that makes sense.   ;  http://local.wasp.uwa.edu.au/~pbourke/geometry/insidepoly/I know link-answers are annoying but these tests look pretty good, and I used something similar when I was working on an engine that used lots of 2D textured polygons.  I'm about to start working on something along these lines as well, good information to know.   ;  Thanks for link zerothrillz. I am able to determine if a point lies within a polygon, it's how I tell if a collision has occurred. As a matter of fact, I'm actually using Randolph Franklin's method mentioned in the link you sent me. My problem is computing the new direction of the player's ship AFTER I've determined the collision. What I do know is that I need to know more than a point being inside a polygon. In other words, I need to know which edge of the polygon the player has collided with and then determine the new direction of the player there after.I have read a lot but I can't seem to get it figured out in my head and actually transmit it to code. If you have any code snippets that collide two objects and then determines the movements after the collision, that would be great.   ;  What you are looking for is the SAT (separating axis theorem) :)   ;  I assume your 2D plane is not oriented weird in the 3D space but mapsfor example to the x/y-plane. Under this circumstance the x and y coordinatesof the polygon in 3D space directly would represent your x and y coordinates in2D space.At first we have given the Ships position p and velocity v as 2D vectors:Every point d on our movement ray is given by: d = p + lambda * vNow we want to check wether the ship will collide with a line that is definedby the points A and B with the 2D vectors a and b pointing to them.First we want to find the intersection between the movement ray of your Ship andthe line A to B extruded into infinity, because that is simpler.1. The "normal" n of the line:2dvector 2dnormal(2dvector x){  2dvector result();  result.x = -x.y;  result.y =  x.x;  return result;}//Get the normalized normal of line ABn = norm(2dnormal(b-a));2. The intersection is equated with Hesse normal form:It is said that:<n,x1> = <n,x2> = p for every point of the line. (<n,x> is the dot-product of n and x)So we replace x1 with a or b and x2 with d of our movement ray:<n, a> = <n, d> = <n, p + lambda * v><n, a> = <n, p> + <n, lambda * v><n, a> = <n, p> + lambda * <n, v>lambda = (<n, a> - <n, p>)/<n, v>Now we have a lambda that says how far away in velocity steps the intersectionis. As you notice <n, v> should not be zero because of the division. This valuebeing zero would mean that the line and the movement ray are parallel.If lambda is less than zero the ship moves away from the line and we do not haveto care about a collision with this line.If there will be a collision we need to know if it will happen in the next turn.This is easy as we only have to check if lambda is less or equal to the delta time of your next step. If not the collision will not take place and we can ignore this line because no collision will take place.If lambda says we will collide in the next step than we should look if the shipwill hit the infinite line of A and B within A and B. When it does not we again can ignore this line.To check if the intersection lies within A and B following will apply:At first we want to know the intersection point x:x = p + lambda * vNow to determine if x lies between A and B:If <x-a, x-b>  is negative, x lies within A and B  is zero, x lies on A or B  is positive, x lies out of A and BNow that we know a collision takes place or not we move to getting the newdirection the ship will be heading after collision.The simple reflection law will do good.In vector terms the new velocity vn will be:vn = v - 2 * <n, v> * nwhere vn and n will have the same length or represent the same speedAnd always remember that n is normalized!Hm that nearly was a tutorial and I hope the right place.If you have any questions or there are mistakes in my equations pleasepm me so I can correct it.   ;Quote:Hm that nearly was a tutorial and I hope the right place.If you have any questions or there are mistakes in my equations pleasepm me so I can correct it.Doesn't your proposed solution presuppose that the ship can be represented as a point? Since the title of the thread is '2D collision between two polygons', I would guess that the ship is represented as a polygon. If that is the case, then line intersection tests won't do you much good here; rather, it's the SAT that you want (as oliii mentioned previously).   ;  Thanks for the detailed post Spynacker. I will try implement this and see if it works.Jyk, if you think about it, a polygon is just a bunch of points joined together. So technically, I could check the collisions with Spynacker's method by checking if the points of the ship intersects with any edge of any polygon (within my camera's view for optimization). The SAT method is great as well and I'm going to try both methods and see which one works best in terms of speed and ease of implementation.Thanks for the posts guys. If anyway comes across more useful stuff, please feel free to share :)   