Anonymous user
Determine if two triangles overlap: Difference between revisions
adding lambdatalk
Alpha bravo (talk | contribs) (Added AutoHotkey) |
(adding lambdatalk) |
||
Line 1,896:
do not overlap
</pre>
=={{header|Lambdatalk}}==
<lang scheme>
Here we present a rasterized version based on a single function "isInside".
1) isInside
Test if a point is inside a triangle
{def isInside
{lambda {p1 p2 p3 q}
{let { {x1 {car p1}} {y1 {cdr p1}}
{x2 {car p2}} {y2 {cdr p2}}
{x3 {car p3}} {y3 {cdr p3}}
{xp {car q}} {yp {cdr q}}
}
{let { {w1 {- {* {- xp x1} {- y3 y1}} {* {- x3 x1} {- yp y1}} }}
{w2 {- {* {- xp x2} {- y1 y2}} {* {- x1 x2} {- yp y2}} }}
{w3 {- {* {- xp x3} {- y2 y3}} {* {- x2 x3} {- yp y3}} }}
} {or {and {>= w1 0} {>= w2 0} {>= w3 0}}
{and {< w1 0} {< w2 0} {< w3 0}}} }}}}
-> isInside
2) overlapping
Test if a point is inside both triangles.
{def overlap
{def overlap.row
{lambda {:p0 :p1 :p2 :q0 :q1 :q2 :w :h :y}
{S.map {{lambda {:p0 :p1 :p2 :q0 :q1 :q2 :qp}
{if {and {isInside :p0 :p1 :p2 :qp}
{isInside :q0 :q1 :q2 :qp}}
then x else}} :p0 :p1 :p2 :q0 :q1 :q2}
{S.map {{lambda {:y :x} {cons :x :y}} :y}
{S.serie :w :h} }}}}
{lambda {:p0 :p1 :p2 :q0 :q1 :q2 :w :h}
{S.length {S.map {overlap.row :p0 :p1 :p2 :q0 :q1 :q2 :w :h}
{S.serie :w :h}} }}}
-> overlap
Given coordonnees will just be multiplied by 10 to become integers.
If the number of shared points is zero, triangles don't overlap.
{overlap {cons 0 0} {cons 50 0} {cons 0 50}
{cons 0 0} {cons 50 0} {cons 0 60} 0 60} -> 1326
{overlap {cons 0 0} {cons 0 50} {cons 50 0}
{cons 0 0} {cons 0 50} {cons 50 0} 0 50} -> 1176
{overlap {cons 0 0} {cons 50 0} {cons 0 50}
{cons -100 0} {cons -50 0} {cons -10 60} 100 60} -> 0
{overlap {cons 0 0} {cons 50 0} {cons 25 50}
{cons 0 40} {cons 25 -10} {cons 50 40} -10 50} -> 831
{overlap {cons 0 0} {cons 10 10} {cons 0 20}
{cons 20 10} {cons 30 0} {cons 30 20} 0 20} -> 0
{overlap {cons 0 0} {cons 10 10} {cons 0 20}
{cons 20 10} {cons 30 -20} {cons 40 40} -20 40} -> 0
{overlap {cons 0 0} {cons 10 0} {cons 0 10}
{cons 10 0} {cons 20 0} {cons 10 10} 0 20} -> 1
3) plot
The first triangle is plotted with 1s, the second with 2s,
the intersection with 3s, else with dots.
{def plot
{def plot.row
{lambda {:p0 :p1 :p2 :q0 :q1 :q2 :w :h :y}
{br}{S.replace \s by in
{S.map {{lambda {:p0 :p1 :p2 :q0 :q1 :q2 :qp}
{let { {:isinp {isInside :p0 :p1 :p2 :qp}}
{:isinq {isInside :q0 :q1 :q2 :qp}}
} {if {and :isinp :isinq} then 3
else {if :isnp then 1
else {if :isnq then 2
else .}}} }} :p0 :p1 :p2 :q0 :q1 :q2}
{S.map {{lambda {:y :x} {cons :x :y}} :y}
{S.serie :w :h} }}} }}
{lambda {:p0 :p1 :p2 :q0 :q1 :q2 :w :h}
{S.map {plot.row :p0 :p1 :p2 :q0 :q1 :q2 :w :h}
{S.serie :w :h}} }}
-> plot
{plot {cons 0 0} {cons 30 0} {cons 30 30}
{cons 5 10} {cons 25 10} {cons 5 25} 0 30}
->
1111111111111111111111111111111
.111111111111111111111111111111
..11111111111111111111111111111
...1111111111111111111111111111
....111111111111111111111111111
.....11111111111111111111111111
......1111111111111111111111111
.......111111111111111111111111
........11111111111111111111111
.........1111111111111111111111
.....22222333333333333333311111
.....22222233333333333331111111
.....22222223333333333311111111
.....22222222333333333111111111
.....22222222233333311111111111
.....22222222223333111111111111
.....22222222222331111111111111
.....22222222222.11111111111111
.....2222222222...1111111111111
.....222222222.....111111111111
.....2222222........11111111111
.....222222..........1111111111
.....22222............111111111
.....222...............11111111
.....22.................1111111
.....2...................111111
..........................11111
...........................1111
............................111
.............................11
..............................1
</lang>
=={{header|Lua}}==
| |||