Intersection fomula

Hm, not sure if this could be homework or no, so I just give a general hint:

Your problem can be solved pretty easy by dividing it into some (2 or 3, depends on view) sub problems (divide and conquer).

to find the sub problems just peer at your picture and describe for each vertex the class it belongs to. then try to generalize.

for all sub problems there are many solutions on the web.

It''s not homework, it''s for a game I''m creating. I don''t see how divide and conquer would help this. I just need to know if there is some sort of algorithm that can find the intersection, as in where the two polygons are touching, like in the picture, and create a new polygon with just those points. I know how to create the new one I just don''t know exactly how to find the points which should be included.

Test to see if the 4 vertices of the square lie inside the triangle. Test to see if the 3 vertices of the triangle lie inside the square. Take each of the 4*3 = 12 pairs of edges (where one comes from the square and the other from the triangle) and see if they intersect. If so, add the points of intersection to the new polygon. Take the union of all those points and uncross any edges to get the vertices in the right order, and you''re done.