Code archives/Algorithms/Is In Triangle 2D
This code has been declared by its author to be Public Domain code.
Download source code
| |||||
Check if point is inside triangle | |||||
; 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 |
Comments
| ||
Here is an example.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 |
| ||
Thanks, very useful. |
| ||
Thanks for isinTriangle.... Here is some related code I found (in "C") for finding whether a point is inside a polygon of any number of corners : sourcepage --> http://alienryderflex.com/polygon/ [ Fast "Point in PolyGon" code by author Lascha Lagidse ] // 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; } [ Here’s a pre-calcuation efficiency improvement provided by Patrick Mullen. This is useful if you have many points that need to be tested against the same (static) polygon: ] // 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; } Sorry it's all in "c" code, but maybe someone can transform it into Blitz3D. :) ============================================================ Here are related links :: NerdParadise : Determining if a Point is in a Triangle http://www.nerdparadise.com/math/geometry/pointinatriangle/ TotoLogic BlogSpot : Accurate point in triangle test http://totologic.blogspot.fr/2014/01/accurate-point-in-triangle-test.html StackOverFlow : Count points inside triangle fast http://stackoverflow.com/questions/14757920/count-points-inside-triangle-fast StackOverFlow : How to determine if a point is in a 2D triangle? http://stackoverflow.com/questions/2049582/how-to-determine-if-a-point-is-in-a-2d-triangle |
Code Archives Forum