Determine if two triangles overlap: Difference between revisions
Added 11l
No edit summary |
Alextretyak (talk | contribs) (Added 11l) |
||
Line 20:
:::* (0,0),(1,0),(0,1) and (1,0),(2,0),(1,1)
<br><br>
=={{header|11l}}==
{{trans|D}}
<lang 11l>T Triangle
(Float, Float) p1, p2, p3
F (p1, p2, p3)
.p1 = p1
.p2 = p2
.p3 = p3
F String()
R ‘Triangle: #., #., #.’.format(.p1, .p2, .p3)
F.const det2D()
R .p1[0] * (.p2[1] - .p3[1])
+ .p2[0] * (.p3[1] - .p1[1])
+ .p3[0] * (.p1[1] - .p2[1])
F checkTriWinding(Triangle &t; allowReversed)
V detTri = t.det2D()
I detTri < 0.0
assert(allowReversed, ‘Triangle has wrong winding direction’)
swap(&t.p2, &t.p3)
F boundaryCollideChk(Triangle t, Float eps)
R t.det2D() < eps
F boundaryDoesntCollideChk(Triangle t, Float eps)
R t.det2D() <= eps
F triTri2D(Triangle &t1, &t2; eps = 0.0, allowReversed = 0B, onBoundary = 1B)
checkTriWinding(&t1, allowReversed)
checkTriWinding(&t2, allowReversed)
V chkEdge = I onBoundary {:boundaryCollideChk} E :boundaryDoesntCollideChk
V lp1 = [t1.p1, t1.p2, t1.p3]
V lp2 = [t2.p1, t2.p2, t2.p3]
L(i) 3
V j = (i + 1) % 3
I chkEdge(Triangle(lp1[i], lp1[j], lp2[0]), eps) &
chkEdge(Triangle(lp1[i], lp1[j], lp2[1]), eps) &
chkEdge(Triangle(lp1[i], lp1[j], lp2[2]), eps)
R 0B
L(i) 3
V j = (i + 1) % 3
I chkEdge(Triangle(lp2[i], lp2[j], lp1[0]), eps) &
chkEdge(Triangle(lp2[i], lp2[j], lp1[1]), eps) &
chkEdge(Triangle(lp2[i], lp2[j], lp1[2]), eps)
R 0B
R 1B
F overlap(Triangle &t1, &t2; eps = 0.0, allowReversed = 0B, onBoundary = 1B)
I triTri2D(&t1, &t2, eps, allowReversed, onBoundary)
print(‘overlap’)
E
print(‘do not overlap’)
V t1 = Triangle((0.0, 0.0), (5.0, 0.0), (0.0, 5.0))
V t2 = Triangle((0.0, 0.0), (5.0, 0.0), (0.0, 6.0))
print(t1" and\n"t2)
overlap(&t1, &t2)
print()
t1 = Triangle((0.0, 0.0), (0.0, 5.0), (5.0, 0.0))
t2 = t1
print(t1" and\n"t2)
overlap(&t1, &t2, 0.0, 1B)
print()
t1 = Triangle((0.0, 0.0), (5.0, 0.0), (0.0, 5.0))
t2 = Triangle((-10.0, 0.0), (-5.0, 0.0), (-1.0, 6.0))
print(t1" and\n"t2)
overlap(&t1, &t2)
print()
t1.p3 = (2.5, 5.0)
t2 = Triangle((0.0, 4.0), (2.5, -1.0), (5.0, 4.0))
print(t1" and\n"t2)
overlap(&t1, &t2)
print()
t1 = Triangle((0.0, 0.0), (1.0, 1.0), (0.0, 2.0))
t2 = Triangle((2.0, 1.0), (3.0, 0.0), (3.0, 2.0))
print(t1" and\n"t2)
overlap(&t1, &t2)
print()
t2 = Triangle((2.0, 1.0), (3.0, -2.0), (3.0, 4.0))
print(t1" and\n"t2)
overlap(&t1, &t2)
print()
t1 = Triangle((0.0, 0.0), (1.0, 0.0), (0.0, 1.0))
t2 = Triangle((1.0, 0.0), (2.0, 0.0), (1.0, 1.1))
print(t1" and\n"t2)
print(‘which have only a single corner in contact, if boundary points collide’)
overlap(&t1, &t2)
print()
print(t1" and\n"t2)
print(‘which have only a single corner in contact, if boundary points do not collide’)
overlap(&t1, &t2, 0.0, 0B, 0B)</lang>
{{out}}
<pre>
Triangle: (0, 0), (5, 0), (0, 5) and
Triangle: (0, 0), (5, 0), (0, 6)
overlap
Triangle: (0, 0), (0, 5), (5, 0) and
Triangle: (0, 0), (0, 5), (5, 0)
overlap
Triangle: (0, 0), (5, 0), (0, 5) and
Triangle: (-10, 0), (-5, 0), (-1, 6)
do not overlap
Triangle: (0, 0), (5, 0), (2.5, 5) and
Triangle: (0, 4), (2.5, -1), (5, 4)
overlap
Triangle: (0, 0), (1, 1), (0, 2) and
Triangle: (2, 1), (3, 0), (3, 2)
do not overlap
Triangle: (0, 0), (1, 1), (0, 2) and
Triangle: (2, 1), (3, -2), (3, 4)
do not overlap
Triangle: (0, 0), (1, 0), (0, 1) and
Triangle: (1, 0), (2, 0), (1, 1.1)
which have only a single corner in contact, if boundary points collide
overlap
Triangle: (0, 0), (1, 0), (0, 1) and
Triangle: (1, 0), (2, 0), (1, 1.1)
which have only a single corner in contact, if boundary points do not collide
do not overlap
</pre>
=={{header|Ada}}==
| |||