The following reply was made to PR mod_imap/1771; it has been noted by GNATS.
From: Konstantin Morshnev <[EMAIL PROTECTED]>
To: [EMAIL PROTECTED], [EMAIL PROTECTED]
Cc: Subject: Re: mod_imap/1771: invalid processing of poly borders
Date: Sat, 07 Feb 1998 18:23:42 +0300
[EMAIL PROTECTED] 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
