Rosetta Code

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

Page Discussion

Find if a point is within a triangle (view source)

Revision as of 12:53, 27 August 2022

1,135 bytes added ,  1 year ago
m
syntax highlighting fixup automation
(J)
m (syntax highlighting fixup automation)
Line 32:
{{trans|Kotlin}}
 
<langsyntaxhighlight lang="11l">V EPS = 0.001
V EPS_SQUARE = EPS * EPS
 
Line 104:
p3 = (-100.0 / 8, 100.0 / 6)
tri = Triangle(p1, p2, p3)
test(tri, pt)</langsyntaxhighlight>
 
{{out}}
Line 129:
It uses a generic two-dimensional geometry, that could be affine, euclidean, or a lot stranger than that. You only need to specify the type of one dimension, and the library ''should'' handle the rest. Edge cases probably exist where they shouldn't, as the area formula might add some imprecision.
 
<langsyntaxhighlight Adalang="ada">-- triangle.ads
generic
type Dimension is private;
Line 163:
with Inline;
end;
</syntaxhighlight>
</lang>
<langsyntaxhighlight Adalang="ada">-- triangle.adb
 
package body Triangle is
Line 185:
end IsPointInTriangle;
end;
</syntaxhighlight>
</lang>
<langsyntaxhighlight Adalang="ada">-- test_triangle.adb
with Ada.Text_IO;
use Ada.Text_IO;
Line 202:
Put_Line("IsPointInTriangle("&Image(origin)&", "&Image(tri2)&") yields "&IsPointInTriangle(origin,tri2)'Image);
end test_triangle;
</syntaxhighlight>
</lang>
 
{{out}}
Line 214:
With additional material
{{Trans|Wren}}
<langsyntaxhighlight lang="algol68">BEGIN # determine whether a point is within a triangle or not #
# tolerance for the accurate test #
REAL eps = 0.001;
Line 287:
, ( 0.1, 0.11111111111111 ), ( 12.5, 33.333333333333 ), ( -12.5, 16.666666666667 )
)
END</langsyntaxhighlight>
{{out}}
<pre>
Line 300:
 
=={{header|AutoHotkey}}==
<langsyntaxhighlight AutoHotkeylang="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"
Line 315:
TriArea(x1, y1, x2, y2, x3, y3){
return Abs((x1 * (y2-y3) + x2 * (y3-y1) + x3 * (y1-y2)) / 2)
}</langsyntaxhighlight>
{{out}}
<pre>[0, 0] is within triangle? ture
Line 324:
=={{header|C}}==
{{trans|Go}}
<langsyntaxhighlight lang="c">#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
Line 421:
 
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>Triangle is [(1.500000, 2.400000), (5.100000, -3.100000), (-3.800000, 1.200000)]
Line 438:
=={{header|C++}}==
{{trans|C}}
<langsyntaxhighlight lang="cpp">#include <iostream>
 
const double EPS = 0.001;
Line 533:
 
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>Triangle is [(1.5, 2.4), (5.1, -3.1), (-3.8, 1.2)]
Line 550:
 
=={{header|Common Lisp}}==
<syntaxhighlight lang="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
Line 581:
(- (car P) (car A)) ))))
 
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 602:
=={{header|D}}==
{{trans|C++}}
<langsyntaxhighlight lang="d">import std.algorithm; //.comparison for min and max
import std.stdio;
 
Line 692:
test(0.1, 0.1111111111111111, 12.5, 33.333333333333336, -12.5, 16.666666666666668, 5.414285714285714, 14.349206349206348);
writeln;
}</langsyntaxhighlight>
{{out}}
<pre>Triangle is [(1.5, 2.4), (5.1, -3.1), (-3.8, 1.2)]
Line 709:
=={{header|Factor}}==
Uses the parametric equations method from [https://totologic.blogspot.com/2014/01/accurate-point-in-triangle-test.html].
<langsyntaxhighlight lang="factor">USING: accessors fry io kernel locals math math.order sequences ;
 
TUPLE: point x y ;
Line 734:
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 '#'
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 760:
 
=={{header|Fortran}}==
<syntaxhighlight lang="fortran">
<lang Fortran>
PROGRAM POINT_WITHIN_TRIANGLE
 
Line 819:
 
END PROGRAM POINT_WITHIN_TRIANGLE
</syntaxhighlight>
</lang>
{{out}}<pre>
Point ( 0.0000000000000000 , 0.0000000000000000 ) is within triangle [( 1.5000000000000000 , 2.4000000953674316 ), ( 5.0999999046325684 , -3.0999999046325684 ), ( -3.7999999523162842 , 1.2000000476837158 )].
Line 825:
 
=={{header|FreeBASIC}}==
<langsyntaxhighlight lang="freebasic">
type p2d
x as double 'define a two-dimensional point
Line 855:
print
next y
</syntaxhighlight>
</lang>
{{out}}<pre>........................................
........................................
Line 880:
=={{header|Go}}==
{{trans|Wren}}
<langsyntaxhighlight lang="go">package main
 
import (
Line 971:
within = accuratePointInTriangle(x1, y1, x2, y2, x3, y3, x, y)
fmt.Println("Point", pt, "is within triangle ?", within)
}</langsyntaxhighlight>
 
{{out}}
Line 988:
 
=={{header|GW-BASIC}}==
<langsyntaxhighlight lang="gwbasic">10 PIT1X! = 3 : PIT1Y! = 1.3 : REM arbitrary triangle for demonstration
20 PIT2X! = 17.222 : PIT2Y! = 10
30 PIT3X! = 5.5 : PIT3Y! = 18.212
Line 1,012:
1110 IF PITXXS!+PITXXT!>=1 THEN RETURN
1120 PITRES% = 1
1130 RETURN</langsyntaxhighlight>
{{out}}<pre>.........................................
.........................................
Line 1,039:
The point to be tested is transformed by affine transformation which turns given triangle to the simplex: Triangle (0,0) (0,s) (s,0), where s is half of the triangles' area. After that criteria of overlapping become trivial. Affinity allows to avoid division, so all functions work for points on the integer, or rational, or even modular meshes as well.
 
<langsyntaxhighlight lang="haskell">type Pt a = (a, a)
 
data Overlapping = Inside | Outside | Boundary
Line 1,070:
(y <= s && y >= 0) &&
(x == 0 || y == 0 || y == s - x) -> Boundary
| otherwise -> Outside</langsyntaxhighlight>
 
Testing
<langsyntaxhighlight lang="haskell">tests = let
t1 = Triangle (2,0) (-1,2) (-2,-2)
bs = [(2,0), (-1,2), (-2,-2), (0,-1), (1/2,1), (-3/2,0)]
Line 1,093:
| i <- [-10..10] :: [Int] ]
| j <- [-5..5] :: [Int] ]
where t = Triangle (-8,-3) (8,1) (-1,4)</langsyntaxhighlight>
 
<pre>λ> tests
Line 1,116:
=={{header|J}}==
Implementation, using complex numbers to represent x,y coordinates:
<langsyntaxhighlight Jlang="j">area=: [:| 0.5-/ .*@,.+. NB. signed area of triangle
I3=: =i.3 NB. identity matrix
inside=: {{ (area y)=+/area"1|:(I3*x)+(1-I3)*y }}</langsyntaxhighlight>
 
This is based on the algorithm documented for the ada implementation: compute the area of triangles using the determinant method (we want the absolute area here), and check whether the triangles formed with the test point and the sides of the test triangle matches the area of the test triangle.
 
Examples:<langsyntaxhighlight Jlang="j"> 0j0 inside 1.5j2.4 5.1j_3.1 _3.8j1.2
1
0j1 inside 1.5j2.4 5.1j_3.1 _3.8j1.2
Line 1,131:
1
5.414285714285714j14.349206349206348 inside 0.1j1r9 12.5j100r3 _12.5j100r6
1</langsyntaxhighlight>
 
=={{header|Java}}==
{{trans|Go}}
<langsyntaxhighlight lang="java">import java.util.Objects;
 
public class FindTriangle {
Line 1,270:
test(tri, pt);
}
}</langsyntaxhighlight>
{{out}}
<pre>Triangle[(1.500000, 2.400000), (5.100000, -3.100000), (-3.800000, 1.200000)]
Line 1,296:
 
'''Preliminaries'''
<langsyntaxhighlight 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]);
Line 1,310:
 
def EPS: 0.001;
def EPS_SQUARE: EPS * EPS; </langsyntaxhighlight>
<langsyntaxhighlight lang="jq">def side(P1; P2; Q):
[P1, P2, Q]
| xy
Line 1,349:
elif distanceSquarePointToSegment(P3; P1; Q) <= EPS_SQUARE then true
else false
end;</langsyntaxhighlight>
'''Examples'''
<langsyntaxhighlight lang="jq">def task1:
def pts: [ [0, 0], [0, 1], [3, 1]];
"Triangle is \(.)",
Line 1,370:
([ [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)</langsyntaxhighlight>
{{out}}
<pre>
Line 1,388:
{{trans|Python}}
Using the Wren examples.
<langsyntaxhighlight lang="julia">Point(x, y) = [x, y]
Triangle(a, b, c) = [a, b, c]
LEzero(x) = x < 0 || isapprox(x, 0, atol=0.00000001)
Line 1,434:
end
end
</langsyntaxhighlight>{{out}}
<pre>
Using triangle [[1.5, 2.4], [0.51, -0.31], [-0.38, 1.2]]:
Line 1,457:
=={{header|Kotlin}}==
{{trans|Java}}
<langsyntaxhighlight lang="scala">import kotlin.math.max
import kotlin.math.min
 
Line 1,552:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>Triangle[(1.5, 2.4), (5.1, -3.1), (-3.8, 1.2)]
Line 1,569:
=={{header|Lua}}==
{{trans|C++}}
<langsyntaxhighlight lang="lua">EPS = 0.001
EPS_SQUARE = EPS * EPS
 
Line 1,653:
 
test(0.1, 0.1111111111111111, 12.5, 33.333333333333336, -12.5, 16.666666666666668, 5.414285714285714, 14.349206349206348)
print()</langsyntaxhighlight>
{{out}}
<pre>Triangle is [(1.5, 2.4), (5.1, -3.1), (-3.8, 1.2)]
Line 1,669:
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<langsyntaxhighlight Mathematicalang="mathematica">RegionMember[Polygon[{{1, 2}, {3, 1}, {2, 4}}], {2, 2}]</langsyntaxhighlight>
{{out}}
<pre>True</pre>
Line 1,675:
=={{header|Nim}}==
{{trans|Kotlin}}
<langsyntaxhighlight Nimlang="nim">import strformat
 
const
Line 1,760:
p3 = (-100 / 8, 100 / 6)
tri = initTriangle(p1, p2, p3)
test(tri, pt)</langsyntaxhighlight>
 
{{out}}
Line 1,778:
=={{header|Perl}}==
Translate the Java program at [https://totologic.blogspot.com/2014/01/accurate-point-in-triangle-test.html this blog post] and data set is taken from the [[Find_if_a_point_is_within_a_triangle#Raku|Raku]] entry.
<langsyntaxhighlight Perllang="perl"># 20201123 added Perl programming solution
 
use strict;
Line 1,840:
while ( my @vertex = $iter->()) { print '(',join(',',@vertex),') ' }
print ': ',naivePointInTriangle (@DATA, @$point) ? 'True' : 'False', "\n" ;
}</langsyntaxhighlight>
{{out}}
<pre>Point (0,0) is within triangle (1.5,2.4) (5.1,-3.1) (-3.8,0.5) : True
Line 1,850:
=== using convex_hull ===
Using convex_hull() from [[Convex_hull#Phix]]
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">p0</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},</span>
Line 1,862:
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Point %v is with triangle %v?:%t\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">triangle</span><span style="color: #0000FF;">,</span><span style="color: #000000;">inside</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">)})</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Point %v is with triangle %v?:%t\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">triangle</span><span style="color: #0000FF;">,</span><span style="color: #000000;">inside</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">)})</span>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 1,872:
===trans python===
(same output)
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">p0</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},</span>
Line 1,907:
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"point %v is with triangle %v?:%t\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">triangle</span><span style="color: #0000FF;">,</span><span style="color: #000000;">iswithin</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">triangle</span><span style="color: #0000FF;">)})</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"point %v is with triangle %v?:%t\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">triangle</span><span style="color: #0000FF;">,</span><span style="color: #000000;">iswithin</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">triangle</span><span style="color: #0000FF;">)})</span>
<!--</langsyntaxhighlight>-->
 
=={{header|Python}}==
<langsyntaxhighlight lang="python">
""" find if point is in a triangle """
 
Line 1,942:
isornot = "is" if iswithin(pnt, a, b, c) else "is not"
print("Point", pnt, isornot, "within the triangle", TRI)
</langsyntaxhighlight>{{out}}
<pre>
Point Point2D(0, 0) is within the triangle Triangle(Point2D(3/2, 12/5), Point2D(51/10, -31/10), Point2D(-19/5, 1/2))
Line 1,956:
I would probably use the dot-product version, if only because it requires less (no) division.
 
<langsyntaxhighlight lang="racket">#lang racket/base
 
(define-syntax-rule (all-between-0..1? x ...)
Line 2,003:
(run-tests point-in-triangle?/barycentric)
(run-tests point-in-triangle?/parametric)
(run-tests point-in-triangle?/dot-product))</langsyntaxhighlight>
 
{{out}}
Line 2,013:
Reusing code from the [[Convex_hull#Raku|Convex hull]] task and some logic from the [[Determine_if_two_triangles_overlap#Raku|Determine if two triangles overlap]] task.
 
<syntaxhighlight lang="raku" perl6line>class Point {
has Real $.x is rw;
has Real $.y is rw;
Line 2,040:
say "Point {$point.gist} is within triangle {join ', ', @triangle».gist}: ",
$point.&is-within: @triangle
}</langsyntaxhighlight>
{{out}}
<pre>Point (0, 0) is within triangle (1.5, 2.4), (5.1, -3.1), (-3.8, 0.5): True
Line 2,050:
 
<br>Extra certification code was added to verify that the &nbsp; '''X,Y''' &nbsp; coördinates for the points are not missing and are numeric.
<langsyntaxhighlight 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.*/
Line 2,066:
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&#2>=0&#3>=0) | (#1<=0&#2<=0&#3<=0)</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the default triangle and the point at: &nbsp; <tt> (0,0) </tt>}}
<pre>
Line 2,082:
=={{header|Ruby}}==
{{trans|Go}}
<langsyntaxhighlight lang="ruby">EPS = 0.001
EPS_SQUARE = EPS * EPS
 
Line 2,169:
end
 
main()</langsyntaxhighlight>
{{out}}
<pre>Triangle is [[1.5, 2.4], [5.1, -3.1], [-3.8, 1.2]]
Line 2,184:
=={{header|Vlang}}==
{{trans|go}}
<langsyntaxhighlight lang="vlang">import math
 
const eps = 0.001
Line 2,270:
within = accurate_point_in_triangle(x1, y1, x2, y2, x3, y3, x, y)
println("Point $pt is within triangle ? $within")
}</langsyntaxhighlight>
 
{{out}}
Line 2,288:
=={{header|Wren}}==
This is a translation of the ActionScript code for the 'accurate' method in the first referenced article above.
<langsyntaxhighlight lang="ecmascript">var EPS = 0.001
var EPS_SQUARE = EPS * EPS
 
Line 2,368:
y3 = tri[2][1]
within = accuratePointInTriangle.call(x1, y1, x2, y2, x3, y3, x, y)
System.print("Point %(pt) is within triangle ? %(within)")</langsyntaxhighlight>
 
{{out}}
Line 2,385:
 
=={{header|XPL0}}==
<langsyntaxhighlight XPL0lang="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);
Line 2,408:
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);
]</langsyntaxhighlight>
 
{{out}}
Thundergnat
10,327

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/327558"