Rosetta Code

Determine if two triangles overlap: Difference between revisions

Page Discussion

Determine if two triangles overlap (view source)

Revision as of 14:59, 14 July 2023

1,658 bytes added ,  11 months ago
→‎{{header|ooRexx}}: add test for triangles' validity
(Added ATS)
(→‎{{header|ooRexx}}: add test for triangles' validity)
Line 3,414:
* This was/is an exercise with ooRexx
* Removed the fraction arithmetic
* add test for triangles' validity
*-------------------------------------------------------------------*/
Parse Version v
 
oid='trioo.txt'; 'erase' oid
Call o v
Line 3,432:
Call trio_test '0 0 1 1 0 2 2 1 3 -2 3 4'
Call trio_test '0 0 1 0 0 1 1 0 2 0 1 1'
Call trio_test '0 0 0 0 2 2 1 1 2 1 1 2' -- two points are identical
Call trio_test '0 0 0 3 2 2 1 1 2 2 3 3' -- three points on a line
Exit
/* Other test cases */
Line 3,465 ⟶ 3,467:
tlist=space(tlist)
tl1=tlist ; Call trio_t tl1
If result=-1 Then Return
tl2=reversex(tlist) ; Call trio_t tl2
tl3=''
Line 3,475 ⟶ 3,478:
tl4=reversex(tl3) ; Call trio_t tl4
tl5=subword(tl4,7) subword(tl4,1,6) ; Call trio_t tl5
tl6=''
tl6=subword(tl5,7) subword(tl5,1,6) ; Call trio_t tl6
tl=tlist
Do While tl<>''
Parse Var tl x y tl
tl6=tl6 y x
End
Call trio_t tl6
Return
 
Line 3,481 ⟶ 3,490:
Parse Arg tlist
tlist=space(tlist)
Say '>' tlist
case+=1
Parse Arg ax ay bx by cx cy dx dy ex ey fx fy
Line 3,489 ⟶ 3,498:
a=.point~new(ax,ay); b=.point~new(bx,by); c=.point~new(cx,cy)
d=.point~new(dx,dy); e=.point~new(ex,ey); f=.point~new(fx,fy)
If area(a,b,c)=0 Then Do
Say a b c 'is not a valid triangle'
Return -1
End
If area(d,e,f)=0 Then Do
Say d e f 'is not a valid triangle'
Return -1
End
abc=.triangle~new(a,b,c)
def=.triangle~new(d,e,f)
Line 3,693 ⟶ 3,710:
expose point edge
use arg p1,p2,p3
If area(p1,p2,p3)=0 Then Do
Say p1 p2 p3 'is not a valid triangle!'
Return .nil
End
point=.array~new
point[1]=p1
Line 3,955 ⟶ 3,976:
res=res word(list,i)
End
Return res </syntaxhighlight>
 
::ROUTINE distpp PUBLIC --Compute the distance between the points A and B
/***********************************************************************
* Compute the distance between the points A and B
***********************************************************************/
Use Arg A,B
ax=A~x; ay=A~y; bx=B~x; by=B~y
res=rxCalcsqrt((bx-ax)**2+(by-ay)**2)
Return res
 
::ROUTINE area PUBLIC --Compute the area of the triangla A B C
/***********************************************************************
* Compute the area of the triangla A B C
***********************************************************************/
Use Arg A,B,C
ax=A~x; ay=A~y; bx=B~x; by=B~y; cx=C~x; cy=C~y
ab=distpp(A,B)
bc=distpp(B,C)
ca=distpp(C,A)
s=(ab+bc+ca)/2
area=rxCalcsqrt(s*(s-ab)*(s-bc)*(s-ca))
Return area
::REQUIRES rxMath Library</syntaxhighlight>
{{out}}
<pre> 0 0 4 0 0 4 1 1 2 1 1 2
Triangle: ABC: (0,0) (4,0) (0,4)
Triangle: DEF: (1,1) (2,1) (1,2)
(1,1) (2,1) (1,2) is fully contained in (0,0) (4,0) (0,4)
 
> 2 1 1 2 1 1 4 0 0 4 0 0
Triangle: ABC: (2,1) (1,2) (1,1)
Triangle: DEF: (4,0) (0,4) (0,0)
(2,1) (1,2) (1,1) is fully contained in (4,0) (0,4) (0,0)
 
> 1 2 2 1 1 1 0 4 4 0 0 0
Triangle: ABC: (1,2) (2,1) (1,1)
Triangle: DEF: (0,4) (4,0) (0,0)
(1,2) (2,1) (1,1) is fully contained in (0,4) (4,0) (0,0)
 
> 0 0 0 4 4 0 1 1 1 2 2 1
Triangle: ABC: (0,0) (0,4) (4,0)
Triangle: DEF: (1,1) (1,2) (2,1)
(1,1) (1,2) (2,1) is fully contained in (0,0) (0,4) (4,0)
 
> 1 1 1 2 2 1 0 0 0 4 4 0
Triangle: ABC: (1,1) (1,2) (2,1)
Triangle: DEF: (0,0) (0,4) (4,0)
(1,1) (1,2) (2,1) is fully contained in (0,0) (0,4) (4,0)
 
0> 01 01 4 4 0 12 1 1 2 20 10 4 0 0 4
Triangle: ABC: (01,01) (02,41) (41,02)
Triangle: DEF: (10,10) (14,20) (20,14)
(1,1) (1,2,1) (2,1,2) is fully contained in (0,0) (0,4,0) (4,0,4)
 
> 0 0 0 6 8 3 8 0 8 8 0 3
Triangle: ABC: (0,0) (0,6) (8,3)
Triangle: DEF: (8,0) (8,8) (0,3)
Corner(s) that touch the other triangle: (0,3) (8,3)
Triangles overlap and touch on (0,3) (8,3)
> 3 0 8 8 0 8 3 8 6 0 0 0
Triangle: ABC: (3,0) (8,8) (0,8)
Triangle: DEF: (3,8) (6,0) (0,0)
Corner(s) that touch the other triangle: (3,8) (3,0)
Triangles overlap and touch on (3,8) (3,0)
> 0 3 8 8 8 0 8 3 0 6 0 0
Triangle: ABC: (0,3) (8,8) (8,0)
Triangle: DEF: (8,3) (0,6) (0,0)
Corner(s) that touch the other triangle: (8,3) (0,3)
Triangles overlap and touch on (8,3) (0,3)
> 0 0 6 0 3 8 0 8 8 8 3 0
Triangle: ABC: (0,0) (6,0) (3,8)
Triangle: DEF: (0,8) (8,8) (3,0)
Corner(s) that touch the other triangle: (3,0) (3,8)
Triangles overlap and touch on (3,0) (3,8)
> 0 8 8 8 3 0 0 0 6 0 3 8
Triangle: ABC: (0,8) (8,8) (3,0)
Triangle: DEF: (0,0) (6,0) (3,8)
Corner(s) that touch the other triangle: (3,8) (3,0)
Triangles overlap and touch on (3,8) (3,0)
0> 8 0 68 8 0 3 80 0 80 86 8 3 0
Triangle: ABC: (08,0) (68,08) (30,83)
Triangle: DEF: (0,80) (80,86) (8,3,0)
Corner(s) that touch the other triangle: (38,03) (30,83)
Triangles overlap and touch on (38,03) (30,83)
> 0 0 0 2 2 0 0 0 4 0 0 6
Triangle: ABC: (0,0) (0,2) (2,0)
Triangle: DEF: (0,0) (4,0) (0,6)
Line 4,023 ⟶ 4,067:
Triangles overlap and touch on (0,0) (0,2) (2,0)
 
> 6 0 0 4 0 0 0 2 2 0 0 0
Triangle: ABC: (6,0) (0,4) (0,0)
Triangle: DEF: (0,2) (2,0) (0,0)
Line 4,029 ⟶ 4,073:
Triangles overlap and touch on (0,2) (2,0) (0,0)
 
> 0 6 4 0 0 0 2 0 0 2 0 0
Triangle: ABC: (0,6) (4,0) (0,0)
Triangle: DEF: (2,0) (0,2) (0,0)
Line 4,035 ⟶ 4,079:
Triangles overlap and touch on (2,0) (0,2) (0,0)
 
> 0 0 2 0 0 2 0 0 0 4 6 0
Triangle: ABC: (0,0) (2,0) (0,2)
Triangle: DEF: (0,0) (0,4) (6,0)
Line 4,041 ⟶ 4,085:
Triangles overlap and touch on (0,0) (2,0) (0,2)
 
> 0 0 0 4 6 0 0 0 2 0 0 2
Triangle: ABC: (0,0) (0,4) (6,0)
Triangle: DEF: (0,0) (2,0) (0,2)
Line 4,047 ⟶ 4,091:
Triangles overlap and touch on (0,0) (2,0) (0,2)
 
> 0 0 24 0 0 26 0 0 0 42 62 0
Triangle: ABC: (0,0) (24,0) (0,26)
Triangle: DEF: (0,0) (0,42) (62,0)
Corner(s) that touch the other triangle: (0,0) (2,0,2) (0,2,0)
Triangles overlap and touch on (0,0) (2,0,2) (0,2,0)
 
> 0 0 5 0 0 5 0 0 5 0 0 6
Triangle: ABC: (0,0) (5,0) (0,5)
Triangle: DEF: (0,0) (5,0) (0,6)
Line 4,059 ⟶ 4,103:
Triangles have an edge in common: (0,0) (5,0)
 
> 6 0 0 5 0 0 5 0 0 5 0 0
Triangle: ABC: (6,0) (0,5) (0,0)
Triangle: DEF: (5,0) (0,5) (0,0)
Line 4,065 ⟶ 4,109:
Triangles have an edge in common: (0,5) (0,0)
 
> 0 6 5 0 0 0 0 5 5 0 0 0
Triangle: ABC: (0,6) (5,0) (0,0)
Triangle: DEF: (0,5) (5,0) (0,0)
Line 4,071 ⟶ 4,115:
Triangles have an edge in common: (5,0) (0,0)
 
> 0 0 0 5 5 0 0 0 0 5 6 0
Triangle: ABC: (0,0) (0,5) (5,0)
Triangle: DEF: (0,0) (0,5) (6,0)
Line 4,077 ⟶ 4,121:
Triangles have an edge in common: (0,0) (0,5)
 
> 0 0 0 5 6 0 0 0 0 5 5 0
Triangle: ABC: (0,0) (0,5) (6,0)
Triangle: DEF: (0,0) (0,5) (5,0)
Line 4,083 ⟶ 4,127:
Triangles have an edge in common: (0,0) (0,5)
 
0> 0 0 5 5 0 0 6 0 0 5 60 0 5
Triangle: ABC: (0,0) (5,0,5) (50,06)
Triangle: DEF: (0,0) (0,5,0) (6,0,5)
Corner(s) that touch the other triangle: (0,0) (0,5,0) (5,0,5)
Triangles have an edge in common: (0,0) (0,5,0)
 
> 0 0 0 5 5 0 0 0 0 5 5 0
Triangle: ABC: (0,0) (0,5) (5,0)
Triangle: DEF: (0,0) (0,5) (5,0)
Line 4,095 ⟶ 4,139:
Triangles are identical
 
> 0 5 5 0 0 0 0 5 5 0 0 0
Triangle: ABC: (0,5) (5,0) (0,0)
Triangle: DEF: (0,5) (5,0) (0,0)
Line 4,101 ⟶ 4,145:
Triangles are identical
 
> 5 0 0 5 0 0 5 0 0 5 0 0
Triangle: ABC: (5,0) (0,5) (0,0)
Triangle: DEF: (5,0) (0,5) (0,0)
Line 4,107 ⟶ 4,151:
Triangles are identical
 
> 0 0 5 0 0 5 0 0 5 0 0 5
Triangle: ABC: (0,0) (5,0) (0,5)
Triangle: DEF: (0,0) (5,0) (0,5)
Line 4,113 ⟶ 4,157:
Triangles are identical
 
> 0 0 5 0 0 5 0 0 5 0 0 5
Triangle: ABC: (0,0) (5,0) (0,5)
Triangle: DEF: (0,0) (5,0) (0,5)
Line 4,119 ⟶ 4,163:
Triangles are identical
 
0> 0 5 0 0 5 5 0 0 5 0 0 5 5 0
Triangle: ABC: (0,0) (5,0,5) (0,5,0)
Triangle: DEF: (0,0) (5,0,5) (0,5,0)
Corner(s) that touch the other triangle: (0,0) (5,0,5) (0,5,0)
Triangles are identical
 
> 0 0 5 0 0 5 -10 0 -5 0 -1 6
Triangle: ABC: (0,0) (5,0) (0,5)
Triangle: DEF: (-10,0) (-5,0) (-1,6)
(0,0) (5,0) (0,5) and (-10,0) (-5,0) (-1,6) don't overlap
 
> 6 -1 0 -5 0 -10 5 0 0 5 0 0
Triangle: ABC: (6,-1) (0,-5) (0,-10)
Triangle: DEF: (5,0) (0,5) (0,0)
(6,-1) (0,-5) (0,-10) and (5,0) (0,5) (0,0) don't overlap
 
> -1 6 -5 0 -10 0 0 5 5 0 0 0
Triangle: ABC: (-1,6) (-5,0) (-10,0)
Triangle: DEF: (0,5) (5,0) (0,0)
(-1,6) (-5,0) (-10,0) and (0,5) (5,0) (0,0) don't overlap
 
> 0 0 0 5 5 0 0 -10 0 -5 6 -1
Triangle: ABC: (0,0) (0,5) (5,0)
Triangle: DEF: (0,-10) (0,-5) (6,-1)
(0,0) (0,5) (5,0) and (0,-10) (0,-5) (6,-1) don't overlap
 
> 0 -10 0 -5 6 -1 0 0 0 5 5 0
Triangle: ABC: (0,-10) (0,-5) (6,-1)
Triangle: DEF: (0,0) (0,5) (5,0)
(0,-10) (0,-5) (6,-1) and (0,0) (0,5) (5,0) don't overlap
 
0> 0-10 0 5 -5 0 0 -101 6 0 0 -5 60 -10 5
Triangle: ABC: (0-10,0) (-5,0,5) (5-1,06)
Triangle: DEF: (0,-100) (0,-5,0) (60,-15)
(0-10,0) (0,-5,0) (5-1,06) and (0,-100) (0,-5,0) (60,-15) don't overlap
 
> 0 0 5 0 2.5 5 0 4 2.5 -1 5 4
Triangle: ABC: (0,0) (5,0) (2.5,5)
Triangle: DEF: (0,4) (2.5,-1) (5,4)
(0,0) (5,0) (2.5,5) and (0,4) (2.5,-1) (5,4) overlap
 
> 4 5 -1 2.5 4 0 5 2.5 0 5 0 0
Triangle: ABC: (4,5) (-1,2.5) (4,0)
Triangle: DEF: (5,2.5) (0,5) (0,0)
(4,5) (-1,2.5) (4,0) and (5,2.5) (0,5) (0,0) overlap
 
> 5 4 2.5 -1 0 4 2.5 5 5 0 0 0
Triangle: ABC: (5,4) (2.5,-1) (0,4)
Triangle: DEF: (2.5,5) (5,0) (0,0)
(5,4) (2.5,-1) (0,4) and (2.5,5) (5,0) (0,0) overlap
 
> 0 0 0 5 5 2.5 4 0 -1 2.5 4 5
Triangle: ABC: (0,0) (0,5) (5,2.5)
Triangle: DEF: (4,0) (-1,2.5) (4,5)
(0,0) (0,5) (5,2.5) and (4,0) (-1,2.5) (4,5) overlap
 
> 4 0 -1 2.5 4 5 0 0 0 5 5 2.5
Triangle: ABC: (4,0) (-1,2.5) (4,5)
Triangle: DEF: (0,0) (0,5) (5,2.5)
(4,0) (-1,2.5) (4,5) and (0,0) (0,5) (5,2.5) overlap
 
0> 0 04 2.5 5-1 2.5 4 0 -10 5 0 2.5 4 5
Triangle: ABC: (0,04) (02.5,5-1) (5,2.54)
Triangle: DEF: (40,0) (-1,2.5,0) (42.5,5)
(0,04) (0,2.5,-1) (5,2.54) and (40,0) (-1,2.5,0) (42.5,5) overlap
 
> 0 0 1 1 0 2 2 1 3 0 3 2
Triangle: ABC: (0,0) (1,1) (0,2)
Triangle: DEF: (2,1) (3,0) (3,2)
(0,0) (1,1) (0,2) and (2,1) (3,0) (3,2) don't overlap
 
> 2 3 0 3 1 2 2 0 1 1 0 0
Triangle: ABC: (2,3) (0,3) (1,2)
Triangle: DEF: (2,0) (1,1) (0,0)
(2,3) (0,3) (1,2) and (2,0) (1,1) (0,0) don't overlap
 
> 3 2 3 0 2 1 0 2 1 1 0 0
Triangle: ABC: (3,2) (3,0) (2,1)
Triangle: DEF: (0,2) (1,1) (0,0)
(3,2) (3,0) (2,1) and (0,2) (1,1) (0,0) don't overlap
 
> 0 0 1 1 2 0 1 2 0 3 2 3
Triangle: ABC: (0,0) (1,1) (2,0)
Triangle: DEF: (1,2) (0,3) (2,3)
(0,0) (1,1) (2,0) and (1,2) (0,3) (2,3) don't overlap
 
> 1 2 0 3 2 3 0 0 1 1 2 0
Triangle: ABC: (1,2) (0,3) (2,3)
Triangle: DEF: (0,0) (1,1) (2,0)
(1,2) (0,3) (2,3) and (0,0) (1,1) (2,0) don't overlap
 
0> 02 1 13 0 3 2 0 0 1 21 0 3 2 3
Triangle: ABC: (02,01) (13,10) (3,2,0)
Triangle: DEF: (10,20) (01,31) (20,32)
(02,01) (13,10) (23,02) and (10,20) (01,31) (20,32) don't overlap
 
> 0 0 1 1 0 2 2 1 3 -2 3 4
Triangle: ABC: (0,0) (1,1) (0,2)
Triangle: DEF: (2,1) (3,-2) (3,4)
(0,0) (1,1) (0,2) and (2,1) (3,-2) (3,4) don't overlap
 
> 4 3 -2 3 1 2 2 0 1 1 0 0
Triangle: ABC: (4,3) (-2,3) (1,2)
Triangle: DEF: (2,0) (1,1) (0,0)
(4,3) (-2,3) (1,2) and (2,0) (1,1) (0,0) don't overlap
 
> 3 4 3 -2 2 1 0 2 1 1 0 0
Triangle: ABC: (3,4) (3,-2) (2,1)
Triangle: DEF: (0,2) (1,1) (0,0)
(3,4) (3,-2) (2,1) and (0,2) (1,1) (0,0) don't overlap
 
> 0 0 1 1 2 0 1 2 -2 3 4 3
Triangle: ABC: (0,0) (1,1) (2,0)
Triangle: DEF: (1,2) (-2,3) (4,3)
(0,0) (1,1) (2,0) and (1,2) (-2,3) (4,3) don't overlap
 
> 1 2 -2 3 4 3 0 0 1 1 2 0
Triangle: ABC: (1,2) (-2,3) (4,3)
Triangle: DEF: (0,0) (1,1) (2,0)
(1,2) (-2,3) (4,3) and (0,0) (1,1) (2,0) don't overlap
 
0 0 1 1> 2 0 1 23 -2 3 4 30 0 1 1 0 2
Triangle: ABC: (02,01) (13,1-2) (23,04)
Triangle: DEF: (10,20) (-21,31) (40,32)
(02,01) (13,1-2) (23,04) and (10,20) (-21,31) (40,32) don't overlap
 
> 0 0 1 0 0 1 1 0 2 0 1 1
Triangle: ABC: (0,0) (1,0) (0,1)
Triangle: DEF: (1,0) (2,0) (1,1)
Line 4,253 ⟶ 4,297:
(0,0) (1,0) (0,1) and (1,0) (2,0) (1,1) don't overlap but touch on (1,0)
 
> 1 1 0 2 0 1 1 0 0 1 0 0
Triangle: ABC: (1,1) (0,2) (0,1)
Triangle: DEF: (1,0) (0,1) (0,0)
Line 4,261 ⟶ 4,305:
(1,1) (0,2) (0,1) and (1,0) (0,1) (0,0) don't overlap but touch on (0,1)
 
> 1 1 2 0 1 0 0 1 1 0 0 0
Triangle: ABC: (1,1) (2,0) (1,0)
Triangle: DEF: (0,1) (1,0) (0,0)
Line 4,269 ⟶ 4,313:
(1,1) (2,0) (1,0) and (0,1) (1,0) (0,0) overlap and touch on (1,0)
 
> 0 0 0 1 1 0 0 1 0 2 1 1
Triangle: ABC: (0,0) (0,1) (1,0)
Triangle: DEF: (0,1) (0,2) (1,1)
Line 4,277 ⟶ 4,321:
(0,0) (0,1) (1,0) and (0,1) (0,2) (1,1) don't overlap but touch on (0,1)
 
> 0 1 0 2 1 1 0 0 0 1 1 0
Triangle: ABC: (0,1) (0,2) (1,1)
Triangle: DEF: (0,0) (0,1) (1,0)
Line 4,285 ⟶ 4,329:
(0,1) (0,2) (1,1) and (0,0) (0,1) (1,0) don't overlap but touch on (0,1)
 
0> 1 0 2 0 1 1 0 0 1 0 2 10 1
Triangle: ABC: (01,0) (2,0,1) (1,01)
Triangle: DEF: (0,10) (01,20) (10,1)
Corner(s) that touch the other triangle: (0,1,0)
Triangles touch on (0,1,0)
we analyze further
(01,0) (02,10) (1,01) and (0,10) (01,20) (10,1) don't overlap but touch on (0,1,0)</pre>
 
> 0 0 0 0 2 2 1 1 2 1 1 2
(0,0) (0,0) (2,2) is not a valid triangle
> 0 0 0 3 2 2 1 1 2 2 3 3
(1,1) (2,2) (3,3) is not a valid triangle</pre>
 
=={{header|Pascal}}==
Walterpachl
2,295

edits

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