Find if a point is within a triangle: Difference between revisions

Content added Content deleted
Line 801: Line 801:
</pre>
</pre>


=={{header|D}}==
=={{header|Rust}}==
{{trans|C++}}
{{trans|D}}
<syntaxhighlight lang="d">import std.algorithm; //.comparison for min and max
import std.stdio;


⚫
<syntaxhighlight lang="rust">
immutable EPS = 0.001;
const EPS: f64 = 0.001;
immutable EPS_SQUARE = EPS * EPS;
const EPS_SQUARE: f64 = EPS * EPS;


double side(double x1, double y1, double x2, double y2, double x, double y) {
fn side(x1: f64, y1: f64, x2: f64, y2: f64, x: f64, y: f64) -> f64 {
return (y2 - y1) * (x - x1) + (-x2 + x1) * (y - y1);
(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) {
fn naive_point_in_triangle(x1: f64, y1: f64, x2: f64, y2: f64, x3: f64, y3: f64, x: f64, y: f64) -> bool {
double checkSide1 = side(x1, y1, x2, y2, x, y) >= 0;
let check_side1 = side(x1, y1, x2, y2, x, y) >= 0.0;
double checkSide2 = side(x2, y2, x3, y3, x, y) >= 0;
let check_side2 = side(x2, y2, x3, y3, x, y) >= 0.0;
double checkSide3 = side(x3, y3, x1, y1, x, y) >= 0;
let check_side3 = side(x3, y3, x1, y1, x, y) >= 0.0;
return checkSide1 && checkSide2 && checkSide3;
check_side1 && check_side2 && check_side3
}
}


bool pointInTriangleBoundingBox(double x1, double y1, double x2, double y2, double x3, double y3, double x, double y) {
fn point_in_triangle_bounding_box(x1: f64, y1: f64, x2: f64, y2: f64, x3: f64, y3: f64, x: f64, y: f64) -> bool {
double xMin = min(x1, x2, x3) - EPS;
let x_min = f64::min(x1, f64::min(x2, x3)) - EPS;
double xMax = max(x1, x2, x3) + EPS;
let x_max = f64::max(x1, f64::max(x2, x3)) + EPS;
double yMin = min(y1, y2, y3) - EPS;
let y_min = f64::min(y1, f64::min(y2, y3)) - EPS;
double yMax = max(y1, y2, y3) + EPS;
let y_max = f64::max(y1, f64::max(y2, y3)) + EPS;
return !(x < xMin || xMax < x || y < yMin || yMax < y);
!(x < x_min || x_max < x || y < y_min || y_max < y)
}
}


fn distance_square_point_to_segment(x1: f64, y1: f64, x2: f64, y2: f64, x: f64, y: f64) -> f64 {
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);
let p1_p2_square_length = (x2 - x1).powi(2) + (y2 - y1).powi(2);
double dotProduct = ((x - x1) * (x2 - x1) + (y - y1) * (y2 - y1)) / p1_p2_squareLength;
let dot_product = ((x - x1) * (x2 - x1) + (y - y1) * (y2 - y1)) / p1_p2_square_length;
if (dotProduct < 0) {
if dot_product < 0.0 {
return (x - x1) * (x - x1) + (y - y1) * (y - y1);
(x - x1).powi(2) + (y - y1).powi(2)
} else if (dotProduct <= 1) {
} else if dot_product <= 1.0 {
double p_p1_squareLength = (x1 - x) * (x1 - x) + (y1 - y) * (y1 - y);
let p_p1_square_length = (x1 - x).powi(2) + (y1 - y).powi(2);
p_p1_square_length - dot_product.powi(2) * p1_p2_square_length
return p_p1_squareLength - dotProduct * dotProduct * p1_p2_squareLength;
} else {
} else {
return (x - x2) * (x - x2) + (y - y2) * (y - y2);
(x - x2).powi(2) + (y - y2).powi(2)
}
}
}
}


bool accuratePointInTriangle(double x1, double y1, double x2, double y2, double x3, double y3, double x, double y) {
fn accurate_point_in_triangle(x1: f64, y1: f64, x2: f64, y2: f64, x3: f64, y3: f64, x: f64, y: f64) -> bool {
if (!pointInTriangleBoundingBox(x1, y1, x2, y2, x3, y3, x, y)) {
if !point_in_triangle_bounding_box(x1, y1, x2, y2, x3, y3, x, y) {
return false;
return false;
}
}
if (naivePointInTriangle(x1, y1, x2, y2, x3, y3, x, y)) {
if naive_point_in_triangle(x1, y1, x2, y2, x3, y3, x, y) {
return true;
return true;
}
}
if (distanceSquarePointToSegment(x1, y1, x2, y2, x, y) <= EPS_SQUARE) {
if distance_square_point_to_segment(x1, y1, x2, y2, x, y) <= EPS_SQUARE {
return true;
return true;
}
}
if (distanceSquarePointToSegment(x2, y2, x3, y3, x, y) <= EPS_SQUARE) {
if distance_square_point_to_segment(x2, y2, x3, y3, x, y) <= EPS_SQUARE {
return true;
return true;
}
}
if (distanceSquarePointToSegment(x3, y3, x1, y1, x, y) <= EPS_SQUARE) {
if distance_square_point_to_segment(x3, y3, x1, y1, x, y) <= EPS_SQUARE {
return true;
return true;
}
}
return false;
false
}
}


fn print_point(x: f64, y: f64) {
void printPoint(double x, double y) {
write('(', x, ", ", y, ')');
print!("({}, {})", x, y);
}
}


void printTriangle(double x1, double y1, double x2, double y2, double x3, double y3) {
fn print_triangle(x1: f64, y1: f64, x2: f64, y2: f64, x3: f64, y3: f64) {
write("Triangle is [");
print!("Triangle is [");
printPoint(x1, y1);
print_point(x1, y1);
write(", ");
print!(", ");
printPoint(x2, y2);
print_point(x2, y2);
write(", ");
print!(", ");
printPoint(x3, y3);
print_point(x3, y3);
writeln(']');
println!("]");
}
}


void test(double x1, double y1, double x2, double y2, double x3, double y3, double x, double y) {
fn test(x1: f64, y1: f64, x2: f64, y2: f64, x3: f64, y3: f64, x: f64, y: f64) {
printTriangle(x1, y1, x2, y2, x3, y3);
print_triangle(x1, y1, x2, y2, x3, y3);
write("Point ");
print!("Point ");
printPoint(x, y);
print_point(x, y);
write(" is within triangle? ");
print!(" is within triangle? ");
writeln(accuratePointInTriangle(x1, y1, x2, y2, x3, y3, x, y));
println!("{}", accurate_point_in_triangle(x1, y1, x2, y2, x3, y3, x, y));
}
}


void main() {
fn 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.0, 0.0);
println!();
⚫
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);
⚫
test(1.5, 2.4, 5.1, -3.1, -3.8, 1.2, 0.0, 1.0);
writeln;
println!();

⚫
test(0.1, 0.1111111111111111, 12.5, 33.333333333333336, 25, 11.11111111111111, 5.414285714285714, 14.349206349206348);
⚫
test(1.5, 2.4, 5.1, -3.1, -3.8, 1.2, 3.0, 1.0);
writeln;
println!();

⚫
test(0.1, 0.1111111111111111, 12.5, 33.333333333333336, 25.0, 11.11111111111111, 5.414285714285714, 14.349206349206348);
println!();
test(0.1, 0.1111111111111111, 12.5, 33.333333333333336, -12.5, 16.666666666666668, 5.414285714285714, 14.349206349206348);
test(0.1, 0.1111111111111111, 12.5, 33.333333333333336, -12.5, 16.666666666666668, 5.414285714285714, 14.349206349206348);
writeln;
println!();
}
⚫
}</syntaxhighlight>
</syntaxhighlight>

{{out}}
{{out}}
<pre>
<pre>Triangle is [(1.5, 2.4), (5.1, -3.1), (-3.8, 1.2)]
Triangle is [(1.5, 2.4), (5.1, -3.1), (-3.8, 1.2)]
Point (0, 0) is within triangle? true
Point (0, 0) is within triangle? true

Triangle is [(1.5, 2.4), (5.1, -3.1), (-3.8, 1.2)]
Triangle is [(1.5, 2.4), (5.1, -3.1), (-3.8, 1.2)]
Point (0, 1) is within triangle? true
Point (0, 1) is within triangle? true

Triangle is [(1.5, 2.4), (5.1, -3.1), (-3.8, 1.2)]
Triangle is [(1.5, 2.4), (5.1, -3.1), (-3.8, 1.2)]
Point (3, 1) is within triangle? false
Point (3, 1) is within triangle? false


Triangle is [(0.1, 0.111111), (12.5, 33.3333), (25, 11.1111)]
Triangle is [(0.1, 0.1111111111111111), (12.5, 33.333333333333336), (25, 11.11111111111111)]
Point (5.41429, 14.3492) is within triangle? true
Point (5.414285714285714, 14.349206349206348) 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</pre>



⚫
Triangle is [(0.1, 0.1111111111111111), (12.5, 33.333333333333336), (-12.5, 16.666666666666668)]
⚫
Point (5.414285714285714, 14.349206349206348) is within triangle? true
</pre>


=={{header|Delphi}}==
=={{header|Delphi}}==
Retrieved from "https://rosettacode.org/wiki/Find_if_a_point_is_within_a_triangle"