By
Jeff Lander
Gamasutra
February 10, 2000
|
|
 Features
Listing
1. The Quadrant Approach
to the Bounding Box Test
// FIGURE
OUT WHICH QUADRANT THE VERTEX IS RELATIVE TO
// THE HIT POINT
#define WHICH_QUAD(vertex,hitPos) \
( (vertex.x
> hitPos->x) ? ((vertex.y > hitPos->y)
? 1 : 4) :( (vertex.y > hitPos->y) ? 2 : 3) )
// GET THE X INTERCEPT OF THE LINE FROM THE CURRENT VERTEX TO
// THE NEXT
#define X_INTERCEPT(point1, point2, hitY) \
(point2.x
- ( ((point2.y - hitY) * (point1.x - point2.x))
/ (point1.y - point2.y) ) )
/////////////////////////////////////////////////////////////
// Procedure:
PointInPoly (SUM OF ANGLES CROSSING VERSION)
// Purpose: Check
if a point is inside a polygon
// Returns: TRUE
if Point is inside polygon, else FALSE
/////////////////////////////////////////////////////////////
BOOL CFateView::PointInPoly(tSector *sector, tPoint2D *hitPos)
{
/// Local Variables /////////////////////////////////////////
short
edge, first, next;
short
quad, next_quad, delta, total;
/////////////////////////////////////////////////////////////
edge
= first = sector->edge;
quad
= WHICH_QUAD(m_edgelist[edge].pos, hitPos);
total = 0; // COUNT OF ABSOLUTE SECTORS CROSSED
/*
LOOP THROUGH THE VERTICES IN A SECTOR */
do
{
next = m_edgelist[edge].nextedge;
next_quad
= WHICH_QUAD(m_edgelist[next].pos, hitPos);
delta
= next_quad - quad; // HOW MANY QUADS HAVE I MOVED
// SPECIAL CASES TO HANDLE CROSSINGS OF MORE THEN ONE
//QUAD
switch
(delta) {
case
2: // IF WE CROSSED THE MIDDLE, FIGURE OUT IF IT
//WAS
CLOCKWISE OR COUNTER
case
-2: // US THE X POSITION AT THE HIT POINT TO
//
DETERMINE WHICH WAY AROUND
if (X_INTERCEPT(m_edgelist[edge].pos,
m_edgelist[next].pos, hitPos->y) > hitPos->x)
delta
= - (delta);
break;
case 3: // MOVING 3 QUADS IS LIKE MOVING BACK 1
delta = -1;
break;
case -3: // MOVING BACK 3 IS LIKE MOVING FORWARD 1
delta = 1;
break;
}
/*
ADD IN THE DELTA */
total
+= delta;
quad
= next_quad; // RESET FOR NEXT STEP
edge
= next;
}
while (edge != first);
/*
AFTER ALL IS DONE IF THE TOTAL IS 4 THEN WE ARE INSIDE */
if
((total == +4) || (total == -4)) return TRUE; else return FALSE;
}
_____________________________________________________________
 Back
to Article
|
|
|
|
|
