Re: mod_imap/1771: invalid processing of poly borders (fwd)

[Dean Gaudet <dg...@arctic.org>]

I keep thinking "yeah I'll go through the math on this one" and never have
the time.  If someone else has the time ... the issue is that the current
mod_imap does not include the borders of polygons in a region, but does
include the borders of rectangles.  This modification should make it
include the borders. 

Dean

---------- Forwarded message ----------
Date: Sat, 07 Feb 1998 18:23:42 +0300
From: Konstantin Morshnev <mo...@design.ru>
Organization: WebDesign
To: dgaudet@hyperreal.org, apbugs@Apache.Org
Subject: Re: mod_imap/1771: invalid processing of poly borders

dgaudet@hyperreal.org wrote:
> 
> Synopsis: invalid processing of poly borders
> 
> State-Changed-From-To: open-analyzed
> State-Changed-By: dgaudet
> State-Changed-When: Sat Feb  7 03:40:07 PST 1998
> State-Changed-Why:

> Yes please send your patch when you're happy with it, just
> reply to this email and include it.  Thanks!

Here it goes:

I've made another (simple, sometimes bit faster, sometimes bit slower)
realization of the algorithm,
and add line (second "if" statement), which tests that point belongs to border,
returning "true" in that case.

This realization:
1. More simple.
2. Does not uses "/".
3. Fixes "border bug".
4. It's not so optimized for big and convex polygon processing (what about
non-convex?), but it's the same linear algorithm.

-------------
#define min(a,b) (((a)>(b))?(b):(a))
#define max(a,b) (((a)>(b))?(a):(b))

static int pointinpoly(const double point[2], const double pgon[MAXVERTS][2])
{
    int i, numverts, crossings = 0;
    double x = point[X], y = point[Y];
    for (numverts = 0; pgon[numverts][X] != -1 && numverts < MAXVERTS;
numverts++);

    for (i = 0; i < numverts; i++){
        double x1=pgon[i][X],
               y1=pgon[i][Y],
               x2=pgon[(i + 1) % numverts][X],
               y2=pgon[(i + 1) % numverts][Y],
               d=(y - y1) * (x2 - x1) - (x - x1) * (y2 - y1);
        if ((y1 >= y) != (y2 >= y)) crossings+=y2 - y1 >= 0 ? d >= 0 : d <= 0;
        if (!d && min(x1,x2) <= x && x <= max(x1,x2) && min(y1,y2) <= y && y <=
max(y1,y2)) return 1;
    }
    return crossings & 0x01;
}
-------------

WBR, MoKo