is within ... polygon shape?

[Jim Hurley]

>
>Message: 15
>Date: Sat, 25 Jun 2005 00:10:18 +0100
>From: Alex Tweedly <alex at tweedly.net>
>Subject: Re: is within ... polygon shape?
>To: How to use Revolution <use-revolution at lists.runrev.com>
>Message-ID: <42BC92DA.6070200 at tweedly.net>
>Content-Type: text/plain; charset=ISO-8859-1; format=flowed
>
>Jim Hurley wrote:
>
>>
>>  Take a look at:
>>
>>  go stack url "http://home.infostations.net/jhurley/CollidingPolygons.rev"
>>
>Sorry, Jim, but that doesn't work for all polygons. For example (excuse
>the ascii drawing ....)
>
>
>         111111111
>         1       1
>         1       1
>    22222222222222222222222
>    2                     2
>    22222222222222222222222
>         1       1
>         111111111
>
>Even for 2  rectangles, it doesn't always work.  If I remember
>correctly, the most effective algorithm for overlap depends on edge
>intersections (with a special case test for one polygon entirely within
>the other). Any two polygons that overlap will have at least one case
>where their edges intersect - though you need to deal with the special
>cases where the edges touch; you can then test the mid-point of the
>edges adjacent to the point of touch to determine if they are within or
>outwith the other polygon (or alternatively, test the points 1 delta
>away from the point of touch - but then you need to be very careful
>about precision and rounding errors).
>
>  And even then, you have some weird corner cases involved in
>self-reflexive polygons - far less Rev's "invisible edge" polygons which
>can produce disjoint areas.
>
>(Is self-reflexive the right term ?  polygons that overlap themselves, like
>
>      11111
>      1   1
>   111111111111111
>   1             1
>   111111111111  1
>       1  1   1  1
>       1  1   1  1
>       1  11111  1
>       1         1
>       11111111111
>
>
>You need to determine whether the points in the self-overlap area are
>within the polygon or not ...  and I can't remember which is the "right"
>decision, i.e. the one that makes the problem easier.
>
>--
>Alex Tweedly       http://www.tweedly.net
>
>


Alex,

Your ascii figures didn't translate very well in my email app.

But I think I understand the first diagram, it represent a somewhat 
different problem from the collision problem. It would not be 
possible to achieve this configuration without one or more apexes 
entering the other polygon.

What you say is quite true if the problem is to detect any 
overlapping area not just a collision. Messy. Even worse, grubby.

Jim