Determine if two triangles overlap: Difference between revisions
Walterpachl (talk | contribs) →{{header|ooRexx}}: fix one bug (found by more testing |
Walterpachl (talk | contribs) →{{header|ooRexx}}: removed the fraction arithmetic (was a false Alarm?) |
||
Line 154: | Line 154: | ||
<lang oorexx>/*-------------------------------------------------------------------- |
<lang oorexx>/*-------------------------------------------------------------------- |
||
* Determine if two triangles overlap |
* Determine if two triangles overlap |
||
* The fraction arithmetic avoids problems with floating point values |
|||
* Fully (?) tested with integer coordinates of the 6 corners |
* Fully (?) tested with integer coordinates of the 6 corners |
||
* This was/is an exercise with ooRexx |
* This was/is an exercise with ooRexx |
||
* Removed the fraction arithmetic |
|||
*-------------------------------------------------------------------*/ |
*-------------------------------------------------------------------*/ |
||
Parse Version v |
Parse Version v |
||
Line 162: | Line 162: | ||
oid='trioo.txt'; 'erase' oid |
oid='trioo.txt'; 'erase' oid |
||
Call o v |
Call o v |
||
case=0 |
|||
cc=0 |
|||
Call trio_test '0 0 4 0 0 4 1 1 2 1 1 2' |
|||
Call trio_test '0 0 0 6 8 3 8 0 8 8 0 3' |
|||
Call trio_test '0 0 0 2 2 0 0 0 4 0 0 6' |
|||
/* The task's specified input */ |
/* The task's specified input */ |
||
Call trio_test '0 0 5 0 0 5 0 0 5 0 0 6' |
Call trio_test '0 0 5 0 0 5 0 0 5 0 0 6' |
||
Line 195: | Line 199: | ||
Call trio_test '2 0 2 6 1 8 0 1 0 5 8 3' |
Call trio_test '2 0 2 6 1 8 0 1 0 5 8 3' |
||
Call trio_test '0 0 4 0 0 4 1 1 2 1 1 2' |
Call trio_test '0 0 4 0 0 4 1 1 2 1 1 2' |
||
Say case 'cases tested' |
|||
Say cc |
|||
Exit |
Exit |
||
trio_test: |
trio_test: |
||
Parse Arg tlist |
|||
cc+=1 |
|||
tlist=space(tlist) |
|||
⚫ | |||
tl2=reversex(tlist) ; Call trio_t tl2 |
|||
tl3='' |
|||
tl=tlist |
|||
Do While tl<>'' |
|||
⚫ | |||
tl3=tl3 y x |
|||
⚫ | |||
⚫ | |||
tl4=reversex(tl3) ; Call trio_t tl4 |
|||
tl5=subword(tl4,7) subword(tl4,1,6) ; Call trio_t tl5 |
|||
tl6=subword(tl5,7) subword(tl5,1,6) ; Call trio_t tl6 |
|||
⚫ | |||
trio_t: |
|||
Parse Arg tlist |
Parse Arg tlist |
||
tlist=space(tlist) |
tlist=space(tlist) |
||
Say tlist |
|||
case+=1 |
|||
Parse Arg ax ay bx by cx cy dx dy ex ey fx fy |
Parse Arg ax ay bx by cx cy dx dy ex ey fx fy |
||
/*--------------------------------------------------------------------- |
/*--------------------------------------------------------------------- |
||
Line 282: | Line 308: | ||
End |
End |
||
Call o '',1 |
Call o '',1 |
||
-- Pull . |
|||
Return |
Return |
||
End |
End |
||
Line 292: | Line 318: | ||
Call o 'Triangles overlap and touch on' bordl,1 |
Call o 'Triangles overlap and touch on' bordl,1 |
||
Call o '' |
Call o '' |
||
-- Pull . |
|||
Return |
Return |
||
End |
End |
||
Line 385: | Line 411: | ||
call o abc 'and' def 'overlap',1 |
call o abc 'and' def 'overlap',1 |
||
Call o '',1 |
Call o '',1 |
||
Pull . |
-- Pull . |
||
End |
End |
||
Return |
Return |
||
Line 457: | Line 483: | ||
Select |
Select |
||
When ka.1='*' Then Do |
When ka.1='*' Then Do |
||
y2= |
y2=ka.2*pp~x+da.2 |
||
y3= |
y3=ka.3*pp~x+da.3 |
||
res=between(y2,pp~y,y3) |
res=between(y2,pp~y,y3) |
||
End |
End |
||
When ka.2='*' Then Do |
When ka.2='*' Then Do |
||
y2= |
y2=ka.1*pp~x+da.1 |
||
res=between(p1~y,y2,p2~y) |
res=between(p1~y,y2,p2~y) |
||
End |
End |
||
Otherwise Do |
Otherwise Do |
||
dap= |
dap=pp~y-ka.1*pp~x |
||
If ka.3='*' Then |
If ka.3='*' Then |
||
x3=xa.3 |
x3=xa.3 |
||
Else |
Else |
||
x3= |
x3=(da.3-dap)/(ka.1-ka.3) |
||
x2= |
x2=(da.2-dap)/(ka.1-ka.2) |
||
res=between(x2,pp~x,x3) |
res=between(x2,pp~x,x3) |
||
End |
End |
||
Line 513: | Line 539: | ||
End |
End |
||
Else Do |
Else Do |
||
ka= |
ka=(y2-y1)/(x2-x1) |
||
da= |
da=y2-ka*x2 |
||
xa='*' |
xa='*' |
||
End |
End |
||
Line 527: | Line 553: | ||
End |
End |
||
Else Do |
Else Do |
||
ey= |
ey=k*p~x+d |
||
res=(ey=p~y)&between(p1~x,p~x,p2~x,'I') |
res=(ey=p~y)&between(p1~x,p~x,p2~x,'I') |
||
End |
End |
||
Line 554: | Line 580: | ||
Else Do |
Else Do |
||
Call o 'kb='kb 'xa='||xa 'db='db |
Call o 'kb='kb 'xa='||xa 'db='db |
||
yy= |
yy=kb*xa+db |
||
res=between(q1~y,yy,q2~y) |
res=between(q1~y,yy,q2~y) |
||
End |
End |
||
End |
End |
||
When kb='*' Then Do |
When kb='*' Then Do |
||
yy= |
yy=ka*xb+da |
||
res=between(p1~y,yy,p2~y) |
res=between(p1~y,yy,p2~y) |
||
End |
End |
||
Line 575: | Line 601: | ||
End |
End |
||
Otherwise Do |
Otherwise Do |
||
x= |
x=(db-da)/(ka-kb) |
||
y= |
y=ka*x+da |
||
Call o 'cross:' x y |
Call o 'cross:' x y |
||
res=between(p1~x,x,p2~x) |
res=between(p1~x,x,p2~x) |
||
Line 605: | Line 631: | ||
Call o a x b 'res='res |
Call o a x b 'res='res |
||
Return res |
Return res |
||
⚫ | |||
⚫ | |||
⚫ | |||
Parse Var b bnom '/' bdenom |
|||
If adenom='' Then adenom=1 |
|||
If bdenom='' Then bdenom=1 |
|||
res=anom*bdenom'/'bnom*adenom |
|||
⚫ | |||
::routine multiply /* multiply two fractions */ |
|||
Use Arg a,b |
|||
Parse Var a anom '/' adenom |
|||
Parse Var b bnom '/' bdenom |
|||
If adenom='' Then adenom=1 |
|||
If bdenom='' Then bdenom=1 |
|||
res=anom*bnom'/'adenom*bdenom |
|||
Return reduce(res) |
|||
::routine subtract /* subtract two fractions */ |
|||
Use Arg a,b |
|||
Parse Var a anom '/' adenom |
|||
Parse Var b bnom '/' bdenom |
|||
If adenom='' Then adenom=1 |
|||
If bdenom='' Then bdenom=1 |
|||
res=(anom*bdenom-bnom*adenom)'/'adenom*bdenom |
|||
Return reduce(res) |
|||
⚫ | |||
Use Arg a,b |
|||
Parse Var a anom '/' adenom |
|||
Parse Var b bnom '/' bdenom |
|||
If adenom='' Then adenom=1 |
|||
If bdenom='' Then bdenom=1 |
|||
res=(anom*bdenom+bnom*adenom)'/'adenom*bdenom |
|||
Return reduce(res) |
|||
::routine reduce /* cancel a fraction */ |
|||
Use Arg a |
|||
Parse Var a anom '/' adenom |
|||
If adenom<0 Then Do |
|||
anom=-anom |
|||
adenom=-adenom |
|||
⚫ | |||
k=gcd(anom,adenom) |
|||
If adenom=k Then |
|||
res=anom/k |
|||
Else |
|||
res=(anom/k)'/'||(adenom/k) |
|||
⚫ | |||
::routine gcd /* greatest common divisor */ |
|||
Use Arg a,b |
|||
if b = 0 then return abs(a) |
|||
return gcd(b,a//b) |
|||
::routine show_g /* show a straight line's forula */ |
::routine show_g /* show a straight line's forula */ |
||
Line 696: | Line 672: | ||
::routine draw |
::routine draw |
||
Use Arg pixl |
Use Arg pixl |
||
Return /* remove to see the triangle corners */ |
Return /* remove to see the triangle corners */ |
||
Say 'pixl='pixl |
Say 'pixl='pixl |
||
pix.=' ' |
pix.=' ' |
||
Line 714: | Line 690: | ||
Say ol |
Say ol |
||
End |
End |
||
Return |
Return |
||
::routine reversex |
|||
⚫ | |||
n=words(list) |
|||
res=word(list,n) |
|||
Do i=n-1 to 1 By -1 |
|||
res=res word(list,i) |
|||
End |
|||
⚫ | |||
{{out}} |
{{out}} |
||
<pre>Triangle: ABC: (0,0) (5,0) (0,5) |
<pre>Triangle: ABC: (0,0) (5,0) (0,5) |
Revision as of 12:00, 12 January 2017
Determining if two triangles in the same plane overlap is an important topic in collision detection.
- Task
Determine which of these pairs of triangles overlap in 2D:
- (0,0),(5,0),(0,5) and (0,0),(5,0),(0,6)
- (0,0),(0,5),(5,0) and (0,0),(0,5),(5,0)
- (0,0),(5,0),(0,5) and (-10,0),(-5,0),(-1,6)
- (0,0),(5,0),(2.5,5) and (0,4),(2.5,-1),(5,4)
- (0,0),(1,1),(0,2) and (2,1),(3,0),(3,2)
- (0,0),(1,1),(0,2) and (2,1),(3,-2),(3,4)
Optionally, see what the result is when only a single corner is in contact (there is no definitively correct answer):
- (0,0),(1,0),(0,1) and (1,0),(2,0),(1,1)
C++
<lang cpp>#include <vector>
- include <iostream>
- include <stdexcept>
using namespace std;
typedef std::pair<double, double> TriPoint;
inline double Det2D(TriPoint &p1, TriPoint &p2, TriPoint &p3) { return +p1.first*(p2.second-p3.second) +p2.first*(p3.second-p1.second) +p3.first*(p1.second-p2.second); }
void CheckTriWinding(TriPoint &p1, TriPoint &p2, TriPoint &p3, bool allowReversed) { double detTri = Det2D(p1, p2, p3); if(detTri < 0.0) { if (allowReversed) { TriPoint a = p3; p3 = p2; p2 = a; } else throw std::runtime_error("triangle has wrong winding direction"); } }
bool BoundaryCollideChk(TriPoint &p1, TriPoint &p2, TriPoint &p3, double eps) { return Det2D(p1, p2, p3) < eps; }
bool BoundaryDoesntCollideChk(TriPoint &p1, TriPoint &p2, TriPoint &p3, double eps) { return Det2D(p1, p2, p3) <= eps; }
bool TriTri2D(TriPoint *t1, TriPoint *t2, double eps = 0.0, bool allowReversed = false, bool onBoundary = true) { //Trangles must be expressed anti-clockwise CheckTriWinding(t1[0], t1[1], t1[2], allowReversed); CheckTriWinding(t2[0], t2[1], t2[2], allowReversed);
bool (*chkEdge)(TriPoint &, TriPoint &, TriPoint &, double) = NULL; if(onBoundary) //Points on the boundary are considered as colliding chkEdge = BoundaryCollideChk; else //Points on the boundary are not considered as colliding chkEdge = BoundaryDoesntCollideChk;
//For edge E of trangle 1, for(int i=0; i<3; i++) { int j=(i+1)%3;
//Check all points of trangle 2 lay on the external side of the edge E. If //they do, the triangles do not collide. if (chkEdge(t1[i], t1[j], t2[0], eps) && chkEdge(t1[i], t1[j], t2[1], eps) && chkEdge(t1[i], t1[j], t2[2], eps)) return false; }
//For edge E of trangle 2, for(int i=0; i<3; i++) { int j=(i+1)%3;
//Check all points of trangle 1 lay on the external side of the edge E. If //they do, the triangles do not collide. if (chkEdge(t2[i], t2[j], t1[0], eps) && chkEdge(t2[i], t2[j], t1[1], eps) && chkEdge(t2[i], t2[j], t1[2], eps)) return false; }
//The triangles collide return true; }
int main() { {TriPoint t1[] = {TriPoint(0,0),TriPoint(5,0),TriPoint(0,5)}; TriPoint t2[] = {TriPoint(0,0),TriPoint(5,0),TriPoint(0,6)}; cout << TriTri2D(t1, t2) << "," << true << endl;}
{TriPoint t1[] = {TriPoint(0,0),TriPoint(0,5),TriPoint(5,0)}; TriPoint t2[] = {TriPoint(0,0),TriPoint(0,5),TriPoint(5,0)}; cout << TriTri2D(t1, t2, 0.0, true) << "," << true << endl;}
{TriPoint t1[] = {TriPoint(0,0),TriPoint(5,0),TriPoint(0,5)}; TriPoint t2[] = {TriPoint(-10,0),TriPoint(-5,0),TriPoint(-1,6)}; cout << TriTri2D(t1, t2) << "," << false << endl;}
{TriPoint t1[] = {TriPoint(0,0),TriPoint(5,0),TriPoint(2.5,5)}; TriPoint t2[] = {TriPoint(0,4),TriPoint(2.5,-1),TriPoint(5,4)}; cout << TriTri2D(t1, t2) << "," << true << endl;}
{TriPoint t1[] = {TriPoint(0,0),TriPoint(1,1),TriPoint(0,2)}; TriPoint t2[] = {TriPoint(2,1),TriPoint(3,0),TriPoint(3,2)}; cout << TriTri2D(t1, t2) << "," << false << endl;}
{TriPoint t1[] = {TriPoint(0,0),TriPoint(1,1),TriPoint(0,2)}; TriPoint t2[] = {TriPoint(2,1),TriPoint(3,-2),TriPoint(3,4)}; cout << TriTri2D(t1, t2) << "," << false << endl;}
//Barely touching {TriPoint t1[] = {TriPoint(0,0),TriPoint(1,0),TriPoint(0,1)}; TriPoint t2[] = {TriPoint(1,0),TriPoint(2,0),TriPoint(1,1)}; cout << TriTri2D(t1, t2, 0.0, false, true) << "," << true << endl;}
//Barely touching {TriPoint t1[] = {TriPoint(0,0),TriPoint(1,0),TriPoint(0,1)}; TriPoint t2[] = {TriPoint(1,0),TriPoint(2,0),TriPoint(1,1)}; cout << TriTri2D(t1, t2, 0.0, false, false) << "," << false << endl;}
}</lang>
- Output:
1,1 1,1 0,0 1,1 0,0 0,0 1,1 0,0
ooRexx
<lang oorexx>/*--------------------------------------------------------------------
- Determine if two triangles overlap
- Fully (?) tested with integer coordinates of the 6 corners
- This was/is an exercise with ooRexx
- Removed the fraction arithmetic
- -------------------------------------------------------------------*/
Parse Version v
oid='trioo.txt'; 'erase' oid Call o v case=0 cc=0 Call trio_test '0 0 4 0 0 4 1 1 2 1 1 2' Call trio_test '0 0 0 6 8 3 8 0 8 8 0 3' Call trio_test '0 0 0 2 2 0 0 0 4 0 0 6' /* The task's specified input */ Call trio_test '0 0 5 0 0 5 0 0 5 0 0 6' Call trio_test '0 0 0 5 5 0 0 0 0 5 5 0' Call trio_test '0 0 5 0 0 5 -10 0 -5 0 -1 6' Call trio_test '0 0 5 0 2.5 5 0 4 2.5 -1 5 4' Call trio_test '0 0 1 1 0 2 2 1 3 0 3 2' 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' Exit /* Other test cases */ Call trio_test '0 0 0 4 4 0 0 2 2 2 2 0' Call trio_test '0 0 0 5 5 0 0 0 0 5 5 0' Call trio_test '0 0 0 5 5 0 0 0 0 5 7 0' Call trio_test '0 0 1 0 0 1 1 0 2 0 1 1' Call trio_test '0 0 1 1 0 2 2 1 3 0 3 2' Call trio_test '0 0 1 1 0 2 2 1 3 -2 3 4' Call trio_test '0 0 2 0 2 2 3 3 5 3 5 5' Call trio_test '0 0 2 0 2 3 0 0 2 0 2 3' Call trio_test '0 0 4 0 0 4 0 2 2 0 2 2' Call trio_test '0 0 4 0 0 4 1 1 2 1 1 2' Call trio_test '0 0 5 0 0 2 5 0 8 0 4 8' Call trio_test '0 0 5 0 0 5 0 0 5 0 0 6' Call trio_test '0 0 5 0 0 5 -10 0 -5 0 -1 6' Call trio_test '0 0 5 0 0 5 -5 0 -1 6 -3 0' Call trio_test '0 0 5 0 3 5 0 4 3 -1 5 4' Call trio_test '0 0 6 0 4 6 1 1 4 2 7 1' Call trio_test '0 1 0 4 2 2 3 1 3 4 5 2' Call trio_test '1 0 3 0 2 2 1 3 3 3 2 2' Call trio_test '1 0 3 0 2 2 1 3 3 3 2 5' Call trio_test '1 1 4 2 7 1 0 0 8 0 4 8' Call trio_test '2 0 2 6 1 8 0 1 0 5 8 3' Call trio_test '0 0 4 0 0 4 1 1 2 1 1 2' Say case 'cases tested' Say cc Exit
trio_test: Parse Arg tlist cc+=1 tlist=space(tlist) tl1=tlist ; Call trio_t tl1 tl2=reversex(tlist) ; Call trio_t tl2 tl3= tl=tlist Do While tl<>
Parse Var tl x y tl tl3=tl3 y x End Call trio_t tl3
tl4=reversex(tl3) ; Call trio_t tl4 tl5=subword(tl4,7) subword(tl4,1,6) ; Call trio_t tl5 tl6=subword(tl5,7) subword(tl5,1,6) ; Call trio_t tl6 Return
trio_t: Parse Arg tlist tlist=space(tlist) Say tlist case+=1 Parse Arg ax ay bx by cx cy dx dy ex ey fx fy /*---------------------------------------------------------------------
- First build the objects needed
- --------------------------------------------------------------------*/
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) abc=.triangle~new(a,b,c) def=.triangle~new(d,e,f) Call o 'Triangle: ABC:' abc ,1 Call o 'Edges of ABC:'; Do i=1 To 3; Call o ' 'abc~edge(i); End Call o 'Triangle: DEF:' def ,1 Call o 'Edges of DEF:'; Do i=1 To 3; Call o ' 'def~edge(i); End pixl=' ' Do i=1 To 3
pixl=pixl abc~draw(i,'O') pixl=pixl def~draw(i,'*') End
res=0 fc=0 touch=0 bordl= Do i=1 To 3
p1=abc~point(i) p2=def~point(i) Do j=1 To 3 e1=abc~edge(j) e2=def~edge(j) If e1~contains(p2) Then Do Call o e1 'contains' p2 ps=p2~string If wordpos(ps,bordl)=0 Then Do bordl=bordl ps touch+=1 End End Else Call o e1 'does not contain' p2 i j If e2~contains(p1) Then Do Call o e2 'contains' p1 ps=p1~string If wordpos(ps,bordl)=0 Then Do bordl=bordl ps touch+=1 End End Else Call o e2 'does not contain' p1 End End
wb=words(bordl) /* how many of them? */ If wb>0 Then
Call o 'Corner(s) that touch the other triangle:' bordl,1
/*---------------------------------------------------------------------
- How many of them are corners of both triangles
- --------------------------------------------------------------------*/
m=0 cmatch= do i=1 To 3
If wordpos(abc~point(i),bordl)>0 &, wordpos(abc~point(i),def)>0 Then Do cmatch=cmatch abc~point(i) m+=1 End End
/*---------------------------------------------------------------------
- With two or three touching corners we show the result and return
- --------------------------------------------------------------------*/
Select
When wb=3 Then Do /* all three touch */ Call draw(pixl) Select When m=3 Then Call o 'Triangles are identical',1 When m=2 Then Call o 'Triangles have an edge in common:' cmatch,1 Otherwise Call o 'Triangles overlap and touch on' bordl,1 End Call o ,1 -- Pull . Return End When wb=2 Then Do /* two of them match */ Call draw(pixl) If m=2 Then Call o 'Triangles have an edge in common:' cmatch,1 Else Call o 'Triangles overlap and touch on' bordl,1 Call o -- Pull . Return End When wb=1 Then Do /* one of them matches */ Call o 'Triangles touch on' bordl,1 /* other parts may overlap */ Call o ' we analyze further',1 End Otherwise /* we know nothing yet */ Nop End
/*---------------------------------------------------------------------
- Now we look for corners of abc that are within the triangle def
- --------------------------------------------------------------------*/
in_def=0 Do i=1 To 3
p=abc~point(i) Call o 'p ='p Call o 'def='def If def~contains(p) &, wordpos(p,bordl)=0 Then Do Call o def 'contains' p in_def+=1 End End
If in_def=3 Then Do
Call o abc 'is fully contained in' def,1 Call o ,1 Call draw(pixl) fc=1 End
res=(in_def>0) /*---------------------------------------------------------------------
- Now we look for corners of def that are within the triangle abc
- --------------------------------------------------------------------*/
If res=0 Then Do
in_abc=0 If res=0 Then Do Do i=1 To 3 p=def~point(i) Call o 'p ='p Call o 'def='def If abc~contains(p) &, wordpos(p,bordl)=0 Then Do Call o abc 'contains' p in_abc+=1 End End End If in_abc=3 Then Do Call o def 'is fully contained in' abc,1 Call o ,1 Call draw(pixl) fc=1 End res=(in_abc>0)
End
/*---------------------------------------------------------------------
- Now we check if some edge of abc crosses any edge of def
- --------------------------------------------------------------------*/
If res=0 Then Do
Do i=1 To 3 Do j=1 To 3 e1=abc~edge(i); Call o 'e1='e1 e2=def~edge(j); Call o 'e2='e2 Call o 'crossing???' res=e1~crosses(e2)
If res Then Do
End If res Then Call o 'edges cross' Else Call o 'edges dont cross' End End End
If fc=0 Then Do /* no fully contained */
Call draw(pixl) If res=0 Then /* no overlap */ If wb=1 Then /* but one touching corner */ call o abc 'and' def 'dont overlap but touch on' bordl,1 Else call o abc 'and' def 'dont overlap',1 Else /* overlap */ If wb>0 Then /* one touching corner */ call o abc 'and' def 'overlap and touch on' bordl,1 Else call o abc 'and' def 'overlap',1 Call o ,1
-- Pull .
End
Return
/*---------------------------------------------------------------------
- And here are all the classes and methods needed:
- point init, x, y, string
- triangle init, point, edge, contains, string
- edge init, p1, p2, kdx, contains, crosses, string
- --------------------------------------------------------------------*/
- class point public
- attribute x
- attribute y
- method init
expose x y use arg x,y
- method string
expose x y return "("||x","y")"
- class triangle public
- method init
expose point edge use arg p1,p2,p3 point=.array~new point[1]=p1 point[2]=p2 point[3]=p3 edge=.array~new Do i=1 To 3 ia=i+1; If ia=4 Then ia=1 edge[i]=.edge~new(point[i],point[ia]) End
- method point
expose point use arg n Return point[n]
- method edge
expose edge use arg n Return edge[n]
- method contains
expose point edge use arg pp Call o self Call o 'pp='pp xmin=1.e9 ymin=1.e9 xmax=-1.e9 ymax=-1.e9 Do i=1 To 3 e=edge[i] Parse Value e~kdx With ka.i da.i xa.i Call o show_g(ka.i,da.i,xa.i) p1=e~p1 p2=e~p2 xmin=min(xmin,p1~x,p2~x) xmax=max(xmax,p1~x,p2~x) ymin=min(ymin,p1~y,p2~y) ymax=max(ymax,p1~y,p2~y) End If pp~x<xmin|pp~x>xmax|pp~y<ymin|pp~y>ymax Then res=0 Else Do e=edge[1] e2=edge[2] p1=e2~p1 p2=e2~p2 Call o 'e:' e Select When ka.1='*' Then Do y2=ka.2*pp~x+da.2 y3=ka.3*pp~x+da.3 res=between(y2,pp~y,y3) End When ka.2='*' Then Do y2=ka.1*pp~x+da.1 res=between(p1~y,y2,p2~y) End Otherwise Do dap=pp~y-ka.1*pp~x If ka.3='*' Then x3=xa.3 Else x3=(da.3-dap)/(ka.1-ka.3) x2=(da.2-dap)/(ka.1-ka.2) res=between(x2,pp~x,x3) End End End Return res
- method string
expose point ol= Do p over point ol=ol p~string End return ol
- method draw
expose point Use Arg i,c p=self~point(i) Return p~x p~y c
- class edge public
- method init
expose edge p1 p2 use arg p1,p2 edge=.array~new edge[1]=p1 edge[2]=p2
- method p1
expose edge p1 p2 return p1
- method p2
expose edge p1 p2 return p2
- method kdx
expose edge p1 p2 x1=p1~x y1=p1~y x2=p2~x y2=p2~y If x1=x2 Then Do Parse Value '*' '-' x1 With ka da xa Call o show_g(ka,da,xa) End Else Do ka=(y2-y1)/(x2-x1) da=y2-ka*x2 xa='*' End Return ka da xa
- method contains
Use Arg p p1=self~p1 p2=self~p2 parse Value self~kdx With k d x If k='*' Then Do res=(p~x=p1~x)&between(p1~y,p~y,p2~y,'I') End Else Do ey=k*p~x+d res=(ey=p~y)&between(p1~x,p~x,p2~x,'I') End If res Then Call o self 'contains' p Else Call o self 'does not contain' p Return res
- method crosses
expose p1 p2 Use Arg e q1=e~p1 q2=e~p2 Call o 'Test if' e 'crosses' self Call o self~kdx Call o e~kdx Parse Value self~kdx With ka da xa; Call o ka da xa Call o show_g(ka,da,xa) Parse Value e~kdx With kb db xb; Call o kb db xb Call o show_g(kb,db,xb) Call o 'ka='ka Call o 'kb='kb Select When ka='*' Then Do If kb='*' Then Do res=(xa=xb) End Else Do Call o 'kb='kb 'xa='||xa 'db='db yy=kb*xa+db res=between(q1~y,yy,q2~y) End End When kb='*' Then Do yy=ka*xb+da res=between(p1~y,yy,p2~y) End When ka=kb Then Do If da=db Then Do If min(p1~x,p2~x)>max(q1~x,q2~x) |, min(q1~x,q2~x)>max(p1~x,p2~x) Then res=0 Else Do res=1 End End Else res=0 End Otherwise Do x=(db-da)/(ka-kb) y=ka*x+da Call o 'cross:' x y res=between(p1~x,x,p2~x) End End Return res
- method string
expose edge p1 p2 ol=p1~string'-'p2~string return ol
- routine between /* check if a number is between two others */
Use Arg a,x,b,inc Call o 'between:' a x b Parse Var a anom '/' adenom Parse Var x xnom '/' xdenom Parse Var b bnom '/' bdenom If adenom= Then adenom=1 If xdenom= Then xdenom=1 If bdenom= Then bdenom=1 aa=anom*xdenom*bdenom xx=xnom*adenom*bdenom bb=bnom*xdenom*adenom If inc='I' Then res=sign(xx-aa)<>sign(xx-bb) Else res=sign(xx-aa)<>sign(xx-bb) & (xx-aa)*(xx-bb)<>0 Call o a x b 'res='res Return res
- routine show_g /* show a straight line's forula */
/*---------------------------------------------------------------------
- given slope, y-distance, and (special) x-value
- compute y=k*x+d or, if a vertical line, k='*'; x=c
- --------------------------------------------------------------------*/
Use Arg k,d,x Select When k='*' Then res='x='||x /* vertical line */ When k=0 Then res='y='d /* horizontal line */ Otherwise Do /* ordinary line */ Select When k=1 Then res='y=x'dd(d) When k=-1 Then res='y=-x'dd(d) Otherwise res='y='k'*x'dd(d) End End End Return res
- routine dd /* prepare a displacement for presenting it in show_g */
/*---------------------------------------------------------------------
- prepare y-distance for display
- --------------------------------------------------------------------*/
Use Arg dd Select When dd=0 Then dd= /* omit dd if it's zero */ When dd<0 Then dd=dd /* use dd as is (-value) */ Otherwise dd='+'dd /* prepend '+' to positive dd */ End Return dd
- routine o /* debug output */
Use Arg txt,say If say=1 Then Say txt oid='trioo.txt' Return lineout(oid,txt)
- routine draw
Use Arg pixl Return /* remove to see the triangle corners */ Say 'pixl='pixl pix.=' ' Do While pixl<> Parse Var pixl x y c pixl x=2*x+16; y=2*y+4 If pix.x.y=' ' Then pix.x.y=c Else pix.x.y='+' End Do j= 20 To 0 By -1 ol= Do i=0 To 40 ol=ol||pix.i.j End Say ol End Return
- routine reversex
Use Arg list n=words(list) res=word(list,n) Do i=n-1 to 1 By -1 res=res word(list,i) End Return res </lang>
- Output:
Triangle: ABC: (0,0) (5,0) (0,5) Triangle: DEF: (0,0) (5,0) (0,6) Corner(s) that touch the other triangle: (0,0) (5,0) (0,5) Triangles have an edge in common: (0,0) (5,0) Triangle: ABC: (0,0) (0,5) (5,0) Triangle: DEF: (0,0) (0,5) (5,0) Corner(s) that touch the other triangle: (0,0) (0,5) (5,0) Triangles are identical 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 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 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 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 Triangle: ABC: (0,0) (1,0) (0,1) Triangle: DEF: (1,0) (2,0) (1,1) Corner(s) that touch the other triangle: (1,0) Triangles touch on (1,0) we analyze further (0,0) (1,0) (0,1) and (1,0) (2,0) (1,1) don't overlap but touch on (1,0)
Python
Using numpy:
<lang python>from __future__ import print_function import numpy as np
def CheckTriWinding(tri, allowReversed): trisq = np.ones((3,3)) trisq[:,0:2] = np.array(tri) detTri = np.linalg.det(trisq) if detTri < 0.0: if allowReversed: a = trisq[2,:].copy() trisq[2,:] = trisq[1,:] trisq[1,:] = a else: raise ValueError("triangle has wrong winding direction") return trisq
def TriTri2D(t1, t2, eps = 0.0, allowReversed = False, onBoundary = True): #Trangles must be expressed anti-clockwise t1s = CheckTriWinding(t1, allowReversed) t2s = CheckTriWinding(t2, allowReversed)
if onBoundary: #Points on the boundary are considered as colliding chkEdge = lambda x: np.linalg.det(x) < eps else: #Points on the boundary are not considered as colliding chkEdge = lambda x: np.linalg.det(x) <= eps
#For edge E of trangle 1, for i in range(3): edge = np.roll(t1s, i, axis=0)[:2,:]
#Check all points of trangle 2 lay on the external side of the edge E. If #they do, the triangles do not collide. if (chkEdge(np.vstack((edge, t2s[0]))) and chkEdge(np.vstack((edge, t2s[1]))) and chkEdge(np.vstack((edge, t2s[2])))): return False
#For edge E of trangle 2, for i in range(3): edge = np.roll(t2s, i, axis=0)[:2,:]
#Check all points of trangle 1 lay on the external side of the edge E. If #they do, the triangles do not collide. if (chkEdge(np.vstack((edge, t1s[0]))) and chkEdge(np.vstack((edge, t1s[1]))) and chkEdge(np.vstack((edge, t1s[2])))): return False
#The triangles collide return True
if __name__=="__main__": t1 = [[0,0],[5,0],[0,5]] t2 = [[0,0],[5,0],[0,6]] print (TriTri2D(t1, t2), True)
t1 = [[0,0],[0,5],[5,0]] t2 = [[0,0],[0,6],[5,0]] print (TriTri2D(t1, t2, allowReversed = True), True)
t1 = [[0,0],[5,0],[0,5]] t2 = [[-10,0],[-5,0],[-1,6]] print (TriTri2D(t1, t2), False)
t1 = [[0,0],[5,0],[2.5,5]] t2 = [[0,4],[2.5,-1],[5,4]] print (TriTri2D(t1, t2), True)
t1 = [[0,0],[1,1],[0,2]] t2 = [[2,1],[3,0],[3,2]] print (TriTri2D(t1, t2), False)
t1 = [[0,0],[1,1],[0,2]] t2 = [[2,1],[3,-2],[3,4]] print (TriTri2D(t1, t2), False)
#Barely touching t1 = [[0,0],[1,0],[0,1]] t2 = [[1,0],[2,0],[1,1]] print (TriTri2D(t1, t2, onBoundary = True), True)
#Barely touching t1 = [[0,0],[1,0],[0,1]] t2 = [[1,0],[2,0],[1,1]] print (TriTri2D(t1, t2, onBoundary = False), False)</lang>
- Output:
True True True True False False True True False False False False True True /False False
Using shapely:
<lang python>from __future__ import print_function from shapely.geometry import Polygon
def PolyOverlaps(poly1, poly2): poly1s = Polygon(poly1) poly2s = Polygon(poly2) return poly1s.intersects(poly2s)
if __name__=="__main__": t1 = [[0,0],[5,0],[0,5]] t2 = [[0,0],[5,0],[0,6]] print (PolyOverlaps(t1, t2), True)
t1 = [[0,0],[0,5],[5,0]] t2 = [[0,0],[0,6],[5,0]] print (PolyOverlaps(t1, t2), True)
t1 = [[0,0],[5,0],[0,5]] t2 = [[-10,0],[-5,0],[-1,6]] print (PolyOverlaps(t1, t2), False)
t1 = [[0,0],[5,0],[2.5,5]] t2 = [[0,4],[2.5,-1],[5,4]] print (PolyOverlaps(t1, t2), True)
t1 = [[0,0],[1,1],[0,2]] t2 = [[2,1],[3,0],[3,2]] print (PolyOverlaps(t1, t2), False)
t1 = [[0,0],[1,1],[0,2]] t2 = [[2,1],[3,-2],[3,4]] print (PolyOverlaps(t1, t2), False)
#Barely touching t1 = [[0,0],[1,0],[0,1]] t2 = [[1,0],[2,0],[1,1]] print (PolyOverlaps(t1, t2), "?")</lang>
- Output:
True True True True False False True True False False False False True ?
REXX
Note: The triangles must be real triangles (no edge of length 0) <lang rexx>Signal On Halt Signal On Novalue Signal On Syntax
fid='trio.in' oid='trio.txt'; 'erase' oid
Call trio_test '0 0 5 0 0 5 0 0 5 0 0 6'
Call trio_test '0 0 0 5 5 0 0 0 0 5 5 0'
Call trio_test '0 0 5 0 0 5 -10 0 -5 0 -1 6'
Call trio_test '0 0 5 0 2.5 5 0 4 2.5 -1 5 4'
Call trio_test '0 0 1 1 0 2 2 1 3 0 3 2'
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 '1 0 3 0 2 2 1 3 3 3 2 5' Call trio_test '1 0 3 0 2 2 1 3 3 3 2 2' Call trio_test '0 0 2 0 2 2 3 3 5 3 5 5' Call trio_test '2 0 2 6 1 8 0 1 0 5 8 3' Call trio_test '0 0 4 0 0 4 0 2 2 0 2 2' Call trio_test '0 0 4 0 0 4 1 1 2 1 1 2' Exit
trio_test: parse Arg tlist tlist=space(tlist) Parse Arg ax ay bx by cx cy dx dy ex ey fx fy
Say 'ABC:' show_p(ax ay) show_p(bx by) show_p(cx cy) Say 'DEF:' show_p(dx dy) show_p(ex ey) show_p(fx fy)
bordl=bord(tlist) /* corners that are on the other triangle's edges */ If bordl<> Then
Say 'Corners on the other triangles edges:' bordl
wb=words(bordl) /* how many of them? */ Select
When wb=3 Then Do /* all three match */ If ident(ax ay,bx by,cx cy,dx dy,ex ey,fx fy) Then Say 'Triangles are identical' Else Say 'Triangles overlap' Say Return End When wb=2 Then Do /* two of them match */ Say 'Triangles overlap' Say ' they have a common edge 'bordl Say Return End When wb=1 Then Do /* one of them match */ Say 'Triangles touch on' bordl /* other parts may overlap */ Say ' we analyze further' End Otherwise /* we know nothing yet */ Nop End
trio_result=trio(tlist) /* any other overlap? */
Select
When trio_result=0 Then Do /* none whatsoever */ If wb=1 Then Say 'Triangles touch (border case) at' show_p(bordl) Else Say 'Triangles dont overlap' End When trio_result>0 Then /* plain overlapping case */ Say 'Triangles overlap' End
Say Return
trio: /*---------------------------------------------------------------------
- Determine if two triangles overlap
- --------------------------------------------------------------------*/
parse Arg tlist Parse Arg pax pay pbx pby pcx pcy pdx pdy pex pey pfx pfy
abc=subword(tlist,1,6) def=subword(tlist,7,6)
Do i=1 To 3
s.i=subword(abc abc,i*2-1,4) t.i=subword(def def,i*2-1,4) End
abc_= def_=
Do i=1 To 3
abc.i=subword(abc,i*2-1,2) /* corners of ABC */ def.i=subword(def,i*2-1,2) /* corners of DEF */ Parse Var abc.i x y; abc_=abc_ '('||x','y')' Parse Var def.i x y; def_=def_ '('||x','y')' End
Call o 'abc_='abc_ Call o 'def_='def_
over=0
Do i=1 To 3 Until over Do j=1 To 3 Until over If ssx(s.i t.j) Then Do /* intersection of two edges */ over=1 Leave End End End
If over=0 Then Do /* no edge intersection found */
Do ii=1 To 3 Until over /* look for first possibility */ Call o ' ' 'abc.'ii'='abc.ii 'def='def Call o 'ii='ii 'def.'ii'='def.ii 'abc='abc If in_tri(abc.ii,def) Then Do /* a corner of ABC is in DEF */ Say abc.ii 'is within' def over=1 End Else If in_tri(def.ii,abc) Then Do /* a corner of DEF is in ABC */ Say def.ii 'is within' abc over=1 End End End
If over=0 Then rw='dont ' Else rw=
Call o 'Triangles' show_p(pax pay) show_p(pbx pby) show_p(pcx pcy),
'and' show_p(pdx pdy) show_p(pex pey) show_p(pfx pfy), rw'overlap'
Call o Return over
ssx: Procedure Expose oid bordl /*---------------------------------------------------------------------
- Intersection of 2 line segments A-B and C-D
- --------------------------------------------------------------------*/
Parse Arg xa ya xb yb xc yc xd yd
d=ggx(xa ya xb yb xc yc xd yd)
Call o 'ssx:' arg(1) d res=0 Select
When d='-' Then res=0 When d='I' Then Do If xa<>xb Then Do xab_min=min(xa,xb) xcd_min=min(xc,xd) xab_max=max(xa,xb) xcd_max=max(xc,xd) If xab_min>xcd_max |, xcd_min>xab_max Then res=0 Else Do res=1 Select When xa=xc & isb(xc,xb,xd)=0 Then Do; x=xa; y=ya; End When xb=xc & isb(xc,xa,xd)=0 Then Do; x=xb; y=yb; End When xa=xd & isb(xc,xb,xd)=0 Then Do; x=xa; y=ya; End When xb=xd & isb(xc,xa,xd)=0 Then Do; x=xb; y=yb; End Otherwise Do x='*' y=ya End End Call o 'ssx:' x y End End Else Do yab_min=min(ya,yb) ycd_min=min(yc,yd) yab_max=max(ya,yb) ycd_max=max(yc,yd) If yab_min>ycd_max |, ycd_min>yab_max Then res=0 Else Do res=1 x=xa y='*' Parse Var bordl x_bord '/' y_bord If x=x_bord Then Do Call o xa'/* IGNORED' res=0 End End End End Otherwise Do Parse Var d x y If is_between(xa,x,xb) &, is_between(xc,x,xd) &, is_between(ya,y,yb) &, is_between(yc,y,yd) Then Do If x'/'y<>bordl Then res=1 End End End If res=1 Then Do Say 'Intersection of line segments: ('||x'/'y')' Parse Var bordl x_bord '/' y_bord If x=x_bord Then Do res=0 Call o x'/'y 'IGNORED' End End Else Call o 'ssx: -'
Return res
ggx: Procedure Expose oid bordl /*---------------------------------------------------------------------
- Intersection of 2 (straight) lines
- --------------------------------------------------------------------*/
Parse Arg xa ya xb yb xc yc xd yd res= If xa=xb Then Do
k1='*' x1=xa If ya=yb Then Do res='Points A and B are identical' rs='*' End End
Else Do
k1=(yb-ya)/(xb-xa) d1=ya-k1*xa End
If xc=xd Then Do
k2='*' x2=xc If yc=yd Then Do res='Points C and D are identical' rs='*' End End
Else Do
k2=(yd-yc)/(xd-xc) d2=yc-k2*xc End
If res= Then Do
If k1='*' Then Do If k2='*' Then Do If x1=x2 Then Do res='Lines AB and CD are identical' rs='I' End Else Do res='Lines AB and CD are parallel' rs='-' End End Else Do x=x1 y=k2*x+d2 End End Else Do If k2='*' Then Do x=x2 y=k1*x+d1 End Else Do If k1=k2 Then Do If d1=d2 Then Do res='Lines AB and CD are identical' rs='I' End Else Do res='Lines AB and CD are parallel' rs='-' End End Else Do x=(d2-d1)/(k1-k2) y=k1*x+d1 End End End End If res= Then Do res='Intersection is ('||x'/'y')' rs=x y Call o 'line intersection' x y End Call o 'A=('xa'/'ya') B=('||xb'/'yb') C=('||xc'/'yc') D=('||xd'/'yd')' '-->' res Return rs
isb: Procedure
Parse Arg a,b,c Return sign(b-a)<>sign(b-c)
is_between: Procedure Expose oid
Parse Arg a,b,c Return diff_sign(b-a,b-c)
diff_sign: Procedure
Parse Arg diff1,diff2 Return (sign(diff1)<>sign(diff2))|(sign(diff1)=0)
o: /*y 'sigl='sigl */ Return lineout(oid,arg(1))
in_tri: Procedure Expose oid bordl /*---------------------------------------------------------------------
- Determine if the point (px/py) is within the given triangle
- --------------------------------------------------------------------*/
Parse Arg px py,ax ay bx by cx cy abc=ax ay bx by cx cy res=0 maxx=max(ax,bx,cx) minx=min(ax,bx,cx) maxy=max(ay,by,cy) miny=min(ay,by,cy)
If px>maxx|px<minx|py>maxy|py<miny Then
Return 0
Parse Value mk_g(ax ay,bx by) With k.1 d.1 x.1 Parse Value mk_g(bx by,cx cy) With k.2 d.2 x.2 Parse Value mk_g(cx cy,ax ay) With k.3 d.3 x.3 /* say 'g1:' show_g(k.1,d.1,x.1) say 'g2:' show_g(k.2,d.2,x.2) say 'g3:' show_g(k.3,d.3,x.3) Say px py '-' ax ay bx by cx cy
- /
Do i=1 To 3
Select When k.i='*' Then Call o 'g.'i':' 'x='||x.i When k.i=0 Then Call o 'g.'i':' 'y='d.i Otherwise Call o 'g.'i':' 'y=' k.i'*x'dd(d.i) End End
If k.1='*' Then Do
y2=k.2*px+d.2 y3=k.3*px+d.3 If is_between(y2,py,y3) Then res=1 End
Else Do
kp1=k.1 dp1=py-kp1*px If k.2='*' Then x12=x.2 Else x12=(d.2-dp1)/(kp1-k.2) If k.3='*' Then x13=x.3 Else x13=(d.3-dp1)/(kp1-k.3) If is_between(x12,px,x13) Then res=1 End
If res=1 Then rr=' '
Else rr=' not '
If pos(px'/'py,bordl)>0 Then Do
ignored=' but is IGNORED' res=0 End
Else
ignored=
Say 'P ('px','py') is'rr'in' abc ignored Return res
bord: /*---------------------------------------------------------------------
- Look for corners of triangles that are situated
- on the edges of the other triangle
- --------------------------------------------------------------------*/
parse Arg tlist Parse Arg pax pay pbx pby pcx pcy pdx pdy pex pey pfx pfy bordl= abc=subword(tlist,1,6) def=subword(tlist,7,6)
Do i=1 To 3
s.i=subword(abc abc,i*2-1,4) t.i=subword(def def,i*2-1,4) End
abc_= def_= Do i=1 To 3
abc.i=subword(abc,i*2-1,2) def.i=subword(def,i*2-1,2) Parse Var abc.i x y; abc_=abc_ '('||x','y')' Parse Var def.i x y; def_=def_ '('||x','y')' End
Do i=1 To 3
i1=i+1 If i1=4 Then i1=1 Parse Value mk_g(abc.i,abc.i1) With k.1.i d.1.i x.1.i Parse Value mk_g(def.i,def.i1) With k.2.i d.2.i x.2.i End
Do i=1 To 3
Call o show_g(k.1.i,d.1.i,x.1.i) End
Do i=1 To 3
Call o show_g(k.2.i,d.2.i,x.2.i) End
pl= Do i=1 To 3
p=def.i Do j=1 To 3 j1=j+1 If j1=4 Then j1=1 g='1.'j If in_segment(p,abc.j,abc.j1) Then Do pp=Translate(p,'/',' ') If wordpos(pp,bordl)=0 Then bordl=bordl pp End Call o show_p(p) show_g(k.g,d.g,x.g) '->' bordl End End
Call o 'Points on abc:' pl
pl= Do i=1 To 3
p=abc.i Do j=1 To 3 j1=j+1 If j1=4 Then j1=1 g='2.'j If in_segment(p,def.j,def.j1)Then Do pp=Translate(p,'/',' ') If wordpos(pp,bordl)=0 Then bordl=bordl pp End Call o show_p(p) show_g(k.g,d.g,x.g) '->' bordl End End
Call o 'Points on def:' pl
Return bordl
in_segment: Procedure Expose g. sigl /*---------------------------------------------------------------------
- Determine if point x/y is on the line segment ax/ay bx/by
- --------------------------------------------------------------------*/
Parse Arg x y,ax ay,bx by Call show_p(x y) show_p(ax ay) show_p(bx by) Parse Value mk_g(ax ay,bx by) With gk gd gx Select
When gx<> Then res=(x=gx & is_between(ay,y,by)) When gk='*' Then res=(y=gd & is_between(ax,x,bx)) Otherwise Do yy=gk*x+gd res=(y=yy & is_between(ax,x,bx)) End End
Return res
mk_g: Procedure Expose g. /*---------------------------------------------------------------------
- given two points (a and b)
- compute y=k*x+d or, if a vertical line, k='*'; x=c
- --------------------------------------------------------------------*/
Parse Arg a,b /* 2 points */ Parse Var a ax ay Parse Var b bx by If ax=bx Then Do /* vertical line */
gk='*' /* special slope */ gx=ax /* x=ax is the equation */ gd='*' /* not required */ End
Else Do
gk=(by-ay)/(bx-ax) /* compute slope */ gd=ay-gk*ax /* compute y-distance */ gx= /* not required */ End
Return gk gd gx
is_between: Procedure
Parse Arg a,b,c Return diff_sign(b-a,b-c)
diff_sign: Procedure
Parse Arg diff1,diff2 Return (sign(diff1)<>sign(diff2))|(sign(diff1)=0)
show_p: Procedure
Call trace 'O' Parse Arg x y If pos('/',x)>0 Then Parse Var x x '/' y Return space('('||x'/'y')',0)
isb: Procedure Expose oid
Parse Arg a,b,c Return sign(b-a)<>sign(b-c)
o: Call o arg(1)
Return
show_g: Procedure /*---------------------------------------------------------------------
- given slope, y-distance, and (special) x-value
- compute y=k*x+d or, if a vertical line, k='*'; x=c
- --------------------------------------------------------------------*/
Parse Arg k,d,x Select
When k='*' Then res='x='||x /* vertical line */ When k=0 Then res='y='d /* horizontal line */ Otherwise Do /* ordinary line */ Select When k=1 Then res='y=x'dd(d) When k=-1 Then res='y=-x'dd(d) Otherwise res='y='k'*x'dd(d) End End End
Return res
dd: Procedure /*---------------------------------------------------------------------
- prepare y-distance for display
- --------------------------------------------------------------------*/
Parse Arg dd Select When dd=0 Then dd= /* omit dd if it's zero */ When dd<0 Then dd=dd /* use dd as is (-value) */ Otherwise dd='+'dd /* prepend '+' to positive dd */ End Return dd
ident: Procedure /*---------------------------------------------------------------------
- Determine if the corners ABC match those of DEF (in any order)
- --------------------------------------------------------------------*/
cnt.=0 Do i=1 To 6 Parse Value Arg(i) With x y cnt.x.y=cnt.x.y+1 End Do i=1 To 3 Parse Value Arg(i) With x y If cnt.x.y<>2 Then Return 0 End Return 1
Novalue:
Say 'Novalue raised in line' sigl Say sourceline(sigl) Say 'Variable' condition('D') Signal lookaround
Syntax:
Say 'Syntax raised in line' sigl Say sourceline(sigl) Say 'rc='rc '('errortext(rc)')'
halt: lookaround:
If fore() Then Do Say 'You can look around now.' Trace ?R Nop End Exit 12</lang>
- Output:
ABC: (0/0) (5/0) (0/5) DEF: (0/0) (5/0) (0/6) Corners on the other triangle's edges: 0/0 5/0 0/5 Triangles overlap ABC: (0/0) (0/5) (5/0) DEF: (0/0) (0/5) (5/0) Corners on the other triangle's edges: 0/0 0/5 5/0 Triangles are identical ABC: (0/0) (5/0) (0/5) DEF: (-10/0) (-5/0) (-1/6) Triangles don't overlap ABC: (0/0) (5/0) (2.5/5) DEF: (0/4) (2.5/-1) (5/4) Intersection of line segments: (2/0) Triangles overlap ABC: (0/0) (1/1) (0/2) DEF: (2/1) (3/0) (3/2) Triangles don't overlap ABC: (0/0) (1/1) (0/2) DEF: (2/1) (3/-2) (3/4) Triangles don't overlap ABC: (0/0) (1/0) (0/1) DEF: (1/0) (2/0) (1/1) Corners on the other triangle's edges: 1/0 Triangles touch on 1/0 we analyze further Intersection of line segments: (1/0) P (1,0) is in 0 0 1 0 0 1 but is IGNORED P (1,0) is in 1 0 2 0 1 1 but is IGNORED P (1,1) is not in 0 0 1 0 0 1 Triangles touch (border case) at (1/0) ABC: (1/0) (3/0) (2/2) DEF: (1/3) (3/3) (2/5) Triangles don't overlap ABC: (1/0) (3/0) (2/2) DEF: (1/3) (3/3) (2/2) Corners on the other triangle's edges: 2/2 Triangles touch on 2/2 we analyze further P (2,2) is in 1 3 3 3 2 2 but is IGNORED P (2,2) is in 1 0 3 0 2 2 but is IGNORED Triangles touch (border case) at (2/2) ABC: (0/0) (2/0) (2/2) DEF: (3/3) (5/3) (5/5) Triangles don't overlap ABC: (2/0) (2/6) (1/8) DEF: (0/1) (0/5) (8/3) Intersection of line segments: (2/4.50) Triangles overlap ABC: (0/0) (4/0) (0/4) DEF: (0/2) (2/0) (2/2) Corners on the other triangle's edges: 0/2 2/0 2/2 Triangles overlap ABC: (0/0) (4/0) (0/4) DEF: (1/1) (2/1) (1/2) P (1,1) is in 0 0 4 0 0 4 1 1 is within 0 0 4 0 0 4 Triangles overlap
zkl
<lang zkl>// A triangle is three pairs of points: ( (x,y), (x,y), (x,y) )
fcn det2D(triangle){
p1,p2,p3 := triangle; p1[0]*(p2[1] - p3[1]) + p2[0]*(p3[1] - p1[1]) + p3[0]*(p1[1] - p2[1]);
} fcn checkTriWinding(triangle,allowReversed){ //-->triangle, maybe new
detTri:=det2D(triangle); if(detTri<0.0){ if(allowReversed){ p1,p2,p3 := triangle; return(p1,p3,p2); } // reverse else throw(Exception.AssertionError(
"triangle has wrong winding direction"));
} triangle // no change
} fcn triTri2D(triangle1,triangle2, eps=0.0, allowReversed=False, onBoundary=True){
// Trangles must be expressed anti-clockwise triangle1=checkTriWinding(triangle1, allowReversed); triangle2=checkTriWinding(triangle2, allowReversed); chkEdge:= if(onBoundary) // Points on the boundary are considered as colliding
fcn(triangle,eps){ det2D(triangle)<eps }
else // Points on the boundary are not considered as colliding
fcn(triangle,eps){ det2D(triangle)<=eps };; // first ; terminates if
t1,t2 := triangle1,triangle2; // change names to protect the typist do(2){ // check triangle1 and then triangle2 foreach i in (3){ //For edge E of trangle 1,
j:=(i+1)%3; // 1,2,0 // Check all points of trangle 2 lay on the external side // of the edge E. If they do, the triangles do not collide. if(chkEdge(T(t1[i],t1[j],t2[0]), eps) and chkEdge(T(t1[i],t1[j],t2[1]), eps) and chkEdge(T(t1[i],t1[j],t2[2]), eps)) return(False); // no collision
} t2,t1 = triangle1,triangle2; // flip and re-test } True // The triangles collide
}</lang> <lang zkl>fcn toTri(ax,ay,bx,by,cx,cy){ //-->( (ax,ay),(bx,by),(cx,cy) )
vm.arglist.apply("toFloat").pump(List,Void.Read)
} triangles:=T( // pairs of triangles
T(toTri(0,0, 5,0, 0, 5), toTri( 0,0, 5, 0, 0,6)), T(toTri(0,0, 0,5, 5, 0), toTri( 0,0, 0, 5 , 5,0)), T(toTri(0,0, 5,0, 0, 5), toTri(-10,0, -5, 0, -1,6)), T(toTri(0,0, 5,0, 2.5,5), toTri( 0,4, 2.5,-1, 5,4)), T(toTri(0,0, 1,1, 0, 2), toTri( 2,1, 3, 0, 3,2)), T(toTri(0,0, 1,1, 0, 2), toTri( 2,1, 3, -2, 3,4))
);
// Expect: overlap, overlap (reversed), no overlap, overlap, no overlap, no overlap
foreach t1,t2 in (triangles){
reg r, reversed=False; try{ r=triTri2D(t1,t2) } catch(AssertionError){ r=triTri2D(t1,t2,0.0,True); reversed=True; } print(t1,"\n",t2," "); println(r and "overlap" or "no overlap", reversed and " (reversed)" or ""); println();
}
c1,c2 := toTri(0,0, 1,0, 0,1), toTri(1,0, 2,0, 1,1); println("Corner case (barely touching): ",triTri2D(c1,c2,0.0,False,True)); // True println("Corner case (barely touching): ",triTri2D(c1,c2,0.0,False,False)); // False</lang>
- Output:
L(L(0,0),L(5,0),L(0,5)) L(L(0,0),L(5,0),L(0,6)) overlap L(L(0,0),L(0,5),L(5,0)) L(L(0,0),L(0,5),L(5,0)) overlap (reversed) L(L(0,0),L(5,0),L(0,5)) L(L(-10,0),L(-5,0),L(-1,6)) no overlap L(L(0,0),L(5,0),L(2.5,5)) L(L(0,4),L(2.5,-1),L(5,4)) overlap L(L(0,0),L(1,1),L(0,2)) L(L(2,1),L(3,0),L(3,2)) no overlap L(L(0,0),L(1,1),L(0,2)) L(L(2,1),L(3,-2),L(3,4)) no overlap Corner case (barely touching): True Corner case (barely touching): False