Find if a point is within a triangle
Find if a point is within a triangle.
You are encouraged to solve this task according to the task description, using any language you may know.
- Task
- Assume points are on a plane defined by (x, y) real number coordinates.
- Given a point P(x, y) and a triangle formed by points A, B, and C, determine if P is within triangle ABC.
- You may use any algorithm.
- Bonus: explain why the algorithm you chose works.
- Related tasks
- Also see
ALGOL 68
Started out as
With additional material
<lang algol68>BEGIN # determine whether a point is within a triangle or not #
# tolerance for the accurate test # REAL eps = 0.001; REAL eps squared = eps * eps; # mode to hold a point # MODE POINT = STRUCT( REAL x, y ); # returns a readable representation of p # OP TOSTRING = ( POINT p )STRING: "[" + fixed( x OF p, -8, 4 ) + "," + fixed( y OF p, -8, 4 ) + "]"; # returns 1 if p is to the right of the line ( a, b ), -1 if it is to the left and 0 if it is on it # PROC side of line = ( POINT p, a, b )INT: SIGN ( ( ( x OF b - x OF a ) * ( y OF p - y OF a ) ) - ( ( y OF b - y OF a ) * ( x OF p - x OF a ) ) ); # returns the minimum of a and b # PROC min = ( REAL a, b )REAL: IF a < b THEN a ELSE b FI; # returns the maximum of a and b # PROC max = ( REAL a, b )REAL: IF a > b THEN a ELSE b FI; # returns TRUE if p is within the bounding box of the triangle a, b, c, FALSE otherwise # PROC point inside bounding box of triangle = ( POINT p, a, b, c )BOOL: BEGIN REAL x min = min( x OF a, min( x OF b, x OF c ) ); REAL y min = min( y OF a, min( y OF b, y OF c ) ); REAL x max = max( x OF a, max( x OF b, x OF c ) ); REAL y max = max( y OF a, max( y OF b, y OF c ) ); x min <= x OF p AND x OF p <= x max AND y min <= y OF p AND y OF p <= y max END # point inside bounding box of triangle # ; # returns the squared distance between p and the line a, b # PROC distance square point to segment = ( POINT p, a, b )REAL: IF REAL a b square length = ( ( x OF b - x OF a ) ^ 2 ) + ( ( y OF b - y OF a ) ^ 2 ); REAL dot product = ( ( ( x OF p - x OF a ) ^ 2 ) + ( ( y OF p - y OF a ) ^ 2 ) ) / a b square length; dot product < 0 THEN ( ( x OF p - x OF a ) ^ 2 ) + ( ( y OF p - y OF a ) ^ 2 ) ELIF dot product <= 1 THEN ( ( x OF a - x OF p ) ^ 2 ) + ( ( y OF a - y OF p ) ^ 2 ) - ( dot product * dot product * a b square length ) ELSE ( ( x OF p - x OF b ) ^ 2 ) + ( ( y OF p - y OF b ) ^ 2 ) FI # distance square point to segment # ; # returns TRUE if p is within the triangle defined by a, b and c, FALSE otherwise # PROC point inside triangle = ( POINT p, a, b, c )BOOL: IF NOT point inside bounding box of triangle( p, a, b, c ) THEN FALSE ELIF INT side of ab = side of line( p, a, b ); INT side of bc = side of line( p, b, c ); side of ab /= side of bc THEN FALSE ELIF side of ab = side of line( p, c, a ) THEN TRUE ELIF distance square point to segment( p, a, b ) <= eps squared THEN TRUE ELIF distance square point to segment( p, b, c ) <= eps squared THEN TRUE ELSE distance square point to segment( p, c, a ) <= eps squared FI # point inside triangle # ; # test the point inside triangle procedure # PROC test point = ( POINT p, a, b, c )VOID: print( ( TOSTRING p, " in ( ", TOSTRING a, ", ", TOSTRING b, ", ", TOSTRING c, ") -> " , IF point inside triangle( p, a, b, c ) THEN "true" ELSE "false" FI , newline ) ); # test cases as in Commpn Lisp # test point( ( 0, 0 ), ( 1.5, 2.4 ), ( 5.1, -3.1 ), ( -3.8, 1.2 ) ); test point( ( 0, 1 ), ( 1.5, 2.4 ), ( 5.1, -3.1 ), ( -3.8, 1.2 ) ); test point( ( 3, 1 ), ( 1.5, 2.4 ), ( 5.1, -3.1 ), ( -3.8, 1.2 ) ); test point( ( 5.414286, 14.349206 ), ( 0.1, 0.111111 ), ( 12.5, 33.333333 ), ( 25.0, 11.111111 ) ); test point( ( 5.414286, 14.349206 ), ( 0.1, 0.111111 ), ( 12.5, 33.333333 ), ( -12.5, 16.666667 ) ); # additional Wren test cases # test point( ( 5.4142857142857, 14.349206349206 ) , ( 0.1, 0.11111111111111 ), ( 12.5, 33.333333333333 ), ( 25, 11.111111111111 ) ); test point( ( 5.4142857142857, 14.349206349206 ) , ( 0.1, 0.11111111111111 ), ( 12.5, 33.333333333333 ), ( -12.5, 16.666666666667 ) )
END</lang>
- Output:
[ 0.0000, 0.0000] in ( [ 1.5000, 2.4000], [ 5.1000, -3.1000], [ -3.8000, 1.2000]) -> true [ 0.0000, 1.0000] in ( [ 1.5000, 2.4000], [ 5.1000, -3.1000], [ -3.8000, 1.2000]) -> true [ 3.0000, 1.0000] in ( [ 1.5000, 2.4000], [ 5.1000, -3.1000], [ -3.8000, 1.2000]) -> false [ 5.4143, 14.3492] in ( [ 0.1000, 0.1111], [ 12.5000, 33.3333], [ 25.0000, 11.1111]) -> true [ 5.4143, 14.3492] in ( [ 0.1000, 0.1111], [ 12.5000, 33.3333], [-12.5000, 16.6667]) -> false [ 5.4143, 14.3492] in ( [ 0.1000, 0.1111], [ 12.5000, 33.3333], [ 25.0000, 11.1111]) -> true [ 5.4143, 14.3492] in ( [ 0.1000, 0.1111], [ 12.5000, 33.3333], [-12.5000, 16.6667]) -> false
AutoHotkey
<lang AutoHotkey>T := [[1.5, 2.4], [5.1, -3.1], [-3.8, 1.2]] for i, p in [[0, 0], [0, 1], [3, 1], [5.4142857, 14.349206]]
result .= "[" p.1 ", " p.2 "] is within triangle?`t" (TriHasP(T, p) ? "ture" : "false") "`n"
MsgBox % result return
TriHasP(T, P){
Ax := TriArea(T.1.1, T.1.2, T.2.1, T.2.2, T.3.1, T.3.2) A1 := TriArea(P.1 , P.2 , T.2.1, T.2.2, T.3.1, T.3.2) A2 := TriArea(T.1.1, T.1.2, P.1 , P.2 , T.3.1, T.3.2) A3 := TriArea(T.1.1, T.1.2, T.2.1, T.2.2, P.1 , P.2) return (Ax = A1 + A2 + A3)
} TriArea(x1, y1, x2, y2, x3, y3){
return Abs((x1 * (y2-y3) + x2 * (y3-y1) + x3 * (y1-y2)) / 2)
}</lang>
- Output:
[0, 0] is within triangle? ture [0, 1] is within triangle? ture [3, 1] is within triangle? false [5.4142857, 14.349206] is within triangle? false
C
<lang c>#include <stdbool.h>
- include <stdio.h>
- include <stdlib.h>
const double EPS = 0.001; const double EPS_SQUARE = 0.000001;
double side(double x1, double y1, double x2, double y2, double x, double y) {
return (y2 - y1) * (x - x1) + (-x2 + x1) * (y - y1);
}
bool naivePointInTriangle(double x1, double y1, double x2, double y2, double x3, double y3, double x, double y) {
double checkSide1 = side(x1, y1, x2, y2, x, y) >= 0; double checkSide2 = side(x2, y2, x3, y3, x, y) >= 0; double checkSide3 = side(x3, y3, x1, y1, x, y) >= 0; return checkSide1 && checkSide2 && checkSide3;
}
bool pointInTriangleBoundingBox(double x1, double y1, double x2, double y2, double x3, double y3, double x, double y) {
double xMin = min(x1, min(x2, x3)) - EPS; double xMax = max(x1, max(x2, x3)) + EPS; double yMin = min(y1, min(y2, y3)) - EPS; double yMax = max(y1, max(y2, y3)) + EPS; return !(x < xMin || xMax < x || y < yMin || yMax < y);
}
double distanceSquarePointToSegment(double x1, double y1, double x2, double y2, double x, double y) {
double p1_p2_squareLength = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1); double dotProduct = ((x - x1) * (x2 - x1) + (y - y1) * (y2 - y1)) / p1_p2_squareLength; if (dotProduct < 0) { return (x - x1) * (x - x1) + (y - y1) * (y - y1); } else if (dotProduct <= 1) { double p_p1_squareLength = (x1 - x) * (x1 - x) + (y1 - y) * (y1 - y); return p_p1_squareLength - dotProduct * dotProduct * p1_p2_squareLength; } else { return (x - x2) * (x - x2) + (y - y2) * (y - y2); }
}
bool accuratePointInTriangle(double x1, double y1, double x2, double y2, double x3, double y3, double x, double y) {
if (!pointInTriangleBoundingBox(x1, y1, x2, y2, x3, y3, x, y)) { return false; } if (naivePointInTriangle(x1, y1, x2, y2, x3, y3, x, y)) { return true; } if (distanceSquarePointToSegment(x1, y1, x2, y2, x, y) <= EPS_SQUARE) { return true; } if (distanceSquarePointToSegment(x2, y2, x3, y3, x, y) <= EPS_SQUARE) { return true; } if (distanceSquarePointToSegment(x3, y3, x1, y1, x, y) <= EPS_SQUARE) { return true; } return false;
}
void printPoint(double x, double y) {
printf("(%f, %f)", x, y);
}
void printTriangle(double x1, double y1, double x2, double y2, double x3, double y3) {
printf("Triangle is ["); printPoint(x1, y1); printf(", "); printPoint(x2, y2); printf(", "); printPoint(x3, y3); printf("] \n");
}
void test(double x1, double y1, double x2, double y2, double x3, double y3, double x, double y) {
printTriangle(x1, y1, x2, y2, x3, y3); printf("Point "); printPoint(x, y); printf(" is within triangle? "); if (accuratePointInTriangle(x1, y1, x2, y2, x3, y3, x, y)) { printf("true\n"); } else { printf("false\n"); }
}
int main() {
test(1.5, 2.4, 5.1, -3.1, -3.8, 1.2, 0, 0); test(1.5, 2.4, 5.1, -3.1, -3.8, 1.2, 0, 1); test(1.5, 2.4, 5.1, -3.1, -3.8, 1.2, 3, 1); printf("\n");
test(0.1, 0.1111111111111111, 12.5, 33.333333333333336, 25, 11.11111111111111, 5.414285714285714, 14.349206349206348); printf("\n");
test(0.1, 0.1111111111111111, 12.5, 33.333333333333336, -12.5, 16.666666666666668, 5.414285714285714, 14.349206349206348); printf("\n");
return 0;
}</lang>
- Output:
Triangle is [(1.500000, 2.400000), (5.100000, -3.100000), (-3.800000, 1.200000)] Point (0.000000, 0.000000) is within triangle? true Triangle is [(1.500000, 2.400000), (5.100000, -3.100000), (-3.800000, 1.200000)] Point (0.000000, 1.000000) is within triangle? true Triangle is [(1.500000, 2.400000), (5.100000, -3.100000), (-3.800000, 1.200000)] Point (3.000000, 1.000000) is within triangle? false Triangle is [(0.100000, 0.111111), (12.500000, 33.333333), (25.000000, 11.111111)] Point (5.414286, 14.349206) is within triangle? true Triangle is [(0.100000, 0.111111), (12.500000, 33.333333), (-12.500000, 16.666667)] Point (5.414286, 14.349206) is within triangle? true
C++
<lang cpp>#include <iostream>
const double EPS = 0.001; const double EPS_SQUARE = EPS * EPS;
double side(double x1, double y1, double x2, double y2, double x, double y) {
return (y2 - y1) * (x - x1) + (-x2 + x1) * (y - y1);
}
bool naivePointInTriangle(double x1, double y1, double x2, double y2, double x3, double y3, double x, double y) {
double checkSide1 = side(x1, y1, x2, y2, x, y) >= 0; double checkSide2 = side(x2, y2, x3, y3, x, y) >= 0; double checkSide3 = side(x3, y3, x1, y1, x, y) >= 0; return checkSide1 && checkSide2 && checkSide3;
}
bool pointInTriangleBoundingBox(double x1, double y1, double x2, double y2, double x3, double y3, double x, double y) {
double xMin = std::min(x1, std::min(x2, x3)) - EPS; double xMax = std::max(x1, std::max(x2, x3)) + EPS; double yMin = std::min(y1, std::min(y2, y3)) - EPS; double yMax = std::max(y1, std::max(y2, y3)) + EPS; return !(x < xMin || xMax < x || y < yMin || yMax < y);
}
double distanceSquarePointToSegment(double x1, double y1, double x2, double y2, double x, double y) {
double p1_p2_squareLength = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1); double dotProduct = ((x - x1) * (x2 - x1) + (y - y1) * (y2 - y1)) / p1_p2_squareLength; if (dotProduct < 0) { return (x - x1) * (x - x1) + (y - y1) * (y - y1); } else if (dotProduct <= 1) { double p_p1_squareLength = (x1 - x) * (x1 - x) + (y1 - y) * (y1 - y); return p_p1_squareLength - dotProduct * dotProduct * p1_p2_squareLength; } else { return (x - x2) * (x - x2) + (y - y2) * (y - y2); }
}
bool accuratePointInTriangle(double x1, double y1, double x2, double y2, double x3, double y3, double x, double y) {
if (!pointInTriangleBoundingBox(x1, y1, x2, y2, x3, y3, x, y)) { return false; } if (naivePointInTriangle(x1, y1, x2, y2, x3, y3, x, y)) { return true; } if (distanceSquarePointToSegment(x1, y1, x2, y2, x, y) <= EPS_SQUARE) { return true; } if (distanceSquarePointToSegment(x2, y2, x3, y3, x, y) <= EPS_SQUARE) { return true; } if (distanceSquarePointToSegment(x3, y3, x1, y1, x, y) <= EPS_SQUARE) { return true; } return false;
}
void printPoint(double x, double y) {
std::cout << '(' << x << ", " << y << ')';
}
void printTriangle(double x1, double y1, double x2, double y2, double x3, double y3) {
std::cout << "Triangle is ["; printPoint(x1, y1); std::cout << ", "; printPoint(x2, y2); std::cout << ", "; printPoint(x3, y3); std::cout << "]\n";
}
void test(double x1, double y1, double x2, double y2, double x3, double y3, double x, double y) {
printTriangle(x1, y1, x2, y2, x3, y3); std::cout << "Point "; printPoint(x, y); std::cout << " is within triangle? "; if (accuratePointInTriangle(x1, y1, x2, y2, x3, y3, x, y)) { std::cout << "true\n"; } else { std::cout << "false\n"; }
}
int main() {
test(1.5, 2.4, 5.1, -3.1, -3.8, 1.2, 0, 0); test(1.5, 2.4, 5.1, -3.1, -3.8, 1.2, 0, 1); test(1.5, 2.4, 5.1, -3.1, -3.8, 1.2, 3, 1); std::cout << '\n';
test(0.1, 0.1111111111111111, 12.5, 33.333333333333336, 25, 11.11111111111111, 5.414285714285714, 14.349206349206348); std::cout << '\n';
test(0.1, 0.1111111111111111, 12.5, 33.333333333333336, -12.5, 16.666666666666668, 5.414285714285714, 14.349206349206348); std::cout << '\n';
return 0;
}</lang>
- Output:
Triangle is [(1.5, 2.4), (5.1, -3.1), (-3.8, 1.2)] Point (0, 0) is within triangle? true Triangle is [(1.5, 2.4), (5.1, -3.1), (-3.8, 1.2)] Point (0, 1) is within triangle? true Triangle is [(1.5, 2.4), (5.1, -3.1), (-3.8, 1.2)] Point (3, 1) is within triangle? false Triangle is [(0.1, 0.111111), (12.5, 33.3333), (25, 11.1111)] Point (5.41429, 14.3492) is within triangle? true Triangle is [(0.1, 0.111111), (12.5, 33.3333), (-12.5, 16.6667)] Point (5.41429, 14.3492) is within triangle? true
Common Lisp
<lang Lisp>
- There are different algorithms to solve this problem, such as adding areas, adding angles, etc... but these
- solutions are sensitive to rounding errors intrinsic to float operations. We want to avoid these issues, therefore we
- use the following algorithm which only uses multiplication and subtraction
- we consider one side of the triangle
- and see on which side of it is the point P located. We can give +1 if it is on the right hand side, -1 for the
- left side, or 0 if it is on the line. If the point is located on the same side relative to all three sides of the triangle
- then the point is inside of it. This has an added advantage that it can be scaled up to other more complicated figures
- (even concave ones, with some minor modifications).
(defun point-inside-triangle (P A B C) "Is the point P inside the triangle formed by ABC?"
(= (side-of-line P A B) (side-of-line P B C) (side-of-line P C A) ))
- This is the version to include those points which are on one of the sides
(defun point-inside-or-on-triangle (P A B C) "Is the point P inside the triangle formed by ABC or on one of the sides?"
(apply #'= (remove 0 (list (side-of-line P A B) (side-of-line P B C) (side-of-line P C A)))) )
(defun side-of-line (P A B)
"Return +1 if it is on the right side, -1 for the left side, or 0 if it is on the line"
- We use the sign of the determinant of vectors (AB,AM), where M(X,Y) is the query point
- position = sign((Bx - Ax) * (Y - Ay) - (By - Ay) * (X - Ax))
(signum (- (* (- (car B) (car A))
(- (cdr P) (cdr A)) ) (* (- (cdr B) (cdr A)) (- (car P) (car A)) ))))
</lang>
- Output:
(point-inside-triangle '(0 . 0) '(1.5 . 2.4) '(5.1 . -3.1) '(-3.8 . 1.2)) T (point-inside-triangle '(0 . 1) '(1.5 . 2.4) '(5.1 . -3.1) '(-3.8 . 1.2)) T (point-inside-triangle '(3 . 1) '(1.5 . 2.4) '(5.1 . -3.1) '(-3.8 . 1.2)) NIL (point-inside-triangle '(5.414286 . 14.349206) '(0.1 . 0.111111) '(12.5 . 33.333333) '(25.0 . 11.111111)) T (point-inside-triangle '(5.414286 . 14.349206) '(0.1 . 0.111111) '(12.5 . 33.333333) '(-12.5 . 16.666667)) NIL
D
<lang d>import std.algorithm; //.comparison for min and max import std.stdio;
immutable EPS = 0.001; immutable EPS_SQUARE = EPS * EPS;
double side(double x1, double y1, double x2, double y2, double x, double y) {
return (y2 - y1) * (x - x1) + (-x2 + x1) * (y - y1);
}
bool naivePointInTriangle(double x1, double y1, double x2, double y2, double x3, double y3, double x, double y) {
double checkSide1 = side(x1, y1, x2, y2, x, y) >= 0; double checkSide2 = side(x2, y2, x3, y3, x, y) >= 0; double checkSide3 = side(x3, y3, x1, y1, x, y) >= 0; return checkSide1 && checkSide2 && checkSide3;
}
bool pointInTriangleBoundingBox(double x1, double y1, double x2, double y2, double x3, double y3, double x, double y) {
double xMin = min(x1, x2, x3) - EPS; double xMax = max(x1, x2, x3) + EPS; double yMin = min(y1, y2, y3) - EPS; double yMax = max(y1, y2, y3) + EPS; return !(x < xMin || xMax < x || y < yMin || yMax < y);
}
double distanceSquarePointToSegment(double x1, double y1, double x2, double y2, double x, double y) {
double p1_p2_squareLength = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1); double dotProduct = ((x - x1) * (x2 - x1) + (y - y1) * (y2 - y1)) / p1_p2_squareLength; if (dotProduct < 0) { return (x - x1) * (x - x1) + (y - y1) * (y - y1); } else if (dotProduct <= 1) { double p_p1_squareLength = (x1 - x) * (x1 - x) + (y1 - y) * (y1 - y); return p_p1_squareLength - dotProduct * dotProduct * p1_p2_squareLength; } else { return (x - x2) * (x - x2) + (y - y2) * (y - y2); }
}
bool accuratePointInTriangle(double x1, double y1, double x2, double y2, double x3, double y3, double x, double y) {
if (!pointInTriangleBoundingBox(x1, y1, x2, y2, x3, y3, x, y)) { return false; } if (naivePointInTriangle(x1, y1, x2, y2, x3, y3, x, y)) { return true; } if (distanceSquarePointToSegment(x1, y1, x2, y2, x, y) <= EPS_SQUARE) { return true; } if (distanceSquarePointToSegment(x2, y2, x3, y3, x, y) <= EPS_SQUARE) { return true; } if (distanceSquarePointToSegment(x3, y3, x1, y1, x, y) <= EPS_SQUARE) { return true; } return false;
}
void printPoint(double x, double y) {
write('(', x, ", ", y, ')');
}
void printTriangle(double x1, double y1, double x2, double y2, double x3, double y3) {
write("Triangle is ["); printPoint(x1, y1); write(", "); printPoint(x2, y2); write(", "); printPoint(x3, y3); writeln(']');
}
void test(double x1, double y1, double x2, double y2, double x3, double y3, double x, double y) {
printTriangle(x1, y1, x2, y2, x3, y3); write("Point "); printPoint(x, y); write(" is within triangle? "); writeln(accuratePointInTriangle(x1, y1, x2, y2, x3, y3, x, y));
}
void main() {
test(1.5, 2.4, 5.1, -3.1, -3.8, 1.2, 0, 0); test(1.5, 2.4, 5.1, -3.1, -3.8, 1.2, 0, 1); test(1.5, 2.4, 5.1, -3.1, -3.8, 1.2, 3, 1); writeln;
test(0.1, 0.1111111111111111, 12.5, 33.333333333333336, 25, 11.11111111111111, 5.414285714285714, 14.349206349206348); writeln;
test(0.1, 0.1111111111111111, 12.5, 33.333333333333336, -12.5, 16.666666666666668, 5.414285714285714, 14.349206349206348); writeln;
}</lang>
- Output:
Triangle is [(1.5, 2.4), (5.1, -3.1), (-3.8, 1.2)] Point (0, 0) is within triangle? true Triangle is [(1.5, 2.4), (5.1, -3.1), (-3.8, 1.2)] Point (0, 1) is within triangle? true Triangle is [(1.5, 2.4), (5.1, -3.1), (-3.8, 1.2)] Point (3, 1) is within triangle? false Triangle is [(0.1, 0.111111), (12.5, 33.3333), (25, 11.1111)] Point (5.41429, 14.3492) is within triangle? true Triangle is [(0.1, 0.111111), (12.5, 33.3333), (-12.5, 16.6667)] Point (5.41429, 14.3492) is within triangle? true
Factor
Uses the parametric equations method from [5]. <lang factor>USING: accessors fry io kernel locals math math.order sequences ;
TUPLE: point x y ; C: <point> point
- >point< ( point -- x y ) [ x>> ] [ y>> ] bi ;
TUPLE: triangle p1 p2 p3 ; C: <triangle> triangle
- >triangle< ( triangle -- x1 y1 x2 y2 x3 y3 )
[ p1>> ] [ p2>> ] [ p3>> ] tri [ >point< ] tri@ ;
- point-in-triangle? ( point triangle -- ? )
point >point< triangle >triangle< :> ( x y x1 y1 x2 y2 x3 y3 ) y2 y3 - x1 * x3 x2 - y1 * + x2 y3 * + y2 x3 * - :> d y3 y1 - x * x1 x3 - y * + x1 y3 * - y1 x3 * + d / :> t1 y2 y1 - x * x1 x2 - y * + x1 y2 * - y1 x2 * + d neg / :> t2 t1 t2 + :> s t1 t2 [ 0 1 between? ] bi@ and s 1 <= and ;
! Test if it works.
20 <iota> dup [ swap <point> ] cartesian-map ! Make a matrix of points 3 3 <point> 16 10 <point> 10 16 <point> <triangle> ! Make a triangle '[ [ _ point-in-triangle? "#" "." ? write ] each nl ] each nl ! Show points inside the triangle with '#' </lang>
- Output:
.................... .................... .................... ...#................ ....#............... .....##............. .....####........... ......#####......... ......#######....... .......########..... .......##########... ........########.... ........#######..... .........#####...... .........####....... ..........##........ ..........#......... .................... .................... ....................
Go
<lang go>package main
import (
"fmt" "math"
)
const EPS = 0.001 const EPS_SQUARE = EPS * EPS
func side(x1, y1, x2, y2, x, y float64) float64 {
return (y2-y1)*(x-x1) + (-x2+x1)*(y-y1)
}
func naivePointInTriangle(x1, y1, x2, y2, x3, y3, x, y float64) bool {
checkSide1 := side(x1, y1, x2, y2, x, y) >= 0 checkSide2 := side(x2, y2, x3, y3, x, y) >= 0 checkSide3 := side(x3, y3, x1, y1, x, y) >= 0 return checkSide1 && checkSide2 && checkSide3
}
func pointInTriangleBoundingBox(x1, y1, x2, y2, x3, y3, x, y float64) bool {
xMin := math.Min(x1, math.Min(x2, x3)) - EPS xMax := math.Max(x1, math.Max(x2, x3)) + EPS yMin := math.Min(y1, math.Min(y2, y3)) - EPS yMax := math.Max(y1, math.Max(y2, y3)) + EPS return !(x < xMin || xMax < x || y < yMin || yMax < y)
}
func distanceSquarePointToSegment(x1, y1, x2, y2, x, y float64) float64 {
p1_p2_squareLength := (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1) dotProduct := ((x-x1)*(x2-x1) + (y-y1)*(y2-y1)) / p1_p2_squareLength if dotProduct < 0 { return (x-x1)*(x-x1) + (y-y1)*(y-y1) } else if dotProduct <= 1 { p_p1_squareLength := (x1-x)*(x1-x) + (y1-y)*(y1-y) return p_p1_squareLength - dotProduct*dotProduct*p1_p2_squareLength } else { return (x-x2)*(x-x2) + (y-y2)*(y-y2) }
}
func accuratePointInTriangle(x1, y1, x2, y2, x3, y3, x, y float64) bool {
if !pointInTriangleBoundingBox(x1, y1, x2, y2, x3, y3, x, y) { return false } if naivePointInTriangle(x1, y1, x2, y2, x3, y3, x, y) { return true } if distanceSquarePointToSegment(x1, y1, x2, y2, x, y) <= EPS_SQUARE { return true } if distanceSquarePointToSegment(x2, y2, x3, y3, x, y) <= EPS_SQUARE { return true } if distanceSquarePointToSegment(x3, y3, x1, y1, x, y) <= EPS_SQUARE { return true } return false
}
func main() {
pts := [][2]float64{{0, 0}, {0, 1}, {3, 1}} tri := [][2]float64{{3.0 / 2, 12.0 / 5}, {51.0 / 10, -31.0 / 10}, {-19.0 / 5, 1.2}} fmt.Println("Triangle is", tri) x1, y1 := tri[0][0], tri[0][1] x2, y2 := tri[1][0], tri[1][1] x3, y3 := tri[2][0], tri[2][1] for _, pt := range pts { x, y := pt[0], pt[1] within := accuratePointInTriangle(x1, y1, x2, y2, x3, y3, x, y) fmt.Println("Point", pt, "is within triangle?", within) } fmt.Println() tri = [][2]float64{{1.0 / 10, 1.0 / 9}, {100.0 / 8, 100.0 / 3}, {100.0 / 4, 100.0 / 9}} fmt.Println("Triangle is", tri) x1, y1 = tri[0][0], tri[0][1] x2, y2 = tri[1][0], tri[1][1] x3, y3 = tri[2][0], tri[2][1] x := x1 + (3.0/7)*(x2-x1) y := y1 + (3.0/7)*(y2-y1) pt := [2]float64{x, y} within := accuratePointInTriangle(x1, y1, x2, y2, x3, y3, x, y) fmt.Println("Point", pt, "is within triangle ?", within) fmt.Println() tri = [][2]float64{{1.0 / 10, 1.0 / 9}, {100.0 / 8, 100.0 / 3}, {-100.0 / 8, 100.0 / 6}} fmt.Println("Triangle is", tri) x3 = tri[2][0] y3 = tri[2][1] within = accuratePointInTriangle(x1, y1, x2, y2, x3, y3, x, y) fmt.Println("Point", pt, "is within triangle ?", within)
}</lang>
- Output:
Triangle is [[1.5 2.4] [5.1 -3.1] [-3.8 1.2]] Point [0 0] is within triangle? true Point [0 1] is within triangle? true Point [3 1] is within triangle? false Triangle is [[0.1 0.1111111111111111] [12.5 33.333333333333336] [25 11.11111111111111]] Point [5.414285714285714 14.349206349206348] is within triangle ? true Triangle is [[0.1 0.1111111111111111] [12.5 33.333333333333336] [-12.5 16.666666666666668]] Point [5.414285714285714 14.349206349206348] is within triangle ? true
Java
<lang java>import java.util.Objects;
public class FindTriangle {
private static final double EPS = 0.001; private static final double EPS_SQUARE = EPS * EPS;
public static class Point { private final double x, y;
public Point(double x, double y) { this.x = x; this.y = y; }
public double getX() { return x; }
public double getY() { return y; }
@Override public String toString() { return String.format("(%f, %f)", x, y); } }
public static class Triangle { private final Point p1, p2, p3;
public Triangle(Point p1, Point p2, Point p3) { this.p1 = Objects.requireNonNull(p1); this.p2 = Objects.requireNonNull(p2); this.p3 = Objects.requireNonNull(p3); }
public Point getP1() { return p1; }
public Point getP2() { return p2; }
public Point getP3() { return p3; }
private boolean pointInTriangleBoundingBox(Point p) { var xMin = Math.min(p1.getX(), Math.min(p2.getX(), p3.getX())) - EPS; var xMax = Math.max(p1.getX(), Math.max(p2.getX(), p3.getX())) + EPS; var yMin = Math.min(p1.getY(), Math.min(p2.getY(), p3.getY())) - EPS; var yMax = Math.max(p1.getY(), Math.max(p2.getY(), p3.getY())) + EPS; return !(p.getX() < xMin || xMax < p.getX() || p.getY() < yMin || yMax < p.getY()); }
private static double side(Point p1, Point p2, Point p) { return (p2.getY() - p1.getY()) * (p.getX() - p1.getX()) + (-p2.getX() + p1.getX()) * (p.getY() - p1.getY()); }
private boolean nativePointInTriangle(Point p) { boolean checkSide1 = side(p1, p2, p) >= 0; boolean checkSide2 = side(p2, p3, p) >= 0; boolean checkSide3 = side(p3, p1, p) >= 0; return checkSide1 && checkSide2 && checkSide3; }
private double distanceSquarePointToSegment(Point p1, Point p2, Point p) { double p1_p2_squareLength = (p2.getX() - p1.getX()) * (p2.getX() - p1.getX()) + (p2.getY() - p1.getY()) * (p2.getY() - p1.getY()); double dotProduct = ((p.getX() - p1.getX()) * (p2.getX() - p1.getX()) + (p.getY() - p1.getY()) * (p2.getY() - p1.getY())) / p1_p2_squareLength; if (dotProduct < 0) { return (p.getX() - p1.getX()) * (p.getX() - p1.getX()) + (p.getY() - p1.getY()) * (p.getY() - p1.getY()); } if (dotProduct <= 1) { double p_p1_squareLength = (p1.getX() - p.getX()) * (p1.getX() - p.getX()) + (p1.getY() - p.getY()) * (p1.getY() - p.getY()); return p_p1_squareLength - dotProduct * dotProduct * p1_p2_squareLength; } return (p.getX() - p2.getX()) * (p.getX() - p2.getX()) + (p.getY() - p2.getY()) * (p.getY() - p2.getY()); }
private boolean accuratePointInTriangle(Point p) { if (!pointInTriangleBoundingBox(p)) { return false; } if (nativePointInTriangle(p)) { return true; } if (distanceSquarePointToSegment(p1, p2, p) <= EPS_SQUARE) { return true; } if (distanceSquarePointToSegment(p2, p3, p) <= EPS_SQUARE) { return true; } return distanceSquarePointToSegment(p3, p1, p) <= EPS_SQUARE; }
public boolean within(Point p) { Objects.requireNonNull(p); return accuratePointInTriangle(p); }
@Override public String toString() { return String.format("Triangle[%s, %s, %s]", p1, p2, p3); } }
private static void test(Triangle t, Point p) { System.out.println(t); System.out.printf("Point %s is within triangle? %s\n", p, t.within(p)); }
public static void main(String[] args) { var p1 = new Point(1.5, 2.4); var p2 = new Point(5.1, -3.1); var p3 = new Point(-3.8, 1.2); var tri = new Triangle(p1, p2, p3); test(tri, new Point(0, 0)); test(tri, new Point(0, 1)); test(tri, new Point(3, 1)); System.out.println();
p1 = new Point(1.0 / 10, 1.0 / 9); p2 = new Point(100.0 / 8, 100.0 / 3); p3 = new Point(100.0 / 4, 100.0 / 9); tri = new Triangle(p1, p2, p3); var pt = new Point(p1.getX() + (3.0 / 7) * (p2.getX() - p1.getX()), p1.getY() + (3.0 / 7) * (p2.getY() - p1.getY())); test(tri, pt); System.out.println();
p3 = new Point(-100.0 / 8, 100.0 / 6); tri = new Triangle(p1, p2, p3); test(tri, pt); }
}</lang>
- Output:
Triangle[(1.500000, 2.400000), (5.100000, -3.100000), (-3.800000, 1.200000)] Point (0.000000, 0.000000) is within triangle? true Triangle[(1.500000, 2.400000), (5.100000, -3.100000), (-3.800000, 1.200000)] Point (0.000000, 1.000000) is within triangle? true Triangle[(1.500000, 2.400000), (5.100000, -3.100000), (-3.800000, 1.200000)] Point (3.000000, 1.000000) is within triangle? false Triangle[(0.100000, 0.111111), (12.500000, 33.333333), (25.000000, 11.111111)] Point (5.414286, 14.349206) is within triangle? true Triangle[(0.100000, 0.111111), (12.500000, 33.333333), (-12.500000, 16.666667)] Point (5.414286, 14.349206) is within triangle? true
jq
Works with gojq, the Go implementation of jq
Adapted from Wren]
A point is represented by [x,y] and denoted by P1, P2, P3, or Q.
A triangle is represented by an array of points: [P1, P2, P3].
Preliminaries <lang jq>def sum_of_squares(stream): reduce stream as $x (0; . + $x * $x);
def distanceSquared(P1; P2): sum_of_squares(P1[0]-P2[0], P1[1]-P2[1]);
- Emit {x1,y1, ...} for the input triangle
def xy:
{ x1: .[0][0], y1: .[0][1], x2: .[1][0], y2: .[1][1], x3: .[2][0], y3: .[2][1] };
def EPS: 0.001; def EPS_SQUARE: EPS * EPS; </lang> <lang jq>def side(P1; P2; Q):
[P1, P2, Q] | xy | (.y2 - .y1)*(.x3 - .x1) + (-.x2 + .x1)*(.y3 - .y1);
def naivePointInTriangle(P1; P2; P3; Q):
side(P1; P2; Q) >= 0 and side(P2; P3; Q) >= 0 and side(P3; P1; Q) >= 0;
def pointInTriangleBoundingBox(P1; P2; P3; Q):
[P1,P2,P3] | (map(.[0]) | min - EPS) as $xMin | (map(.[0]) | max + EPS) as $xMax | (map(.[1]) | min - EPS) as $yMin | (map(.[1]) | max + EPS) as $yMax | (Q[0] < $xMin or $xMax < Q[0] or Q[1] < $yMin or $yMax < Q[1]) | not;
def distanceSquarePointToSegment(P1; P2; Q):
distanceSquared(P1; P2) as $p1_p2_squareLength | [P1, P2, Q] | xy | (((.x3 - .x1)*(.x2 - .x1) + (.y3 - .y1)*(.y2 - .y1)) / $p1_p2_squareLength) as $dotProduct | if $dotProduct < 0 then sum_of_squares(.x3 - .x1, .y3 - .y1) elif $dotProduct <= 1 then sum_of_squares(.x1 - .x3, .y1 - .y3) as $p_p1_squareLength | $p_p1_squareLength - $dotProduct * $dotProduct * $p1_p2_squareLength else sum_of_squares(.x3 - .x2, .y3 - .y2) end;
def accuratePointInTriangle(P1; P2; P3; Q):
if (pointInTriangleBoundingBox(P1; P2; P3; Q) | not) then false elif naivePointInTriangle(P1; P2; P3; Q) then true elif distanceSquarePointToSegment(P1; P2; Q) <= EPS_SQUARE then true elif distanceSquarePointToSegment(P2; P3; Q) <= EPS_SQUARE then true elif distanceSquarePointToSegment(P3; P1; Q) <= EPS_SQUARE then true else false end;</lang>
Examples <lang jq>def task1:
def pts: [ [0, 0], [0, 1], [3, 1; "Triangle is \(.)", (. as [$P1, $P2, $P3] | pts[] as $Q | accuratePointInTriangle($P1; $P2; $P3; $Q) as $within | "Point \($Q) is within triangle ? \($within)" );
def task2:
"Triangle is \(.)", (. as [$P1, $P2, $P3] | [ $P1[0] + (3/7)*($P2[0] - $P1[0]), $P1[1] + (3/7)*($P2[1] - $P1[1]) ] as $Q | accuratePointInTriangle($P1; $P2; $P3; $Q) as $within | "Point \($Q) is within triangle ? \($within)" );
([ [3/2, 12/5], [51/10, -31/10], [-19/5, 1.2] ] | task1), "", ([ [1/10, 1/9], [100/8, 100/3], [100/4, 100/9] ] | task2), "", ([ [1/10, 1/9], [100/8, 100/3], [-100/8, 100/6] ] | task2)</lang>
- Output:
Triangle is [[1.5,2.4],[5.1,-3.1],[-3.8,1.2]] Point [0,0] is within triangle ? true Point [0,1] is within triangle ? true Point [3,1] is within triangle ? false Triangle is [[0.1,0.1111111111111111],[12.5,33.333333333333336],[25,11.11111111111111]] Point [5.414285714285714,14.349206349206348] is within triangle ? true Triangle is [[0.1,0.1111111111111111],[12.5,33.333333333333336],[-12.5,16.666666666666668]] Point [5.414285714285714,14.349206349206348] is within triangle ? true
Julia
Using the Wren examples. <lang julia>Point(x, y) = [x, y] Triangle(a, b, c) = [a, b, c] LEzero(x) = x < 0 || isapprox(x, 0, atol=0.00000001) GEzero(x) = x > 0 || isapprox(x, 0, atol=0.00000001)
""" Determine which side of plane cut by line (p2, p3) p1 is on """ side(p1, p2, p3) = (p1[1] - p3[1]) * (p2[2] - p3[2]) - (p2[1] - p3[1]) * (p1[2] - p3[2])
""" Determine if point is within triangle formed by points p1, p2, p3. If so, the point will be on the same side of each of the half planes defined by vectors p1p2, p2p3, and p3p1. Each z is positive if outside, negative if inside such a plane. All should be positive or all negative if point is within the triangle. """ function iswithin(point, p1, p2, p3)
z1 = side(point, p1, p2) z2 = side(point, p2, p3) z3 = side(point, p3, p1) notanyneg = GEzero(z1) && GEzero(z2) && GEzero(z3) notanypos = LEzero(z1) && LEzero(z2) && LEzero(z3) return notanyneg || notanypos
end
const POINTS = [Point(0 // 1, 0 // 1), Point(0 // 1, 1 // 1), Point(3 // 1, 1 // 1),
Point(1 // 10 + (3 // 7) * (100 // 8 - 1 // 10), 1 // 9 + (3 // 7) * (100 // 3 - 1 // 9)), Point(3 // 2, 12 // 5), Point(51 // 100, -31 // 100), Point(-19 // 50, 6 // 5), Point(1 // 10, 1 // 9), Point(25 / 2, 100 // 3), Point(25, 100 // 9), Point(-25 // 2, 50 // 3)
]
const TRI = [
Triangle(POINTS[5], POINTS[6], POINTS[7]), Triangle(POINTS[8], POINTS[9], POINTS[10]), Triangle(POINTS[8], POINTS[9], POINTS[11])
]
for tri in TRI
pstring(pt) = "[$(Float32(pt[1])), $(Float32(pt[2]))]" println("\nUsing triangle [", join([pstring(x) for x in tri], ", "), "]:") a, b, c = tri[1], tri[2], tri[3] for p in POINTS[1:4] isornot = iswithin(p, a, b, c) ? "is" : "is not" println("Point $(pstring(p)) $isornot within the triangle.") end
end
</lang>
- Output:
Using triangle [[1.5, 2.4], [0.51, -0.31], [-0.38, 1.2]]: Point [0.0, 0.0] is not within the triangle. Point [0.0, 1.0] is within the triangle. Point [3.0, 1.0] is not within the triangle. Point [5.4142857, 14.349206] is not within the triangle. Using triangle [[0.1, 0.11111111], [12.5, 33.333332], [25.0, 11.111111]]: Point [0.0, 0.0] is not within the triangle. Point [0.0, 1.0] is not within the triangle. Point [3.0, 1.0] is not within the triangle. Point [5.4142857, 14.349206] is within the triangle. Using triangle [[0.1, 0.11111111], [12.5, 33.333332], [-12.5, 16.666666]]: Point [0.0, 0.0] is not within the triangle. Point [0.0, 1.0] is within the triangle. Point [3.0, 1.0] is not within the triangle. Point [5.4142857, 14.349206] is within the triangle.
Kotlin
<lang scala>import kotlin.math.max import kotlin.math.min
private const val EPS = 0.001 private const val EPS_SQUARE = EPS * EPS
private fun test(t: Triangle, p: Point) {
println(t) println("Point $p is within triangle ? ${t.within(p)}")
}
fun main() {
var p1 = Point(1.5, 2.4) var p2 = Point(5.1, -3.1) var p3 = Point(-3.8, 1.2) var tri = Triangle(p1, p2, p3) test(tri, Point(0.0, 0.0)) test(tri, Point(0.0, 1.0)) test(tri, Point(3.0, 1.0)) println() p1 = Point(1.0 / 10, 1.0 / 9) p2 = Point(100.0 / 8, 100.0 / 3) p3 = Point(100.0 / 4, 100.0 / 9) tri = Triangle(p1, p2, p3) val pt = Point(p1.x + 3.0 / 7 * (p2.x - p1.x), p1.y + 3.0 / 7 * (p2.y - p1.y)) test(tri, pt) println() p3 = Point(-100.0 / 8, 100.0 / 6) tri = Triangle(p1, p2, p3) test(tri, pt)
}
class Point(val x: Double, val y: Double) {
override fun toString(): String { return "($x, $y)" }
}
class Triangle(private val p1: Point, private val p2: Point, private val p3: Point) {
private fun pointInTriangleBoundingBox(p: Point): Boolean { val xMin = min(p1.x, min(p2.x, p3.x)) - EPS val xMax = max(p1.x, max(p2.x, p3.x)) + EPS val yMin = min(p1.y, min(p2.y, p3.y)) - EPS val yMax = max(p1.y, max(p2.y, p3.y)) + EPS return !(p.x < xMin || xMax < p.x || p.y < yMin || yMax < p.y) }
private fun nativePointInTriangle(p: Point): Boolean { val checkSide1 = side(p1, p2, p) >= 0 val checkSide2 = side(p2, p3, p) >= 0 val checkSide3 = side(p3, p1, p) >= 0 return checkSide1 && checkSide2 && checkSide3 }
private fun distanceSquarePointToSegment(p1: Point, p2: Point, p: Point): Double { val p1P2SquareLength = (p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y) val dotProduct = ((p.x - p1.x) * (p2.x - p1.x) + (p.y - p1.y) * (p2.y - p1.y)) / p1P2SquareLength if (dotProduct < 0) { return (p.x - p1.x) * (p.x - p1.x) + (p.y - p1.y) * (p.y - p1.y) } if (dotProduct <= 1) { val pP1SquareLength = (p1.x - p.x) * (p1.x - p.x) + (p1.y - p.y) * (p1.y - p.y) return pP1SquareLength - dotProduct * dotProduct * p1P2SquareLength } return (p.x - p2.x) * (p.x - p2.x) + (p.y - p2.y) * (p.y - p2.y) }
private fun accuratePointInTriangle(p: Point): Boolean { if (!pointInTriangleBoundingBox(p)) { return false } if (nativePointInTriangle(p)) { return true } if (distanceSquarePointToSegment(p1, p2, p) <= EPS_SQUARE) { return true } return if (distanceSquarePointToSegment(p2, p3, p) <= EPS_SQUARE) { true } else distanceSquarePointToSegment(p3, p1, p) <= EPS_SQUARE }
fun within(p: Point): Boolean { return accuratePointInTriangle(p) }
override fun toString(): String { return "Triangle[$p1, $p2, $p3]" }
companion object { private fun side(p1: Point, p2: Point, p: Point): Double { return (p2.y - p1.y) * (p.x - p1.x) + (-p2.x + p1.x) * (p.y - p1.y) } }
}</lang>
- Output:
Triangle[(1.5, 2.4), (5.1, -3.1), (-3.8, 1.2)] Point (0.0, 0.0) is within triangle ? true Triangle[(1.5, 2.4), (5.1, -3.1), (-3.8, 1.2)] Point (0.0, 1.0) is within triangle ? true Triangle[(1.5, 2.4), (5.1, -3.1), (-3.8, 1.2)] Point (3.0, 1.0) is within triangle ? false Triangle[(0.1, 0.1111111111111111), (12.5, 33.333333333333336), (25.0, 11.11111111111111)] Point (5.414285714285714, 14.349206349206348) is within triangle ? true Triangle[(0.1, 0.1111111111111111), (12.5, 33.333333333333336), (-12.5, 16.666666666666668)] Point (5.414285714285714, 14.349206349206348) is within triangle ? true
Lua
<lang lua>EPS = 0.001 EPS_SQUARE = EPS * EPS
function side(x1, y1, x2, y2, x, y)
return (y2 - y1) * (x - x1) + (-x2 + x1) * (y - y1)
end
function naivePointInTriangle(x1, y1, x2, y2, x3, y3, x, y)
local checkSide1 = side(x1, y1, x2, y2, x, y) >= 0 local checkSide2 = side(x2, y2, x3, y3, x, y) >= 0 local checkSide3 = side(x3, y3, x1, y1, x, y) >= 0 return checkSide1 and checkSide2 and checkSide3
end
function pointInTriangleBoundingBox(x1, y1, x2, y2, x3, y3, x, y)
local xMin = math.min(x1, x2, x3) - EPS local xMax = math.max(x1, x2, x3) + EPS local yMin = math.min(y1, y2, y3) - EPS local yMax = math.max(y1, y2, y3) + EPS return not (x < xMin or xMax < x or y < yMin or yMax < y)
end
function distanceSquarePointToSegment(x1, y1, x2, y2, x, y)
local p1_p2_squareLength = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) local dotProduct = ((x - x1) * (x2 - x1) + (y - y1) * (y2 - y1)) / p1_p2_squareLength if dotProduct < 0 then return (x - x1) * (x - x1) + (y - y1) * (y - y1) end if dotProduct <= 1 then local p_p1_squareLength = (x1 - x) * (x1 - x) + (y1 - y) * (y1 - y) return p_p1_squareLength - dotProduct * dotProduct * p1_p2_squareLength end return (x - x2) * (x - x2) + (y - y2) * (y - y2)
end
function accuratePointInTriangle(x1, y1, x2, y2, x3, y3, x, y)
if not pointInTriangleBoundingBox(x1, y1, x2, y2, x3, y3, x, y) then return false end if naivePointInTriangle(x1, y1, x2, y2, x3, y3, x, y) then return true end if distanceSquarePointToSegment(x1, y1, x2, y2, x, y) <= EPS_SQUARE then return true end if distanceSquarePointToSegment(x2, y2, x3, y3, x, y) <= EPS_SQUARE then return true end if distanceSquarePointToSegment(x3, y3, x1, y1, x, y) <= EPS_SQUARE then return true end return false
end
function printPoint(x, y)
io.write('('..x..", "..y..')')
end
function printTriangle(x1, y1, x2, y2, x3, y3)
io.write("Triangle is [") printPoint(x1, y1) io.write(", ") printPoint(x2, y2) io.write(", ") printPoint(x3, y3) print("]")
end
function test(x1, y1, x2, y2, x3, y3, x, y)
printTriangle(x1, y1, x2, y2, x3, y3) io.write("Point ") printPoint(x, y) print(" is within triangle? " .. tostring(accuratePointInTriangle(x1, y1, x2, y2, x3, y3, x, y)))
end
test(1.5, 2.4, 5.1, -3.1, -3.8, 1.2, 0, 0) test(1.5, 2.4, 5.1, -3.1, -3.8, 1.2, 0, 1) test(1.5, 2.4, 5.1, -3.1, -3.8, 1.2, 3, 1) print()
test(0.1, 0.1111111111111111, 12.5, 33.333333333333336, 25, 11.11111111111111, 5.414285714285714, 14.349206349206348) print()
test(0.1, 0.1111111111111111, 12.5, 33.333333333333336, -12.5, 16.666666666666668, 5.414285714285714, 14.349206349206348) print()</lang>
- Output:
Triangle is [(1.5, 2.4), (5.1, -3.1), (-3.8, 1.2)] Point (0, 0) is within triangle? true Triangle is [(1.5, 2.4), (5.1, -3.1), (-3.8, 1.2)] Point (0, 1) is within triangle? true Triangle is [(1.5, 2.4), (5.1, -3.1), (-3.8, 1.2)] Point (3, 1) is within triangle? false Triangle is [(0.1, 0.11111111111111), (12.5, 33.333333333333), (25, 11.111111111111)] Point (5.4142857142857, 14.349206349206) is within triangle? true Triangle is [(0.1, 0.11111111111111), (12.5, 33.333333333333), (-12.5, 16.666666666667)] Point (5.4142857142857, 14.349206349206) is within triangle? true
Mathematica /Wolfram Language
<lang Mathematica>RegionMember[Polygon[{{1, 2}, {3, 1}, {2, 4}}], {2, 2}]</lang>
- Output:
True
Nim
<lang Nim>import strformat
const
Eps = 0.001 Eps2 = Eps * Eps
type
Point = tuple[x, y: float] Triangle = object p1, p2, p3: Point
func initTriangle(p1, p2, p3: Point): Triangle =
Triangle(p1: p1, p2: p2, p3: p3)
func side(p1, p2, p: Point): float =
(p2.y - p1.y) * (p.x - p1.x) + (-p2.x + p1.x) * (p.y - p1.y)
func distanceSquarePointToSegment(p1, p2, p: Point): float =
let p1P2SquareLength = (p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y) let dotProduct = ((p.x - p1.x) * (p2.x - p1.x) + (p.y - p1.y) * (p2.y - p1.y)) / p1P2SquareLength if dotProduct < 0: return (p.x - p1.x) * (p.x - p1.x) + (p.y - p1.y) * (p.y - p1.y) if dotProduct <= 1: let pP1SquareLength = (p1.x - p.x) * (p1.x - p.x) + (p1.y - p.y) * (p1.y - p.y) return pP1SquareLength - dotProduct * dotProduct * p1P2SquareLength result = (p.x - p2.x) * (p.x - p2.x) + (p.y - p2.y) * (p.y - p2.y)
func pointInTriangleBoundingBox(t: Triangle; p: Point): bool =
let xMin = min(t.p1.x, min(t.p2.x, t.p3.x)) - EPS let xMax = max(t.p1.x, max(t.p2.x, t.p3.x)) + EPS let yMin = min(t.p1.y, min(t.p2.y, t.p3.y)) - EPS let yMax = max(t.p1.y, max(t.p2.y, t.p3.y)) + EPS result = p.x in xMin..xMax and p.y in yMin..yMax
func nativePointInTriangle(t: Triangle; p: Point): bool =
let checkSide1 = side(t.p1, t.p2, p) >= 0 let checkSide2 = side(t.p2, t.p3, p) >= 0 let checkSide3 = side(t.p3, t.p1, p) >= 0 result = checkSide1 and checkSide2 and checkSide3
func accuratePointInTriangle(t: Triangle; p: Point): bool =
if not t.pointInTriangleBoundingBox(p): return false if t.nativePointInTriangle(p): return true if distanceSquarePointToSegment(t.p1, t.p2, p) <= Eps2 or distanceSquarePointToSegment(t.p3, t.p1, p) <= Eps2: return true
func `$`(p: Point): string = &"({p.x}, {p.y})"
func `$`(t: Triangle): string = &"Triangle[{t.p1}, {t.p2}, {t.p3}]"
func contains(t: Triangle; p: Point): bool = t.accuratePointInTriangle(p)
when isMainModule:
proc test(t: Triangle; p: Point) = echo t echo &"Point {p} is within triangle ? {p in t}"
var p1: Point = (1.5, 2.4) var p2: Point = (5.1, -3.1) var p3: Point = (-3.8, 1.2) var tri = initTriangle(p1, p2, p3) test(tri, (0.0, 0.0)) test(tri, (0.0, 1.0)) test(tri, (3.0, 1.0)) echo() p1 = (1 / 10, 1 / 9) p2 = (100 / 8, 100 / 3) p3 = (100 / 4, 100 / 9) tri = initTriangle(p1, p2, p3) let pt = (p1.x + 3.0 / 7 * (p2.x - p1.x), p1.y + 3.0 / 7 * (p2.y - p1.y)) test(tri, pt) echo() p3 = (-100 / 8, 100 / 6) tri = initTriangle(p1, p2, p3) test(tri, pt)</lang>
- Output:
Triangle[(1.5, 2.4), (5.1, -3.1), (-3.8, 1.2)] Point (0.0, 0.0) is within triangle ? true Triangle[(1.5, 2.4), (5.1, -3.1), (-3.8, 1.2)] Point (0.0, 1.0) is within triangle ? true Triangle[(1.5, 2.4), (5.1, -3.1), (-3.8, 1.2)] Point (3.0, 1.0) is within triangle ? false Triangle[(0.1, 0.1111111111111111), (12.5, 33.33333333333334), (25.0, 11.11111111111111)] Point (5.414285714285714, 14.34920634920635) is within triangle ? true Triangle[(0.1, 0.1111111111111111), (12.5, 33.33333333333334), (-12.5, 16.66666666666667)] Point (5.414285714285714, 14.34920634920635) is within triangle ? true
Perl
Translate the Java program at this blog post and data set is taken from the Raku entry. <lang Perl># 20201123 added Perl programming solution
use strict; use warnings;
use List::AllUtils qw(min max natatime); use constant EPSILON => 0.001; use constant EPSILON_SQUARE => EPSILON*EPSILON;
sub side {
my ($x1, $y1, $x2, $y2, $x, $y) = @_; return ($y2 - $y1)*($x - $x1) + (-$x2 + $x1)*($y - $y1);
}
sub naivePointInTriangle {
my ($x1, $y1, $x2, $y2, $x3, $y3, $x, $y) = @_; my $checkSide1 = side($x1, $y1, $x2, $y2, $x, $y) >= 0 ; my $checkSide2 = side($x2, $y2, $x3, $y3, $x, $y) >= 0 ; my $checkSide3 = side($x3, $y3, $x1, $y1, $x, $y) >= 0 ; return $checkSide1 && $checkSide2 && $checkSide3 || 0 ;
}
sub pointInTriangleBoundingBox {
my ($x1, $y1, $x2, $y2, $x3, $y3, $x, $y) = @_; my $xMin = min($x1, min($x2, $x3)) - EPSILON; my $xMax = max($x1, max($x2, $x3)) + EPSILON; my $yMin = min($y1, min($y2, $y3)) - EPSILON; my $yMax = max($y1, max($y2, $y3)) + EPSILON; ( $x < $xMin || $xMax < $x || $y < $yMin || $yMax < $y ) ? 0 : 1
}
sub distanceSquarePointToSegment {
my ($x1, $y1, $x2, $y2, $x, $y) = @_; my $p1_p2_squareLength = ($x2 - $x1)**2 + ($y2 - $y1)**2; my $dotProduct = ($x-$x1)*($x2-$x1)+($y-$y1)*($y2-$y1) ; if ( $dotProduct < 0 ) { return ($x - $x1)**2 + ($y - $y1)**2; } elsif ( $dotProduct <= $p1_p2_squareLength ) { my $p_p1_squareLength = ($x1 - $x)**2 + ($y1 - $y)**2; return $p_p1_squareLength - $dotProduct**2 / $p1_p2_squareLength; } else { return ($x - $x2)**2 + ($y - $y2)**2; }
}
sub accuratePointInTriangle {
my ($x1, $y1, $x2, $y2, $x3, $y3, $x, $y) = @_; return 0 unless pointInTriangleBoundingBox($x1,$y1,$x2,$y2,$x3,$y3,$x,$y); return 1 if ( naivePointInTriangle($x1, $y1, $x2, $y2, $x3, $y3, $x, $y) or distanceSquarePointToSegment($x1, $y1, $x2, $y2, $x, $y) <= EPSILON_SQUARE or distanceSquarePointToSegment($x2, $y2, $x3, $y3, $x, $y) <= EPSILON_SQUARE or distanceSquarePointToSegment($x3, $y3, $x1, $y1, $x, $y) <= EPSILON_SQUARE); return 0
}
my @DATA = (1.5, 2.4, 5.1, -3.1, -3.8, 0.5);
for my $point ( [0,0] , [0,1] ,[3,1] ) {
print "Point (", join(',',@$point), ") is within triangle "; my $iter = natatime 2, @DATA; while ( my @vertex = $iter->()) { print '(',join(',',@vertex),') ' } print ': ',naivePointInTriangle (@DATA, @$point) ? 'True' : 'False', "\n" ;
}</lang>
- Output:
Point (0,0) is within triangle (1.5,2.4) (5.1,-3.1) (-3.8,0.5) : True Point (0,1) is within triangle (1.5,2.4) (5.1,-3.1) (-3.8,0.5) : True Point (3,1) is within triangle (1.5,2.4) (5.1,-3.1) (-3.8,0.5) : False
Phix
using convex_hull
Using convex_hull() from Convex_hull#Phix <lang Phix>constant p0 = {0,0},
p1 = {0,1}, p2 = {3,1}, triangle = {{3/2, 12/5}, {51/10, -31/10}, {-19/5, 1/2}}
function inside(sequence p) return sort(convex_hull({p}&triangle))==sort(triangle) end function printf(1,"Point %v is with triangle %v?:%t\n",{p0,triangle,inside(p0)}) printf(1,"Point %v is with triangle %v?:%t\n",{p1,triangle,inside(p1)}) printf(1,"Point %v is with triangle %v?:%t\n",{p2,triangle,inside(p2)})</lang>
- Output:
Point {0,0} is with triangle {{1.5,2.4},{5.1,-3.1},{-3.8,0.5}}?:true Point {0,1} is with triangle {{1.5,2.4},{5.1,-3.1},{-3.8,0.5}}?:true Point {3,1} is with triangle {{1.5,2.4},{5.1,-3.1},{-3.8,0.5}}?:false
trans python
(using the same p0/p1/p2/triangle constants from above, same output) <lang Phix>function side(sequence p1, p2, p3)
-- which side of plane cut by line (p2, p3) is p1 on? atom {x1, y1} = p1, {x2, y2} = p2, {x3, y3} = p3 return (x1 - x3) * (y2 - y3) - (x2 - x3) * (y1 - y3)
end function
function iswithin(sequence point, triangle) -- -- Determine if point is within triangle. -- If so, the point will be on the same side of each of the half planes -- defined by vectors p1p2, p2p3, and p3p1. zval is positive if outside, -- negative if inside such a plane. All should be positive or all negative -- if point is within the triangle. --
sequence {pt1, pt2, pt3} = triangle atom zval1 = side(point, pt1, pt2), zval2 = side(point, pt2, pt3), zval3 = side(point, pt3, pt1) bool notanyneg = zval1 >= 0 and zval2 >= 0 and zval3 >= 0, notanypos = zval1 <= 0 and zval2 <= 0 and zval3 <= 0 return notanyneg or notanypos
end function
printf(1,"point %v is with triangle %v?:%t\n",{p0,triangle,iswithin(p0,triangle)}) printf(1,"point %v is with triangle %v?:%t\n",{p1,triangle,iswithin(p1,triangle)}) printf(1,"point %v is with triangle %v?:%t\n",{p2,triangle,iswithin(p2,triangle)})</lang>
Python
<lang python> """ find if point is in a triangle """
from sympy.geometry import Point, Triangle
def sign(pt1, pt2, pt3):
""" which side of plane cut by line (pt2, pt3) is pt1 on? """ return (pt1.x - pt3.x) * (pt2.y - pt3.y) - (pt2.x - pt3.x) * (pt1.y - pt3.y)
def iswithin(point, pt1, pt2, pt3):
""" Determine if point is within triangle formed by points p1, p2, p3. If so, the point will be on the same side of each of the half planes defined by vectors p1p2, p2p3, and p3p1. zval is positive if outside, negative if inside such a plane. All should be positive or all negative if point is within the triangle. """ zval1 = sign(point, pt1, pt2) zval2 = sign(point, pt2, pt3) zval3 = sign(point, pt3, pt1) notanyneg = zval1 >= 0 and zval2 >= 0 and zval3 >= 0 notanypos = zval1 <= 0 and zval2 <= 0 and zval3 <= 0 return notanyneg or notanypos
if __name__ == "__main__":
POINTS = [Point(0, 0)] TRI = Triangle(Point(1.5, 2.4), Point(5.1, -3.1), Point(-3.8, 0.5)) for pnt in POINTS: a, b, c = TRI.vertices isornot = "is" if iswithin(pnt, a, b, c) else "is not" print("Point", pnt, isornot, "within the triangle", TRI)
</lang>
- Output:
Point Point2D(0, 0) is within the triangle Triangle(Point2D(3/2, 12/5), Point2D(51/10, -31/10), Point2D(-19/5, 1/2))
Racket
Racket has exact numbers in its numerical tower... so I don't see much motivation to accomodate rounding errors. This is why the implementation _fails_ the second imprecise test, whereas other implementations pass it. That point is very close to the edge of the triange. If your edge is fat enough (epsilon), it will fall inside. If it is infinitessimal (i.e. exact), it is on the outside.
I would probably use the dot-product version, if only because it requires less (no) division.
<lang racket>#lang racket/base
(define-syntax-rule (all-between-0..1? x ...)
(and (<= 0 x 1) ...))
(define (point-in-triangle?/barycentric x1 y1 x2 y2 x3 y3)
(let* ((y2-y3 (- y2 y3)) (x1-x3 (- x1 x3)) (x3-x2 (- x3 x2)) (y1-y3 (- y1 y3)) (d (+ (* y2-y3 x1-x3) (* x3-x2 y1-y3)))) (λ (x y) (define a (/ (+ (* x3-x2 (- y y3)) (* y2-y3 (- x x3))) d)) (define b (/ (- (* x1-x3 (- y y3)) (* y1-y3 (- x x3))) d)) (define c (- 1 a b)) (all-between-0..1? a b c))))
(define (point-in-triangle?/parametric x1 y1 x2 y2 x3 y3)
(let ((dp (+ (* x1 (- y2 y3)) (* y1 (- x3 x2)) (* x2 y3) (- (* y2 x3))))) (λ (x y) (define t1 (/ (+ (* x (- y3 y1)) (* y (- x1 x3)) (- (* x1 y3)) (* y1 x3)) dp)) (define t2 (/ (+ (* x (- y2 y1)) (* y (- x1 x2)) (- (* x1 y2)) (* y1 x2)) (- dp))) (all-between-0..1? t1 t2 (+ t1 t2)))))
(define (point-in-triangle?/dot-product X1 Y1 X2 Y2 X3 Y3)
(λ (x y) (define (check-side x1 y1 x2 y2) (>= (+ (* (- y2 y1) (- x x1)) (* (- x1 x2) (- y y1))) 0)) (and (check-side X1 Y1 X2 Y2) (check-side X2 Y2 X3 Y3) (check-side X3 Y3 X1 Y1))))
(module+ main
(require rackunit)
(define (run-tests point-in-triangle?) (define pit?-1 (point-in-triangle? #e1.5 #e2.4 #e5.1 #e-3.1 #e-3.8 #e1.2)) (check-true (pit?-1 0 0)) (check-true (pit?-1 0 1)) (check-false (pit?-1 3 1)) (check-true ((point-in-triangle? 1/10 1/9 25/2 100/3 25 10/9) #e5.414285714285714 #e14.349206349206348)) ; exactly speaking, point is _not_ in the triangle (check-false ((point-in-triangle? 1/10 1/9 25/2 100/3 -25/2 50/3) #e5.414285714285714 #e14.349206349206348)))
(run-tests point-in-triangle?/barycentric) (run-tests point-in-triangle?/parametric) (run-tests point-in-triangle?/dot-product))</lang>
- Output:
no output means all tests passed
Raku
Reusing code from the Convex hull task and some logic from the Determine if two triangles overlap task.
<lang perl6>class Point {
has Real $.x is rw; has Real $.y is rw; method gist { [~] '(', self.x,', ', self.y, ')' };
}
sub sign (Point $a, Point $b, Point $c) {
($b.x - $a.x)*($c.y - $a.y) - ($b.y - $a.y)*($c.x - $a.x);
}
sub triangle (*@points where *.elems == 6) {
@points.batch(2).map: { Point.new(:x(.[0]),:y(.[1])) };
}
sub is-within ($point, @triangle is copy) {
my @signs = sign($point, |(@triangle.=rotate)[0,1]) xx 3; so (all(@signs) >= 0) or so(all(@signs) <= 0);
}
my @triangle = triangle((1.5, 2.4), (5.1, -3.1), (-3.8, 0.5));
for Point.new(:x(0),:y(0)),
Point.new(:x(0),:y(1)), Point.new(:x(3),:y(1)) -> $point { say "Point {$point.gist} is within triangle {join ', ', @triangle».gist}: ", $point.&is-within: @triangle
}</lang>
- Output:
Point (0, 0) is within triangle (1.5, 2.4), (5.1, -3.1), (-3.8, 0.5): True Point (0, 1) is within triangle (1.5, 2.4), (5.1, -3.1), (-3.8, 0.5): True Point (3, 1) is within triangle (1.5, 2.4), (5.1, -3.1), (-3.8, 0.5): False
REXX
Extra certification code was added to verify that the X,Y coördinates for the points are not missing and are numeric.
<lang rexx>/*REXX program determines if a specified point is within a specified triangle. */
parse arg p a b c . /*obtain optional arguments from the CL*/
if p== | p=="," then p= '(0,0)' /*Not specified? Then use the default.*/
if a== | a=="," then a= '(1.5,2.4)' /* " " " " " " */
if b== | b=="," then b= '(5.1,-3.1)' /* " " " " " " */
if c== | c=="," then c= '(-3.8,0.5)' /* " " " " " " */
if ?(p, a, b, c) then @= ' is ' /*Is the point inside the triangle ? */
else @= " isn't " /* " " " outside " " */
say 'point' p @ " within the triangle " a ',' b "," c exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ cert: parse arg z,W; if datatype(z,'N') then return z; call serr z /*return coördinate.*/ serr: say W 'data point ' z " isn't numeric or missing."; exit 13 /*tell error message*/ x: procedure; parse arg "(" x ',' ; return cert(x,"X") /*return the X coördinate.*/ y: procedure; parse arg ',' y ")"; return cert(y,"Y") /* " " Y " */ $: parse arg aa,bb,cc; return (x(aa)-x(cc)) *(y(bb)-y(cc)) - (x(bb)-x(cc)) *(y(aa)-y(cc)) ?: #1=$(p,a,b); #2=$(p,b,c); #3=$(p,c,a); return (#1>=0>=0>=0) | (#1<=0<=0<=0)</lang>
- output when using the default triangle and the point at: (0,0)
point (0,0) is within the triangle (1.5,2.4) , (5.1,-3.1) , (-3.8,0.5)
- output when using the default triangle and the point at: (0,1)
point (0,1) is within the triangle (1.5,2.4) , (5.1,-3.1) , (-3.8,0.5)
- output when using the default triangle and the point at: (3,1)
point (3,1) isn't within the triangle (1.5,2.4) , (5.1,-3.1) , (-3.8,0.5)
Ruby
<lang ruby>EPS = 0.001 EPS_SQUARE = EPS * EPS
def side(x1, y1, x2, y2, x, y)
return (y2 - y1) * (x - x1) + (-x2 + x1) * (y - y1)
end
def naivePointInTriangle(x1, y1, x2, y2, x3, y3, x, y)
checkSide1 = side(x1, y1, x2, y2, x, y) >= 0 checkSide2 = side(x2, y2, x3, y3, x, y) >= 0 checkSide3 = side(x3, y3, x1, y1, x, y) >= 0 return checkSide1 && checkSide2 && checkSide3
end
def pointInTriangleBoundingBox(x1, y1, x2, y2, x3, y3, x, y)
xMin = [x1, x2, x3].min - EPS xMax = [x1, x2, x3].max + EPS yMin = [y1, y2, y3].min - EPS yMax = [y1, y2, y3].max + EPS return !(x < xMin || xMax < x || y < yMin || yMax < y)
end
def distanceSquarePointToSegment(x1, y1, x2, y2, x, y)
p1_p2_squareLength = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) dotProduct = ((x - x1) * (x2 - x1) + (y - y1) * (y2 - y1)) / p1_p2_squareLength if dotProduct < 0 then return (x - x1) * (x - x1) + (y - y1) * (y - y1) end if dotProduct <= 1 then p_p1_squareLength = (x1 - x) * (x1 - x) + (y1 - y) * (y1 - y) return p_p1_squareLength - dotProduct * dotProduct * p1_p2_squareLength end return (x - x2) * (x - x2) + (y - y2) * (y - y2)
end
def accuratePointInTriangle(x1, y1, x2, y2, x3, y3, x, y)
if !pointInTriangleBoundingBox(x1, y1, x2, y2, x3, y3, x, y) then return false end if naivePointInTriangle(x1, y1, x2, y2, x3, y3, x, y) then return true end if distanceSquarePointToSegment(x1, y1, x2, y2, x, y) <= EPS_SQUARE then return true end if distanceSquarePointToSegment(x2, y2, x3, y3, x, y) <= EPS_SQUARE then return true end if distanceSquarePointToSegment(x3, y3, x1, y1, x, y) <= EPS_SQUARE then return true end return false
end
def main
pts = [[0, 0], [0, 1], [3, 1]] tri = [[1.5, 2.4], [5.1, -3.1], [-3.8, 1.2]] print "Triangle is ", tri, "\n" x1, y1 = tri[0][0], tri[0][1] x2, y2 = tri[1][0], tri[1][1] x3, y3 = tri[2][0], tri[2][1] for pt in pts x, y = pt[0], pt[1] within = accuratePointInTriangle(x1, y1, x2, y2, x3, y3, x, y) print "Point ", pt, " is within triangle? ", within, "\n" end print "\n"
tri = [[0.1, 1.0 / 9.0], [12.5, 100.0 / 3.0], [25.0, 100.0 / 9.0]] print "Triangle is ", tri, "\n" x1, y1 = tri[0][0], tri[0][1] x2, y2 = tri[1][0], tri[1][1] x3, y3 = tri[2][0], tri[2][1] x = x1 + (3.0 / 7.0) * (x2 - x1) y = y1 + (3.0 / 7.0) * (y2 - y1) pt = [x, y] within = accuratePointInTriangle(x1, y1, x2, y2, x3, y3, x, y) print "Point ", pt, " is within triangle? ", within, "\n" print "\n"
tri = [[0.1, 1.0 / 9.0], [12.5, 100.0 / 3.0], [-12.5, 100.0 / 6.0]] print "Triangle is ", tri, "\n" x3, y3 = tri[2][0], tri[2][1] within = accuratePointInTriangle(x1, y1, x2, y2, x3, y3, x, y) print "Point ", pt, " is within triangle? ", within, "\n"
end
main()</lang>
- Output:
Triangle is [[1.5, 2.4], [5.1, -3.1], [-3.8, 1.2]] Point [0, 0] is within triangle? true Point [0, 1] is within triangle? true Point [3, 1] is within triangle? false Triangle is [[0.1, 0.1111111111111111], [12.5, 33.333333333333336], [25.0, 11.11111111111111]] Point [5.414285714285714, 14.349206349206348] is within triangle? true Triangle is [[0.1, 0.1111111111111111], [12.5, 33.333333333333336], [-12.5, 16.666666666666668]] Point [5.414285714285714, 14.349206349206348] is within triangle? true
Wren
This is a translation of the ActionScript code for the 'accurate' method in the first referenced article above. <lang ecmascript>import "/math" for Math
var EPS = 0.001 var EPS_SQUARE = EPS * EPS
var side = Fn.new { |x1, y1, x2, y2, x, y|
return (y2 - y1)*(x - x1) + (-x2 + x1)*(y - y1)
}
var naivePointInTriangle = Fn.new { |x1, y1, x2, y2, x3, y3, x, y|
var checkSide1 = side.call(x1, y1, x2, y2, x, y) >= 0 var checkSide2 = side.call(x2, y2, x3, y3, x, y) >= 0 var checkSide3 = side.call(x3, y3, x1, y1, x, y) >= 0 return checkSide1 && checkSide2 && checkSide3
}
var pointInTriangleBoundingBox = Fn.new { |x1, y1, x2, y2, x3, y3, x, y|
var xMin = Math.min(x1, Math.min(x2, x3)) - EPS var xMax = Math.max(x1, Math.max(x2, x3)) + EPS var yMin = Math.min(y1, Math.min(y2, y3)) - EPS var yMax = Math.max(y1, Math.max(y2, y3)) + EPS return !(x < xMin || xMax < x || y < yMin || yMax < y)
}
var distanceSquarePointToSegment = Fn.new { |x1, y1, x2, y2, x, y|
var p1_p2_squareLength = (x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1) var dotProduct = ((x - x1)*(x2 - x1) + (y - y1)*(y2 - y1)) / p1_p2_squareLength if (dotProduct < 0) { return (x - x1)*(x - x1) + (y - y1)*(y - y1) } else if (dotProduct <= 1) { var p_p1_squareLength = (x1 - x)*(x1 - x) + (y1 - y)*(y1 - y) return p_p1_squareLength - dotProduct * dotProduct * p1_p2_squareLength } else { return (x - x2)*(x - x2) + (y - y2)*(y - y2) }
}
var accuratePointInTriangle = Fn.new { |x1, y1, x2, y2, x3, y3, x, y|
if (!pointInTriangleBoundingBox.call(x1, y1, x2, y2, x3, y3, x, y)) return false if (naivePointInTriangle.call(x1, y1, x2, y2, x3, y3, x, y)) return true if (distanceSquarePointToSegment.call(x1, y1, x2, y2, x, y) <= EPS_SQUARE) return true if (distanceSquarePointToSegment.call(x2, y2, x3, y3, x, y) <= EPS_SQUARE) return true if (distanceSquarePointToSegment.call(x3, y3, x1, y1, x, y) <= EPS_SQUARE) return true return false
}
var pts = [ [0, 0], [0, 1], [3, 1]] var tri = [ [3/2, 12/5], [51/10, -31/10], [-19/5, 1.2] ] System.print("Triangle is %(tri)") var x1 = tri[0][0] var y1 = tri[0][1] var x2 = tri[1][0] var y2 = tri[1][1] var x3 = tri[2][0] var y3 = tri[2][1]
for (pt in pts) {
var x = pt[0] var y = pt[1] var within = accuratePointInTriangle.call(x1, y1, x2, y2, x3, y3, x, y) System.print("Point %(pt) is within triangle ? %(within)")
} System.print() tri = [ [1/10, 1/9], [100/8, 100/3], [100/4, 100/9] ] System.print("Triangle is %(tri)") x1 = tri[0][0] y1 = tri[0][1] x2 = tri[1][0] y2 = tri[1][1] x3 = tri[2][0] y3 = tri[2][1] var x = x1 + (3/7)*(x2 - x1) var y = y1 + (3/7)*(y2 - y1) var pt = [x, y] var within = accuratePointInTriangle.call(x1, y1, x2, y2, x3, y3, x, y) System.print("Point %(pt) is within triangle ? %(within)") System.print() tri = [ [1/10, 1/9], [100/8, 100/3], [-100/8, 100/6] ] System.print("Triangle is %(tri)") x3 = tri[2][0] y3 = tri[2][1] within = accuratePointInTriangle.call(x1, y1, x2, y2, x3, y3, x, y) System.print("Point %(pt) is within triangle ? %(within)")</lang>
- Output:
Triangle is [[1.5, 2.4], [5.1, -3.1], [-3.8, 1.2]] Point [0, 0] is within triangle ? true Point [0, 1] is within triangle ? true Point [3, 1] is within triangle ? false Triangle is [[0.1, 0.11111111111111], [12.5, 33.333333333333], [25, 11.111111111111]] Point [5.4142857142857, 14.349206349206] is within triangle ? true Triangle is [[0.1, 0.11111111111111], [12.5, 33.333333333333], [-12.5, 16.666666666667]] Point [5.4142857142857, 14.349206349206] is within triangle ? true
XPL0
<lang XPL0>func real Dot(W,X,Y,Z); \Return the dot product of two 2D vectors real W,X,Y,Z; \ (W-X) dot (Y-Z) real WX(2), YZ(2); [WX(0):= W(0)-X(0); WX(1):= W(1)-X(1);
YZ(0):= Y(0)-Z(0); YZ(1):= Y(1)-Z(1);
return WX(0)*YZ(0) + WX(1)*YZ(1); ];
real A,B,C; \triangle
func PointInTri(P); \Return 'true' if point P is inside triangle ABC real P; int S0,S1,S2; \signs [S0:= Dot(P,A,B,A) >= 0.0;
S1:= Dot(P,B,C,B) >= 0.0; S2:= Dot(P,C,A,C) >= 0.0;
return S0=S1 & S1=S2 & S2=S0; ];
[A:= [10.5, 6.3]; B:= [13.5, 3.6]; C:= [ 3.3, -1.6]; Text(0, if PointInTri([10.0, 3.0]) then "inside" else "outside"); CrLf(0); Text(0, if PointInTri([-5.0,-2.2]) then "inside" else "outside"); CrLf(0); Text(0, if PointInTri([10.5, 6.3]) then "inside" else "outside"); CrLf(0); ]</lang>
- Output:
inside outside inside