Code archives/Algorithms/Is In Triangle 2D

Graphics 800,600,0,2


x1#=50
y1#=50

x2#=150
y2#=50


x3#=70
y3#=350



SetBuffer BackBuffer()

Color 255,255,255

While Not KeyHit(1)
	
	Cls
	
	Line x1,y1,x2,y2
	Line x3,y3,x2,y2
	Line x1,y1,x3,y3
	
	x#=MouseX()
	y#=MouseY()
	
	
	If IsInTriangle(x,y,x1,y1,x2,y2,x3,y3)
		
		Text 10,10,"Inside"
		
	Else
		
		Text 10,10,"-"
		
	EndIf
	
	
	
	Flip
	
Wend


End


; by Charles H. Giffen from
; http://groups.google.com/groups?selm=3784B03B.F1CCF05D%40virginia.edu&oe=UTF-8&output=gplain
; Blitz Port by Peter Scheutz

Function IsInTriangle ( px#,py#, ax#,ay#,bx#,by#,cx#,cy# ) 

	Local bc#,ca#,ab#,ap#,bp#,cp#,abc#

	bc# = bx*cy - by*cx 
	ca# = cx*ay - cy*ax 
	ab# = ax*by - ay*bx
	ap# = ax*py - ay*px
	bp# = bx*py - by*px
	cp# = cx*py - cy*px
	abc# = Sgn(bc + ca + ab)

	If (abc*(bc-bp+cp)>0) And (abc*(ca-cp+ap)>0) And (abc*(ab-ap+bp)>0) Then Return True
End Function

//  Globals which should be set before calling this function:
//
//  int    polyCorners  =  how many corners the polygon has (no repeats)
//  float  polyX[]      =  horizontal coordinates of corners
//  float  polyY[]      =  vertical coordinates of corners
//  float  x, y         =  point to be tested
//
//  (Globals are used in this example for purposes of speed.  Change as
//  desired.)
//
//  The function will return YES if the point x,y is inside the polygon, or
//  NO if it is not.  If the point is exactly on the edge of the polygon,
//  then the function may return YES or NO.
//
//  Note that division by zero is avoided because the division is protected
//  by the "if" clause which surrounds it.

bool pointInPolygon() 

{
  int   i, j=polyCorners-1 ;
  bool  oddNodes=NO      ;

  for (i=0; i<polyCorners; i++) {
    if ((polyY[i]< y && polyY[j]>=y
    ||   polyY[j]< y && polyY[i]>=y)
    &&  (polyX[i]<=x || polyX[j]<=x)) {
      if (polyX[i]+(y-polyY[i])/(polyY[j]-polyY[i])*(polyX[j]-polyX[i])<x) {
        oddNodes=!oddNodes; }}
    j=i; }

  return oddNodes; 
}

//  Globals which should be set before calling these functions:
//
//  int    polyCorners  =  how many corners the polygon has (no repeats)
//  float  polyX[]      =  horizontal coordinates of corners
//  float  polyY[]      =  vertical coordinates of corners
//  float  x, y         =  point to be tested
//
//  The following global arrays should be allocated before calling these functions:
//
//  float  constant[] = storage for precalculated constants (same size as polyX)
//  float  multiple[] = storage for precalculated multipliers (same size as polyX)
//
//  (Globals are used in this example for purposes of speed.  Change as
//  desired.)
//
//  USAGE:
//  Call precalc_values() to initialize the constant[] and multiple[] arrays,
//  then call pointInPolygon(x, y) to determine if the point is in the polygon.
//
//  The function will return YES if the point x,y is inside the polygon, or
//  NO if it is not.  If the point is exactly on the edge of the polygon,
//  then the function may return YES or NO.
//
//  Note that division by zero is avoided because the division is protected
//  by the "if" clause which surrounds it.

void precalc_values() 
{
  int   i, j=polyCorners-1 ;

  for(i=0; i<polyCorners; i++) {
    if(polyY[j]==polyY[i]) {
      constant[i]=polyX[i];
      multiple[i]=0; }
    else {
      constant[i]=polyX[i]-(polyY[i]*polyX[j])/(polyY[j]-polyY[i])+(polyY[i]*polyX[i])/(polyY[j]-polyY[i]);
      multiple[i]=(polyX[j]-polyX[i])/(polyY[j]-polyY[i]); }
    j=i; }}

bool pointInPolygon() {

  int   i, j=polyCorners-1 ;
  bool  oddNodes=NO      ;

  for (i=0; i<polyCorners; i++) {
    if ((polyY[i]< y && polyY[j]>=y
    ||   polyY[j]< y && polyY[i]>=y)) {
      oddNodes^=(y*multiple[i]+constant[i]<x); }
    j=i; }

  return oddNodes; 
}