ANN Testing for overlapping polygons

[Alex Tweedly]

Jim Hurley wrote:

> [Hope this isn't a repeat. According to my ISP this was not delivered. 
> Perhaps the problems that Heather warned of over the weekend.]
>
I've only seen one copy.

> Well, I said it was grubby, but here it is, a stack which test for 
> overlap between polygons.
>
That's not at all grubby - that's really neat, very nice job.

It does demonstrate that the built-in function "within" is fairly 
inexact (since it's defined as "whether a point is within the clickable 
part of a shape" this inexact-ness is probably intentional). If you 
position the blue shape above the red one such that the approx mid-point 
is above the top point of the red one, and slowly drag it down, you find 
that "point is within" becomes true when there is still a clearly 
visible yellow gap between the two shapes - so it's clear that the RR 
test doesn't involve checking pixel colours..

> I was wondering how RR tests for within(). One way would be to draw a 
> line from the point in question to the edge of the screen. If there 
> are an odd number of intersections with the lines of the polygon, then 
> the point is inside, otherwise it is outside.

Either that or decide if it is "above" or "below", and "left" or "right" 
of each directed line segment in turn; only if both pairs match is it 
within.  Both of those allow for easy "inexact" checks, so they could 
use either.

> But how does RR paste a color into an opaque polygon, how does it know 
> which pixels are inside and which outside the polygon? It doesn't test 
> for all points, of which there are an infinite number, but it must 
> know which pixels (integer points) are located inside--this generally 
> would be sufficient to test for overlap--and collision. Maybe this 
> would be a request feature RR might consider. The hard part of overlap 
> and collision may already be in the engine.
>
Standard algorithm uses a "scan" pattern over the bounding rectangle, 
toggling on/off as the scan crosses (or touches) the edges. I don't know 
if that'll be within the engine or if they'll use system-provided 
primitives to handle filled polygons.

Either way, since there's already a "point within shape" test, it would 
be a nice feature to extend that to "overlap shapes".

(Actually, I'd prefer that "intersect" be changed to mean what it says 
(i.e. two shapes overlap), and a new term be devised for "rectangles 
overlap", but I guess that could break too many existing stacks :-)


-- 
Alex Tweedly       http://www.tweedly.net



-- 
No virus found in this outgoing message.
Checked by AVG Anti-Virus.
Version: 7.0.323 / Virus Database: 267.8.2/29 - Release Date: 27/06/2005