JavaScript "pixel"-perfect collision detection for rotating sprites using math (probably linear algebra)

Question

I'm making a 2D game in JavaScript. For it, I need to be able to "perfectly" check collision between two sprites which have x/y positions (corresponding to their centre), a rotation in radians, and of course known width/height.

After spending many weeks of work (yeah, I'm not even exaggerating), I finally came up with a working solution, which unfortunately turned out to be about 10,000x too slow and impossible to optimize in any meaningful manner. I have entirely abandoned the idea of actually drawing and reading pixels from a canvas. That's just not going to cut it, but please don't make me explain in detail why. This needs to be done with math and an "imaginated" 2D world/grid, and from talking to numerous people, the basic idea became obvious. However, the practical implementation is not. Here's what I do and want to do:

What I already have done

In the beginning of the program, each sprite is pixel-looked through in its default upright position and a 1-dimensional array is filled up with data corresponding to the alpha channel of the image: solid pixels get represented by a 1, and transparent ones by 0. See figure 3.

The idea behind that is that those 1s and 0s no longer represent "pixels", but "little math orbs positioned in perfect distances to each other", which can be rotated without "losing" or "adding" data, as happens with pixels if you rotate images in anything but 90 degrees at a time.

I naturally do the quick "bounding box" check first to see if I should bother calculating accurately. This is done. The problem is the fine/"for-sure" check...

What I cannot figure out

Now that I need to figure out whether the sprites collide for sure, I need to construct a math expression of some sort using "linear algebra" (which I do not know) to determine if these "rectangles of data points", positioned and rotated correctly, both have a "1" in an overlapping position.

Although the theory is very simple, the practical code needed to accomplish this is simply beyond my capabilities. I've stared at the code for many hours, asking numerous people (and had massive problems explaining my problem clearly) and really put in an effort. Now I finally want to give up. I would very, very much appreciate getting this done with. I can't even give up and "cheat" by using a library, because nothing I find even comes close to solving this problem from what I can tell. They are all impossible for me to understand, and seem to have entirely different assumptions/requirements in mind. Whatever I'm doing always seems to be some special case. It's annoying.

This is the pseudo code for the relevant part of the program:

function doThisAtTheStartOfTheProgram()
{
    makeQuickVectorFromImageAlpha(sprite1);
    makeQuickVectorFromImageAlpha(sprite2);
}

function detectCollision(sprite1, sprite2)
{
    // This easy, outer check works. Please ignore it as it is unrelated to the problem.
    if (bounding_box_match)
    {
        /*

            This part is the entire problem.
            I must do a math-based check to see if they really collide.

            These are the relevant variables as I have named them:

                sprite1.x
                sprite1.y
                sprite1.rotation // in radians
                sprite1.width
                sprite1.height
                sprite1.diagonal // might not be needed, but is provided

                sprite2.x
                sprite2.y
                sprite2.rotation // in radians
                sprite2.width
                sprite2.height
                sprite2.diagonal // might not be needed, but is provided

                sprite1.vectorForCollisionDetection
                sprite2.vectorForCollisionDetection

            Can you please help me construct the math expression, or the series of math expressions, needed to do this check?
            To clarify, using the variables above, I need to check if the two sprites (which can rotate around their centre, have any position and any dimensions) are colliding. A collision happens when at least one "unit" (an imagined sphere) of BOTH sprites are on the same unit in our imaginated 2D world (starting from 0,0 in the top-left).

        */

        if (accurate_check_goes_here)
            return true;
    }

    return false;
}

In other words, "accurate_check_goes_here" is what I wonder what it should be. It doesn't need to be a single expression, of course, and I would very much prefer seeing it done in "steps" (with comments!) so that I have a chance of understanding it, but please don't see this as "spoon feeding". I fully admit I suck at math and this is beyond my capabilities. It's just a fact. I want to move on and work on the stuff I can actually solve on my own.

To clarify: the 1D arrays are 1D and not 2D due to performance. As it turns out, speed matters very much in JS World. Although this is a non-profit project, entirely made for private satisfaction, I just don't have the time and energy to order and sit down with some math book and learn about that from the ground up. I take no pride in lacking the math skills which would help me a lot, but at this point, I need to get this game done or I'll go crazy. This particular problem has prevented me from getting any other work done for far too long.

I hope I have explained the problem well. However, one of the most frustrating feelings is when people send well-meaning replies that unfortunately show that the person helping has not read the question. I'm not pre-insulting you all -- I just wish that won't happen this time! Sorry if my description is poor. I really tried my best to be perfectly clear.

Okay, so I need "reputation" to be able to post the illustrations I spent time to create to illustrate my problem. So instead I link to them:

Illustrations

1. (censored by Stackoverflow)
2. (censored by Stackoverflow)
3. 

OK. This site won't let me even link to the images. Only one. Then I'll pick the most important one, but it would've helped a lot if I could link to the others...

Answer 1

First you need to understand that detecting such collisions cannot be done with a single/simple equation. Because the shapes of the sprites matter and these are described by an array of Width x Height = Area bits. So the worst-case complexity of the algorithm must be at least O(Area).

Here is how I would do it:

Represent the sprites in two ways:

1) a bitmap indicating where pixels are opaque,

2) a list of the coordinates of the opaque pixels. [Optional, for speedup, in case of hollow sprites.]

Choose the sprite with the shortest pixel list. Find the rigid transform (translation + rotation) that transforms the local coordinates of this sprite into the local coordinates of the other sprite (this is where linear algebra comes into play - the rotation is the difference of the angles, the translation is the vector between upper-left corners - see http://planning.cs.uiuc.edu/node99.html).

Now scan the opaque pixel list, transforming the local coordinates of the pixels to the local coordinates of the other sprite. Check if you fall on an opaque pixel by looking up the bitmap representation.

This takes at worst O(Opaque Area) coordinate transforms + pixel tests, which is optimal.

If you sprites are zoomed-in (big pixels), as a first approximation you can ignore the zooming. If you need more accuracy, you can think of sampling a few points per pixel. Exact computation will involve a square/square collision intersection algorithm (with rotation), more complex and costly. See http://en.wikipedia.org/wiki/Sutherland%E2%80%93Hodgman_algorithm.