Find if a point is within a triangle: Difference between revisions
Content added Content deleted
No edit summary |
(Find if a point is within a triangle in Dart) |
||
Line 706: | Line 706: | ||
Triangle is [(0.1, 0.111111), (12.5, 33.3333), (-12.5, 16.6667)] |
Triangle is [(0.1, 0.111111), (12.5, 33.3333), (-12.5, 16.6667)] |
||
Point (5.41429, 14.3492) is within triangle? true</pre> |
Point (5.41429, 14.3492) is within triangle? true</pre> |
||
=={{header|Dart}}== |
|||
{{trans|C++}} |
|||
<syntaxhighlight lang="dart">import 'dart:math'; |
|||
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; |
|||
if (checkSide1 >= 0 && checkSide2 >= 0 && checkSide3 >= 0) { |
|||
return true; |
|||
} else { |
|||
return false; |
|||
} |
|||
} |
|||
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 printTriangle( |
|||
double x1, double y1, double x2, double y2, double x3, double y3) { |
|||
print("Triangle is [($x1, $y1), ($x2, $y2), ($x3, $y3)]"); |
|||
} |
|||
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); |
|||
print("Point ($x, $y) is within triangle? "); |
|||
if (accuratePointInTriangle(x1, y1, x2, y2, x3, y3, x, y)) { |
|||
print("true"); |
|||
} else { |
|||
print("false"); |
|||
} |
|||
} |
|||
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); |
|||
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(''); |
|||
}</syntaxhighlight> |
|||
=={{header|Factor}}== |
=={{header|Factor}}== |