3
$\begingroup$

...

I'm working on a programming project and got to the point where I need to find how much is the blue square overlapping each of the other 9 squares. The squares' sides(including the blue one's) are 1-length. The blue square is tilted by the alpha angle. I've thought of some trivial approaches to the problem, but they are severely inefficient, and due to the fact that I have to run this test around 784 X 42000 times, an analytic solution would be best. Also, I also thought of checking each of the 2 triangles in the blue square to the triangles in the other squares, but that means 36 checks, which is quite slow.

I would like to get something like a 3x3 matrix with the areas of the overlapping regions (some of the values in the matrix may be 0).

Assuming we know the coordinates of A, B, C, D and the angle alpha (we would only need to know two of them actually), is there a more efficient approach to finding the area of the overlapping parts (and filling the matrix)?

$\endgroup$
  • $\begingroup$ If you have to run such tests so many times, you must be using the wrong algorithm. $\endgroup$ – user21820 Jul 4 '15 at 11:14
  • $\begingroup$ The nature of my objective makes it so that the overlapping areas test has to be executed 784 times for each example, and I've got 42000 of them. It is a preprocessing stage and, therefore, is allowed to take some time, although not extremely much. $\endgroup$ – Lighthink Jul 4 '15 at 14:49
  • $\begingroup$ My point is that your chosen algorithm must be the wrong one, meaning that there are far more efficient ways of achieving what you want to do, in which case you are asking us to solve a problem that shouldn't exist in the first place. $\endgroup$ – user21820 Jul 4 '15 at 15:03
  • $\begingroup$ Here's what it looks like: I have 42000 28x28 pixels images that are tilted by some angle (different for each image) I have computed. I have to rotate each of these images by -angle. So, pixel ( x, y ) transforms into ( ( x, y ) * rotationMatrix( -angle ) ). The transformed pixel is the blue square. The other squares are the pixels that will form the resulting image. Now, I need to distribute the value of the blue pixel to the pixels it overlaps. How much is every target pixel receiving, that's decided by the overlapping area. That's the whole problem, so if you have better ideas let me know. $\endgroup$ – Lighthink Jul 4 '15 at 15:33
  • 1
    $\begingroup$ Perhaps a formula like this one would help wiki $\endgroup$ – Michael Burr Jul 5 '15 at 20:16
1
$\begingroup$

As I saw I probably won't be getting an answer I took a more naive path. I sampled the blue square by 100 points (10x10) and just approximated the overlapping areas using the number of points contained by the other squares. It proved to be precise enough, and yielded pretty good results for my task.

I know it's not a real mathematical solution to the problem, but maybe it will help other people facing the same task.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.