Anonymous user
Find if a point is within a triangle: Difference between revisions
Find if a point is within a triangle (view source)
Revision as of 09:30, 2 December 2021
, 2 years ago→{{header|Haskell}}: added Haskell solution
(add gwbasic) |
(→{{header|Haskell}}: added Haskell solution) |
||
Line 881:
.........................................
</pre>
=={{header|Haskell}}==
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.
<lang haskell>type Pt a = (a, a)
data Overlapping = Inside | Outside | Boundary
deriving (Show, Eq)
data Triangle a = Triangle (Pt a) (Pt a) (Pt a)
deriving Show
vertices (Triangle a b c) = [a, b, c]
-- Performs the affine transformation
-- which turns a triangle to Triangle (0,0) (0,s) (s,0)
-- where s is half of the triangles' area
toTriangle :: Num a => Triangle a -> Pt a -> (a, Pt a)
toTriangle t (x,y) = let
[(x0,y0), (x1,y1), (x2,y2)] = vertices t
in ( x2*(y0-y1)+x0*(y1-y2)+x1*(-y0+y2)
, ( x2*(-y+y0)+x0*(y-y2)+x*(-y0+y2)
, x1*(y-y0)+x*(y0-y1)+x0*(-y+y1)))
-- returning the overlapping relation between
-- a triangle and a point
overlapping :: (Eq a, Ord a, Num a) =>
Triangle a -> Pt a -> Overlapping
overlapping t p = let
(s, (x, y)) = toTriangle t p
in case () of
() | s == 0 && (x == 0 && y == 0) -> Boundary
| s == 0 -> Outside
| x > 0 && y > 0 && y < s - x -> Inside
| x == 0 || y == 0 || y == s - x -> Boundary
| otherwise -> Outside</lang>
Testing
<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)]
is = [(0,0), (0,1), (-1,0), (-1,1), (-1,-1)]
os = [(1,1), (-2,2), (100,100), (2.00000001, 0)]
t2 = Triangle (1,2) (1,2) (-1,3)
ps = [(1,2), (0,5/2), (0,2), (1,3)]
in mapM_ print [ overlapping t1 <$> bs
, overlapping t1 <$> is
, overlapping t1 <$> os
, overlapping t2 <$> ps]</lang>
<pre>λ> tests
[Boundary,Boundary,Boundary,Boundary,Boundary,Boundary]
[Inside,Inside,Inside,Inside,Inside]
[Outside,Outside,Outside,Outside]
[Boundary,Boundary,Outside,Outside]</pre>
=={{header|Java}}==
| |||