PointInRegion Collision
Detection Code Demo
by
Ben Kenwright
This really isn't much of a demo, but I think the principle behind how we
solve this solution is really interesting. It all depends on how well you
know your vector maths, and how you use it.
Basically if we have a Convex shape, then we can determine if a point is
inside or outside this shape.
With a bit of modification, this method is also used to determine if a 3d
point is inside a triangle or not. Or you could combine it with the dot
product, to show if the angle is to the right or left (as the dot product only
returns the angle between the two vectors, it doesn't tell us if its to the left
or right).
The below applet is as simple as I could make it, basically you can drag the
mouse cursor in and out of the rectange, while holding the mouse button down,
and it will fill the screen a different colour to prove that you've entered or
left the region.
How it works? Well basically you go around the shape, using pairs of
points. Then you work out the direction vectors from your point to each of
them. You do the cross product, and you should get a value. Now
because where in 2D, the cross product will either by positive y or negative y,
depending if our vectors go from left to right or right to left. Now if we
are point is inside the shape, all our cross product results will be all the
same sign. If we are outside the shape, then we will have different
values.
PointInRegion.java - Applet Demo Source Code |
import java.awt.image.*;
import java.awt.*;
import java.applet.*;
/*********************************************************************************************/
class Point2
{
public int x, y;
public Point2( int xx, int yy )
{
x = xx; y = yy;
}// End constructor
}// End Point3 class
/*********************************************************************************************/
/* */
/* Program Entry Point! */
/* Let the coding begin.... */
/* */
/*********************************************************************************************/
public class pointInRegion extends Applet
{
int scr_width;
int scr_height;
// Mouse coords
int mx;
int my;
int mb;
public void init()
{
scr_width = getSize().width;
scr_height = getSize().height;
repaint();
}// End init(..)
void RenderBox( Graphics g )
{
Point2[] pts;
pts = new Point2[ 4 ];
pts[0] = new Point2( 10, 10);
pts[1] = new Point2( 50, 10);
pts[2] = new Point2( 50, 50);
pts[3] = new Point2( 10, 50);
boolean inRegion = false;
inRegion =
CheckIsInRegion((float)mx, (float)my, pts);
// Clear the screen
if (inRegion)
{
g.setColor( Color.blue );
}
else
{
g.setColor( Color.black );
}
g.fillRect( 0, 0, scr_width, scr_height );
int p0 = 0;
int p1 = 1;
for(int j=0; j<3; j++)
{
g.setColor( Color.white );
g.drawLine( pts[p0].x, pts[p0].y, pts[p1].x, pts[p1].y );
p0++;
p1++;
}// End for loop j
// Draw closing line of the shape
g.drawLine( pts[0].x, pts[0].y, pts[3].x, pts[3].y );
g.drawLine( mx, my, mx+1, my+1 );
}// End renderWireCube(..)
float Cross2D(float ux, float uy, float vx, float vy)
{
return uy*vx - ux*vy;
}
boolean CheckIsInRegion(float px, float py, Point2[] pts)
{
float p0x = pts[3].x;
float p0y = pts[3].y;
float p1x = pts[0].x;
float p1y = pts[0].y;
float d0x = p0x - px;
float d0y = p0y - py;
float d1x = p1x - px;
float d1y = p1y - py;
float firstDir = Cross2D(d0x,d0y, d1x,d1y);
System.out.println("\nfirstDir " + firstDir);
for (int i=0; i<3; i++)
{
p0x = pts[i].x;
p0y = pts[i].y;
p1x = pts[i+1].x;
p1y = pts[i+1].y;
d0x = p0x - px;
d0y = p0y - py;
d1x = p1x - px;
d1y = p1y - py;
float dir = Cross2D(d0x,d0y, d1x,d1y);
float testDir = dir * firstDir;
System.out.println("dir " + dir);
if (testDir < 0.0f)
{
return true;
}
}
System.out.println("-");
return false;
}
public void update( Graphics g )
{
RenderBox( g );
showStatus("Press Mouse Button and Drag In and Out of Rectangle ");
}// End update(..)
public void paint( Graphics g )
{
update( g );
}// End paint(..)
/*********************************************************************************************/
/* */
/* Capture event when mouse is pressed */
/* Parameters: */
/* evt is The event... */
/* x is the x mouse position */
/* y is the y mouse position */
/* return whether or not we handled the event */
/* */
/*********************************************************************************************/
public boolean mouseDown(Event evt, int x, int y)
{
mb = 1;
return true;
}// End of mouseDown(..)
/*********************************************************************************************/
/* */
/* Capture mouse release */
/* Parameters: */
/* evt is The event... */
/* x is the x mouse position */
/* y is the y mouse position */
/* return whether or not we handled the event */
/* */
/*********************************************************************************************/
public boolean mouseUp(Event evt, int x, int y)
{
mb=0;
return false;
}// End of mouseUp(..)
/*********************************************************************************************/
/* */
/* Captures mouse movement */
/* -> Was added so that the dagging of the wire cube was more smooth...as if you click at a */
/* new place on the screen, there would be a sudden jump...this way its smooth right from */
/* your first click with the mouse :) */
/* */
/*********************************************************************************************/
public boolean mouseMove(Event evt, int x, int y)
{
// Update our old mouse pos
mx = x;
my = y;
return true;
}// End mouseMove(..)
/*********************************************************************************************/
/* */
/* Capture mouse drags */
/* Parameters: */
/* evt is The event... */
/* x is the x mouse position */
/* y is the y mouse position */
/* return whether or not we handled the event */
/* */
/*********************************************************************************************/
public boolean mouseDrag(Event evt, int x, int y)
{
if( mb == 1 )
{
int xnew = my - y;
int ynew = mx - x;
// Update the screen
repaint();
}// End if(..)
// Update our old mouse pos
mx = x;
my = y;
return true;
}// End of mouseDrag(..)
}// End of Applet
|
Feedback is always welcome, and if you notice any anomalies or
bugs please feel free to email me - as it goes to improve the tutorials and
demos for others. (bkenwright@xbdev.net)
|