Quadrangle intersection algorithm

I'm currently writing a game (2D with OpenTK) in which there is a lot of rotation, and with it comes that I sometimes need to get the intersection between these lines/shapes:

I know the rotation (in degrees) of both of them, and therefore I know the position of all the vertices in both shapes.

The algorithm needs to give me a bool on whether they intersect, or better yet, the coordinates of the intersections.

I have written my own algorithm, which scrolls through the sides of the first box, gets the formula for each side and compares them to the formulas of the lines of the second box. Now, this doesn't work when the lines are upright (slope of float.Infinity or float.NegativeInfinity), is a pain to debug and is far from fast, so I need a better one!

Any suggestions?

Answers


I ended up using the SAT method, as suggested by Nickon, thanks a bunch mate!


Need Your Help

Validating xml against relax ng in ANSI C

c xml relaxng

Is it possible to validate an xml file against a Relax NG schema in ANSI C? I have come across this library called libxml2 but all help I could get from it is with respect to how to parse an xml fi...

Watir Webdriver in IE8, click link, event seems to keep firing for ever

ruby windows-7 selenium internet-explorer-8 watir-webdriver

I've replicated this Watir Webdriver problem in Ruby 1.9.2 with IE8 and 1.9.3 with IE9; it does not seem to happen if I use Chrome or Firefox. The OS is Windows 7 (64 bit).

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.