C / C++ / MFC

"The greatest good you can do for another is not just to share your riches but to reveal to him his own." - Benjamin Disraeli

Have a nice code day

Have a nice code day

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;
}

/*
From http://www.faqs.org/faqs/graphics/algorithms-faq/

	        (Ay-Cy)(Dx-Cx)-(Ax-Cx)(Dy-Cy)
        r = -----------------------------  (eqn 1)
            (Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx)

            (Ay-Cy)(Bx-Ax)-(Ax-Cx)(By-Ay)
        s = -----------------------------  (eqn 2)
            (Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx)

If 0<=r<=1 & 0<=s<=1, intersection exists
            r<0 or r>1 or s<0 or s>1 line segments do not intersect

        If the denominator in eqn 1 is zero, AB & CD are parallel
        If the numerator in eqn 1 is also zero, AB & CD are collinear.



*/

// Returns true iff ab properly intersects cd: they share a point interior to both segments.
// The properness of the intersection is ensured by using strict leftness.
BOOL	LinesIntersect (CPoint a, CPoint b, CPoint c, CPoint d, CPoint *ptIntersect)
{
	// Quick check for parallel
	if (Colinear (a,b,c,d))
		return FALSE;

	// Get the "meeting point" of the two lines.
	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; // Parallel.
	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;
//	int CrossZ = (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
//	return (abs(CrossZ) < 1);
}

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;
}

Have a nice code day