Determine if two triangles overlap: Difference between revisions
m (→{{header|zkl}}: crunch) |
Walterpachl (talk | contribs) (add REXX) |
||
Line 299: | Line 299: | ||
False False |
False False |
||
True ?</pre> |
True ?</pre> |
||
=={{header|REXX}}== |
|||
<lang> Signal On Halt |
|||
Signal On Novalue |
|||
Signal On Syntax |
|||
oid='trio.txt'; 'erase' oid |
|||
Call trio '0 0 5 0 0 5 0 0 5 0 0 6 ' |
|||
Call trio '0 0 0 5 5 0 0 0 0 5 5 0 ' |
|||
Call trio '0 0 5 0 0 5 -10 0 -5 0 -1 6 ' |
|||
Call trio '0 0 5 0 2.5 5 0 4 2.5 -1 5 4' |
|||
Call trio '0 0 1 1 0 2 2 1 3 0 3 2 ' |
|||
Call trio '0 0 1 1 0 2 2 1 3 -2 3 4 ' |
|||
Call trio '0 0 1 0 0 1 1 0 2 0 1 1 ' |
|||
Call trio '1 0 3 0 2 2 1 3 3 3 2 5 ' |
|||
Call trio '1 0 3 0 2 2 1 3 3 3 2 2 ' |
|||
Call trio '0 0 2 0 2 2 3 3 5 3 5 5 ' |
|||
Exit |
|||
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) |
|||
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 |
|||
Call o 'abc_='abc_ |
|||
Call o 'def_='def_ |
|||
over=0 |
|||
Do i=1 To 3 |
|||
Do j=1 To 3 |
|||
If ssx(s.i t.j) Then Do |
|||
over=1 |
|||
Leave |
|||
End |
|||
End |
|||
End |
|||
If over=0 Then Do |
|||
Do ii=1 To 3 Until over |
|||
Call o 'ii='ii 'def.'ii'='def.ii 'abc='abc |
|||
Call o ' ' 'abc.'ii'='abc.ii 'def='def |
|||
Select |
|||
When in_tri(def.ii,abc) Then over=1 |
|||
When in_tri(abc.ii,def) Then over=1 |
|||
Otherwise Nop |
|||
End |
|||
End |
|||
End |
|||
If over=0 Then rw='don''t ' |
|||
Else rw='' |
|||
Say 'Triangles' point(pax,pay) point(pbx,pby) point(pcx,pcy), |
|||
'and' point(pdx,pdy) point(pex,pey) point(pfx,pfy) rw'overlap' |
|||
Say '' |
|||
Return |
|||
ssx: Procedure Expose oid |
|||
/*--------------------------------------------------------------------- |
|||
* Intersection of 2 line segments |
|||
*--------------------------------------------------------------------*/ |
|||
Parse Arg xa ya xb yb xc yc xd yd |
|||
d=ggx(xa ya xb yb xc yc xd yd) |
|||
Call o d |
|||
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 |
|||
x='*' |
|||
y=ya |
|||
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='*' |
|||
End |
|||
End |
|||
End |
|||
Otherwise Do |
|||
Parse Var d x y |
|||
res=is_between(xa,x,xb) &, |
|||
is_between(xc,x,xd) &, |
|||
is_between(ya,y,yb) &, |
|||
is_between(yc,y,yd) |
|||
End |
|||
End |
|||
If xa=xc Then Do |
|||
x=xa |
|||
y='*' |
|||
End |
|||
If res=1 Then Call o 'intersection of line segments: ('||x'/'y')' |
|||
Return res |
|||
ggx: Procedure Expose oid |
|||
/*--------------------------------------------------------------------- |
|||
* Intersection of 2 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 |
|||
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) |
|||
o: |
|||
Return lineout(oid,arg(1)) |
|||
in_tri: Procedure Expose oid |
|||
/*--------------------------------------------------------------------- |
|||
* 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) |
|||
Call mk_g 1,'A','B' |
|||
Call mk_g 2,'B','C' |
|||
Call mk_g 3,'C','A' |
|||
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 px>maxx|px<minx|py>maxy|py<miny Then Nop |
|||
Else Do |
|||
kp1=k.1 |
|||
dp1=py-kp1*px |
|||
Call o 'p1: y='kp1'*x'dd(dp1) |
|||
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(ax,x12,bx) Then Do |
|||
Call o x12 px x13 |
|||
d12=x12-px |
|||
d13=x13-px |
|||
Call o d12 d13 |
|||
res=res|diff_sign(d12,d13) |
|||
End |
|||
If k.2='*' Then Do |
|||
x21=x.2 |
|||
x23=x.2 |
|||
End |
|||
Else Do |
|||
kp2=k.2 |
|||
dp2=py-kp2*px |
|||
Call o 'p2: y='kp2'*x'dd(dp2) |
|||
If k.1='*' Then |
|||
x21=x.1 |
|||
Else |
|||
x21=(d.1-dp2)/(kp2-k.1) |
|||
If k.3='*' Then |
|||
x23=x.3 |
|||
Else |
|||
x23=(d.3-dp2)/(kp2-k.3) |
|||
End |
|||
If is_between(bx,x21,ax) Then Do |
|||
Call o x21 px x23 |
|||
d21=x21-px |
|||
d23=x23-px |
|||
Call o d21 d23 |
|||
res=res|diff_sign(d21,d23) |
|||
End |
|||
kp3=k.3 |
|||
dp3=py-kp3*px |
|||
Call o 'p3: y='kp3'*x'dd(dp3) |
|||
If k.2='*' Then |
|||
x32=x.2 |
|||
Else |
|||
x32=(d.2-dp3)/(kp3-k.2) |
|||
x31=(d.1-dp3)/(kp3-k.1) |
|||
If is_between(cx,x32,bx) Then Do |
|||
Call o x31 px x32 |
|||
d31=x31-px |
|||
d32=x32-px |
|||
Call o d31 d32 |
|||
res=res|diff_sign(d31,d32) |
|||
End |
|||
End |
|||
If res=1 Then rr=' ' |
|||
Else rr=' not ' |
|||
Call o 'P ('px','py') is'rr'in' abc |
|||
Return res |
|||
mk_g: |
|||
Parse Arg g,a,b |
|||
g.g='('a','||b')' |
|||
If value(a||'x')=value(b||'x') Then Do |
|||
k.g='*' |
|||
x.g=value(a||'x') |
|||
End |
|||
Else Do |
|||
k.g=(value(b||'y')-value(a||'y'))/(value(b||'x')-value(a||'x')) |
|||
d.g=value(a||'y')-k.g*value(a||'x') |
|||
End |
|||
Return |
|||
dd: Procedure |
|||
Parse Arg dd |
|||
Select |
|||
When dd=0 Then dd='' |
|||
When dd<0 Then dd=dd |
|||
Otherwise dd='+'dd |
|||
End |
|||
Return dd |
|||
point: Return '('arg(1)','arg(2)')' |
|||
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> |
|||
{{out}} |
|||
<pre>Triangles (0,0) (5,0) (0,5) and (0,0) (5,0) (0,6 ) overlap |
|||
Triangles (0,0) (0,5) (5,0) and (0,0) (0,5) (5,0 ) overlap |
|||
Triangles (0,0) (5,0) (0,5) and (-10,0) (-5,0) (-1,6 ) don't overlap |
|||
Triangles (0,0) (5,0) (2.5,5) and (0,4) (2.5,-1) (5,4) overlap |
|||
Triangles (0,0) (1,1) (0,2) and (2,1) (3,0) (3,2 ) don't overlap |
|||
Triangles (0,0) (1,1) (0,2) and (2,1) (3,-2) (3,4 ) don't overlap |
|||
Triangles (0,0) (1,0) (0,1) and (1,0) (2,0) (1,1 ) overlap |
|||
Triangles (1,0) (3,0) (2,2) and (1,3) (3,3) (2,5 ) don't overlap |
|||
Triangles (1,0) (3,0) (2,2) and (1,3) (3,3) (2,2 ) overlap |
|||
Triangles (0,0) (2,0) (2,2) and (3,3) (5,3) (5,5 ) don't overlap</pre> |
|||
=={{header|zkl}}== |
=={{header|zkl}}== |
Revision as of 15:52, 1 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
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
<lang> Signal On Halt
Signal On Novalue Signal On Syntax
oid='trio.txt'; 'erase' oid
Call trio '0 0 5 0 0 5 0 0 5 0 0 6 ' Call trio '0 0 0 5 5 0 0 0 0 5 5 0 ' Call trio '0 0 5 0 0 5 -10 0 -5 0 -1 6 ' Call trio '0 0 5 0 2.5 5 0 4 2.5 -1 5 4' Call trio '0 0 1 1 0 2 2 1 3 0 3 2 ' Call trio '0 0 1 1 0 2 2 1 3 -2 3 4 ' Call trio '0 0 1 0 0 1 1 0 2 0 1 1 ' Call trio '1 0 3 0 2 2 1 3 3 3 2 5 ' Call trio '1 0 3 0 2 2 1 3 3 3 2 2 ' Call trio '0 0 2 0 2 2 3 3 5 3 5 5 ' Exit
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) 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
Call o 'abc_='abc_ Call o 'def_='def_
over=0
Do i=1 To 3 Do j=1 To 3 If ssx(s.i t.j) Then Do over=1 Leave End End End
If over=0 Then Do
Do ii=1 To 3 Until over Call o 'ii='ii 'def.'ii'='def.ii 'abc='abc Call o ' ' 'abc.'ii'='abc.ii 'def='def Select When in_tri(def.ii,abc) Then over=1 When in_tri(abc.ii,def) Then over=1 Otherwise Nop End End End
If over=0 Then rw='dont ' Else rw=
Say 'Triangles' point(pax,pay) point(pbx,pby) point(pcx,pcy),
'and' point(pdx,pdy) point(pex,pey) point(pfx,pfy) rw'overlap'
Say Return
ssx: Procedure Expose oid /*---------------------------------------------------------------------
- Intersection of 2 line segments
- --------------------------------------------------------------------*/
Parse Arg xa ya xb yb xc yc xd yd d=ggx(xa ya xb yb xc yc xd yd) Call o d 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 x='*' y=ya 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='*' End End End Otherwise Do Parse Var d x y res=is_between(xa,x,xb) &, is_between(xc,x,xd) &, is_between(ya,y,yb) &, is_between(yc,y,yd) End End If xa=xc Then Do x=xa y='*' End If res=1 Then Call o 'intersection of line segments: ('||x'/'y')'
Return res
ggx: Procedure Expose oid /*---------------------------------------------------------------------
- Intersection of 2 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
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)
o: Return lineout(oid,arg(1))
in_tri: Procedure Expose oid /*---------------------------------------------------------------------
- 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) Call mk_g 1,'A','B' Call mk_g 2,'B','C' Call mk_g 3,'C','A'
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 px>maxx|px<minx|py>maxy|py<miny Then Nop
Else Do
kp1=k.1 dp1=py-kp1*px Call o 'p1: y='kp1'*x'dd(dp1) 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(ax,x12,bx) Then Do Call o x12 px x13 d12=x12-px d13=x13-px Call o d12 d13 res=res|diff_sign(d12,d13) End If k.2='*' Then Do x21=x.2 x23=x.2 End Else Do kp2=k.2 dp2=py-kp2*px Call o 'p2: y='kp2'*x'dd(dp2) If k.1='*' Then x21=x.1 Else x21=(d.1-dp2)/(kp2-k.1) If k.3='*' Then x23=x.3 Else x23=(d.3-dp2)/(kp2-k.3) End If is_between(bx,x21,ax) Then Do Call o x21 px x23 d21=x21-px d23=x23-px Call o d21 d23 res=res|diff_sign(d21,d23) End kp3=k.3 dp3=py-kp3*px Call o 'p3: y='kp3'*x'dd(dp3) If k.2='*' Then x32=x.2 Else x32=(d.2-dp3)/(kp3-k.2) x31=(d.1-dp3)/(kp3-k.1) If is_between(cx,x32,bx) Then Do Call o x31 px x32 d31=x31-px d32=x32-px Call o d31 d32 res=res|diff_sign(d31,d32) End End
If res=1 Then rr=' '
Else rr=' not '
Call o 'P ('px','py') is'rr'in' abc Return res
mk_g: Parse Arg g,a,b g.g='('a','||b')' If value(a||'x')=value(b||'x') Then Do
k.g='*' x.g=value(a||'x') End
Else Do
k.g=(value(b||'y')-value(a||'y'))/(value(b||'x')-value(a||'x')) d.g=value(a||'y')-k.g*value(a||'x') End
Return
dd: Procedure
Parse Arg dd Select When dd=0 Then dd= When dd<0 Then dd=dd Otherwise dd='+'dd End Return dd
point: Return '('arg(1)','arg(2)')'
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:
Triangles (0,0) (5,0) (0,5) and (0,0) (5,0) (0,6 ) overlap Triangles (0,0) (0,5) (5,0) and (0,0) (0,5) (5,0 ) overlap Triangles (0,0) (5,0) (0,5) and (-10,0) (-5,0) (-1,6 ) don't overlap Triangles (0,0) (5,0) (2.5,5) and (0,4) (2.5,-1) (5,4) overlap Triangles (0,0) (1,1) (0,2) and (2,1) (3,0) (3,2 ) don't overlap Triangles (0,0) (1,1) (0,2) and (2,1) (3,-2) (3,4 ) don't overlap Triangles (0,0) (1,0) (0,1) and (1,0) (2,0) (1,1 ) overlap Triangles (1,0) (3,0) (2,2) and (1,3) (3,3) (2,5 ) don't overlap Triangles (1,0) (3,0) (2,2) and (1,3) (3,3) (2,2 ) overlap Triangles (0,0) (2,0) (2,2) and (3,3) (5,3) (5,5 ) don't 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