Determine if two triangles overlap: Difference between revisions
Content added Content deleted
No edit summary |
Alextretyak (talk | contribs) (Added 11l) |
||
Line 20: | Line 20: | ||
:::* (0,0),(1,0),(0,1) and (1,0),(2,0),(1,1) |
:::* (0,0),(1,0),(0,1) and (1,0),(2,0),(1,1) |
||
<br><br> |
<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}}== |
=={{header|Ada}}== |