Your going to like me....
The very clever stuff was taken almost exactly from http://www.faqs.org/faqs/graphics/algorithms-faq/ which is a superb repository of this sort of stuff.
I'm sure you could make a more compact version of this stuff, but many of these functions are used elsewhere in my code, so it made sense to keep them multi-purpose.
ptPoly is an array of the vertices of the polygon.
BOOL PointInPolygon (const CPoint *ptPoly, const int nPoints, const CPoint ptTest)
{
return (LineCrossesPolygon (ptPoly, nPoints, CPoint (-99999999, ptTest.y), ptTest) % 2) == 1;
}
int LineCrossesPolygon (const CPoint *ptPoly, const int nPoints, const CPoint ptA1, const CPoint ptA2)
{
int nPt, nCross = 0;
for (nPt = 0; nPt < nPoints; nPt++)
{
if (LinesIntersect (ptA1, ptA2, ptPoly [nPt], ((nPt + 1) == nPoints) ? ptPoly [0] : ptPoly [nPt + 1], NULL))
nCross++;
}
return nCross;
}
BOOL LinesIntersect (CPoint a, CPoint b, CPoint c, CPoint d, CPoint *ptIntersect)
{
if (Colinear (a,b,c,d))
return FALSE;
double rTop, rBot, sTop, sBot, r, s;
double Ax = a.x, Ay = a.y, Bx = b.x, By = b.y, Cx = c.x, Cy = c.y, Dx = d.x, Dy = d.y;
rTop = (Ay-Cy)*(Dx-Cx)-(Ax-Cx)*(Dy-Cy);
rBot = (Bx-Ax)*(Dy-Cy)-(By-Ay)*(Dx-Cx);
sTop = (Ay-Cy)*(Bx-Ax)-(Ax-Cx)*(By-Ay);
sBot = rBot;
if (sBot == 0.0)
return FALSE;
r = rTop / rBot;
if (r < 0.0)
return FALSE;
if (r > 1.0)
return FALSE;
s = sTop / sBot;
if (s < 0.0)
return FALSE;
if (s > 1.0)
return FALSE;
if (ptIntersect)
*ptIntersect = InterpolatePoint (a, b, r, 1.0);
return TRUE;
}
BOOL Colinear(CPoint a, CPoint b, CPoint c, CPoint d)
{
int dot = (b.x-a.x)*(d.y-c.y) - (d.x-c.x)*(b.y-a.y);
return !dot;
}
CPoint InterpolatePoint (CPoint Begin, CPoint End, double Which, double OutOf)
{
CPoint pt;
pt.x = (int)InterpolateDouble (Begin.x, End.x, Which, OutOf);
pt.y = (int)InterpolateDouble (Begin.y, End.y, Which, OutOf);
return pt;
}
double InterpolateDouble ( double Begin, double End, double Which, double OutOf)
{
if (OutOf == 0.0)
return Begin;
return ((End - Begin) * Which / OutOf) + Begin;
}
Good luck!
Iain.
|