Determine if two triangles overlap: Difference between revisions
Determine if two triangles overlap (view source)
Revision as of 21:56, 14 December 2017
, 6 years agoAdded a solution for D
(→{{header|Kotlin}}: Updated example see https://github.com/dkandalov/rosettacode-kotlin for details) |
(Added a solution for D) |
||
Line 150:
1,1
0,0</pre>
=={{header|D}}==
{{trans|Kotlin}}
<lang D>import std.stdio;
import std.typecons;
alias Pair = Tuple!(real, real);
struct Triangle {
Pair p1;
Pair p2;
Pair p3;
void toString(scope void delegate(const(char)[]) sink) const {
import std.format;
sink("Triangle: ");
formattedWrite!"%s"(sink, p1);
sink(", ");
formattedWrite!"%s"(sink, p2);
sink(", ");
formattedWrite!"%s"(sink, p3);
}
}
auto det2D(Triangle t) {
return t.p1[0] *(t.p2[1] - t.p3[1])
+ t.p2[0] *(t.p3[1] - t.p1[1])
+ t.p3[0] *(t.p1[1] - t.p2[1]);
}
void checkTriWinding(Triangle t, bool allowReversed) {
auto detTri = t.det2D();
if (detTri < 0.0) {
if (allowReversed) {
auto a = t.p3;
t.p3 = t.p2;
t.p2 = a;
} else {
throw new Exception("Triangle has wrong winding direction");
}
}
}
auto boundaryCollideChk(Triangle t, real eps) {
return t.det2D() < eps;
}
auto boundaryDoesntCollideChk(Triangle t, real eps) {
return t.det2D() <= eps;
}
bool triTri2D(Triangle t1, Triangle t2, real eps = 0.0, bool allowReversed = false, bool onBoundary = true) {
// Triangles must be expressed anti-clockwise
checkTriWinding(t1, allowReversed);
checkTriWinding(t2, allowReversed);
// 'onBoundary' determines whether points on boundary are considered as colliding or not
auto chkEdge = onBoundary ? &boundaryCollideChk : &boundaryDoesntCollideChk;
auto lp1 = [t1.p1, t1.p2, t1.p3];
auto lp2 = [t2.p1, t2.p2, t2.p3];
// for each edge E of t1
foreach (i; 0..3) {
auto j = (i + 1) % 3;
// Check all points of t2 lay on the external side of edge E.
// If they do, the triangles do not overlap.
if (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)) {
return false;
}
}
// for each edge E of t2
foreach (i; 0..3) {
auto j = (i + 1) % 3;
// Check all points of t1 lay on the external side of edge E.
// If they do, the triangles do not overlap.
if (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)) {
return false;
}
}
// The triangles overlap
return true;
}
void overlap(Triangle t1, Triangle t2, real eps = 0.0, bool allowReversed = false, bool onBoundary = true) {
if (triTri2D(t1, t2, eps, allowReversed, onBoundary)) {
writeln("overlap");
} else {
writeln("do not overlap");
}
}
void main() {
auto t1 = Triangle(Pair(0.0, 0.0), Pair(5.0, 0.0), Pair(0.0, 5.0));
auto t2 = Triangle(Pair(0.0, 0.0), Pair(5.0, 0.0), Pair(0.0, 6.0));
writeln(t1, " and\n", t2);
overlap(t1, t2);
writeln;
// need to allow reversed for this pair to avoid exception
t1 = Triangle(Pair(0.0, 0.0), Pair(0.0, 5.0), Pair(5.0, 0.0));
t2 = t1;
writeln(t1, " and\n", t2);
overlap(t1, t2, 0.0, true);
writeln;
t1 = Triangle(Pair(0.0, 0.0), Pair(5.0, 0.0), Pair(0.0, 5.0));
t2 = Triangle(Pair(-10.0, 0.0), Pair(-5.0, 0.0), Pair(-1.0, 6.0));
writeln(t1, " and\n", t2);
overlap(t1, t2);
writeln;
t1.p3 = Pair(2.5, 5.0);
t2 = Triangle(Pair(0.0, 4.0), Pair(2.5, -1.0), Pair(5.0, 4.0));
writeln(t1, " and\n", t2);
overlap(t1, t2);
writeln;
t1 = Triangle(Pair(0.0, 0.0), Pair(1.0, 1.0), Pair(0.0, 2.0));
t2 = Triangle(Pair(2.0, 1.0), Pair(3.0, 0.0), Pair(3.0, 2.0));
writeln(t1, " and\n", t2);
overlap(t1, t2);
writeln;
t2 = Triangle(Pair(2.0, 1.0), Pair(3.0, -2.0), Pair(3.0, 4.0));
writeln(t1, " and\n", t2);
overlap(t1, t2);
writeln;
t1 = Triangle(Pair(0.0, 0.0), Pair(1.0, 0.0), Pair(0.0, 1.0));
t2 = Triangle(Pair(1.0, 0.0), Pair(2.0, 0.0), Pair(1.0, 1.1));
writeln(t1, " and\n", t2);
writeln("which have only a single corner in contact, if boundary points collide");
overlap(t1, t2);
writeln;
writeln(t1, " and\n", t2);
writeln("which have only a single corner in contact, if boundary points do not collide");
overlap(t1, t2, 0.0, false, false);
}</lang>
{{out}}
<pre>Triangle: Tuple!(real, real)(0, 0), Tuple!(real, real)(5, 0), Tuple!(real, real)(0, 5) and
Triangle: Tuple!(real, real)(0, 0), Tuple!(real, real)(5, 0), Tuple!(real, real)(0, 6)
overlap
Triangle: Tuple!(real, real)(0, 0), Tuple!(real, real)(0, 5), Tuple!(real, real)(5, 0) and
Triangle: Tuple!(real, real)(0, 0), Tuple!(real, real)(0, 5), Tuple!(real, real)(5, 0)
overlap
Triangle: Tuple!(real, real)(0, 0), Tuple!(real, real)(5, 0), Tuple!(real, real)(0, 5) and
Triangle: Tuple!(real, real)(-10, 0), Tuple!(real, real)(-5, 0), Tuple!(real, real)(-1, 6)
do not overlap
Triangle: Tuple!(real, real)(0, 0), Tuple!(real, real)(5, 0), Tuple!(real, real)(2.5, 5) and
Triangle: Tuple!(real, real)(0, 4), Tuple!(real, real)(2.5, -1), Tuple!(real, real)(5, 4)
overlap
Triangle: Tuple!(real, real)(0, 0), Tuple!(real, real)(1, 1), Tuple!(real, real)(0, 2) and
Triangle: Tuple!(real, real)(2, 1), Tuple!(real, real)(3, 0), Tuple!(real, real)(3, 2)
do not overlap
Triangle: Tuple!(real, real)(0, 0), Tuple!(real, real)(1, 1), Tuple!(real, real)(0, 2) and
Triangle: Tuple!(real, real)(2, 1), Tuple!(real, real)(3, -2), Tuple!(real, real)(3, 4)
do not overlap
Triangle: Tuple!(real, real)(0, 0), Tuple!(real, real)(1, 0), Tuple!(real, real)(0, 1) and
Triangle: Tuple!(real, real)(1, 0), Tuple!(real, real)(2, 0), Tuple!(real, real)(1, 1.1)
which have only a single corner in contact, if boundary points collide
overlap
Triangle: Tuple!(real, real)(0, 0), Tuple!(real, real)(1, 0), Tuple!(real, real)(0, 1) and
Triangle: Tuple!(real, real)(1, 0), Tuple!(real, real)(2, 0), Tuple!(real, real)(1, 1.1)
which have only a single corner in contact, if boundary points do not collide
do not overlap</pre>
=={{header|Kotlin}}==
| |||