From: Kent L. <kln...@st...> - 2004-02-24 01:54:31
|
>[Please use the subject line!] Ops sorry about that. I did=B4nt add a subject at this message either in= case=20 that someone views it in "thread mode" (but i will in the future, it was a= =20 mistake only). >Kent Larsson wrote: >>Wich is the best (fastest) way to check if to rectangles intersect based= =20 >>on knowledge about the 4 coordinates of the corners in each rectangle=20 >>only? (se example below) > >I'll use r1.x1 for the left of the first rectangle, r2.y2 for the bottom=20 >of the second rectangle, etc. > >It is easiest to test the opposite: they intersect if and only if one is=20 >NOT right of, left of, above, or below the other, i.e.: > > r1 and r2 intersect, if and only if > !(r1.x1>r2.x2 || r2.x1>r1.x2 || r1.y1>r2.y2 || r2.y1>r1.y1) > >Depending on how you want to treat boundary cases, you may have to replace= =20 >some > by >=3D. > >Now, this can be optimized a bit more. Code that branches (like || does,=20 >since it uses short-circuit evaluation) may be slow on modern processors,= =20 >and integer operations are fast. Since the short-circuit evaluation is not= =20 >necessary for the code to be correct, and boolean true in C is represented= =20 >as any non-zero integer, the above is actually equivalent to: > > !((r1.x1>r2.x2) | (r2.x1>r1.x2) | (r1.y1>r2.y2) | (r2.y1>r1.y1)) > >I.e., we may replace boolean or by binary or. This can be made even faster= =20 >because a>b is the same as b-a>0, which is the same as "the sign bit of=20 >b-a is set". We can "or" all the sign bits into one before testing, and=20 >thus the expression above is equivalent to > > !(((r2.x2-r1.x2) | (r1.x2-r2.x1) | (r2.y2-r1.y1) | (r1.y1-r2.y1)) &=20 > 0x8000000) > >Here, 0x80000000 is the sign bit, assuming 32 bit ints. Thus, we reduced=20 >the problem to eight integer operations, which are likely to be pairable=20 >(i.e., the processor can execute them in parallel). That should be about=20 >as fast as it gets. The same should work for floating point numbers, using= =20 >integer arithmetic, but it may be slower depending on the situation (you=20 >don't want to move things between floating point registers and integer=20 >registers). > >Sven A very good and informative answer! Thanks a lot! Best regards, Kent |