Determine if two triangles overlap: Difference between revisions
Content added Content deleted
Alpha bravo (talk | contribs) (Added AutoHotkey) |
(adding lambdatalk) |
||
Line 1,896: | Line 1,896: | ||
do not overlap |
do not overlap |
||
</pre> |
</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}}== |
=={{header|Lua}}== |