Determine if two triangles overlap: Difference between revisions

Content added Content deleted

Inline

Revision as of 01:22, 31 December 2018

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

Translation of: C++

<lang c>#include <errno.h>

include <stdbool.h>
include <stdio.h>
include <stdlib.h>

typedef struct {

   double x, y;

} Point;

double det2D(const Point * const p1, const Point * const p2, const Point * const p3) {

   return p1->x * (p2->y - p3->y)
       + p2->x * (p3->y - p1->y)
       + p3->x * (p1->y - p2->y);

}

void checkTriWinding(Point * p1, Point * p2, Point * p3, bool allowReversed) {

   double detTri = det2D(p1, p2, p3);
   if (detTri < 0.0) {
       if (allowReversed) {
           double t = p3->x;
           p3->x = p2->x;
           p2->x = t;

           t = p3->y;
           p3->y = p2->y;
           p2->y = t;
       } else {
           errno = 1;
       }
   }

}

bool boundaryCollideChk(const Point *p1, const Point *p2, const Point *p3, double eps) {

   return det2D(p1, p2, p3) < eps;

}

bool boundaryDoesntCollideChk(const Point *p1, const Point *p2, const Point *p3, double eps) {

   return det2D(p1, p2, p3) <= eps;

}

bool triTri2D(Point t1[], Point t2[], double eps, bool allowReversed, bool onBoundary) {

   bool(*chkEdge)(Point*, Point*, Point*, double);
   int i;

   // Triangles must be expressed anti-clockwise
   checkTriWinding(&t1[0], &t1[1], &t1[2], allowReversed);
   if (errno != 0) {
       return false;
   }
   checkTriWinding(&t2[0], &t2[1], &t2[2], allowReversed);
   if (errno != 0) {
       return false;
   }

   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 (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 (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() {

   {
       Point t1[] = { {0, 0}, {5, 0}, {0, 5} };
       Point t2[] = { {0, 0}, {5, 0}, {0, 6} };
       printf("%d,true\n", triTri2D(t1, t2, 0.0, false, true));
   }

   {
       Point t1[] = { {0, 0}, {0, 5}, {5, 0} };
       Point t2[] = { {0, 0}, {0, 5}, {5, 0} };
       printf("%d,true\n", triTri2D(t1, t2, 0.0, true, true));
   }

   {
       Point t1[] = { {0, 0}, {5, 0}, {0, 5} };
       Point t2[] = { {-10, 0}, {-5, 0}, {-1, 6} };
       printf("%d,false\n", triTri2D(t1, t2, 0.0, false, true));
   }

   {
       Point t1[] = { {0, 0}, {5, 0}, {2.5, 5} };
       Point t2[] = { {0, 4}, {2.5, -1}, {5, 4} };
       printf("%d,true\n", triTri2D(t1, t2, 0.0, false, true));
   }

   {
       Point t1[] = { {0, 0}, {1, 1}, {0, 2} };
       Point t2[] = { {2, 1}, {3, 0}, {3, 2} };
       printf("%d,false\n", triTri2D(t1, t2, 0.0, false, true));
   }

   {
       Point t1[] = { {0, 0}, {1, 1}, {0, 2} };
       Point t2[] = { {2, 1}, {3, -2}, {3, 4} };
       printf("%d,false\n", triTri2D(t1, t2, 0.0, false, true));
   }

   //Barely touching
   {
       Point t1[] = { {0, 0}, {1, 0}, {0, 1} };
       Point t2[] = { {1, 0}, {2, 0}, {1, 1} };
       printf("%d,true\n", triTri2D(t1, t2, 0.0, false, true));
   }

   //Barely touching
   {
       Point t1[] = { {0, 0}, {1, 0}, {0, 1} };
       Point t2[] = { {1, 0}, {2, 0}, {1, 1} };
       printf("%d,false\n", triTri2D(t1, t2, 0.0, false, false));
   }

   return EXIT_SUCCESS;

}</lang>

Output:

1,true
1,true
0,false
1,true
0,false
0,false
1,true
0,false

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

C#

<lang csharp>using System; using System.Collections.Generic;

namespace TriangleOverlap {

   class Triangle {
       public Tuple<double, double> P1 { get; set; }
       public Tuple<double, double> P2 { get; set; }
       public Tuple<double, double> P3 { get; set; }

       public Triangle(Tuple<double, double> p1, Tuple<double, double> p2, Tuple<double, double> p3) {
           P1 = p1;
           P2 = p2;
           P3 = p3;
       }

       public double Det2D() {
           return P1.Item1 * (P2.Item2 - P3.Item2)
                + P2.Item1 * (P3.Item2 - P1.Item2)
                + P3.Item1 * (P3.Item1 - P2.Item2);
       }

       public void CheckTriWinding(bool allowReversed) {
           var detTri = Det2D();
           if (detTri < 0.0) {
               if (allowReversed) {
                   var a = P3;
                   P3 = P2;
                   P2 = a;
               } else {
                   throw new Exception("Triangle has wrong winding direction");
               }
           }
       }

       public bool BoundaryCollideChk(double eps) {
           return Det2D() < eps;
       }

       public bool BoundaryDoesntCollideChk(double eps) {
           return Det2D() <= eps;
       }

       public override string ToString() {
           return string.Format("Triangle: {0}, {1}, {2}", P1, P2, P3);
       }
   }

   class Program {
       static bool BoundaryCollideChk(Triangle t, double eps) {
           return t.BoundaryCollideChk(eps);
       }

       static bool BoundaryDoesntCollideChk(Triangle t, double eps) {
           return t.BoundaryDoesntCollideChk(eps);
       }

       static bool TriTri2D(Triangle t1, Triangle t2, double eps = 0.0, bool allowReversed = false, bool onBoundary = true) {
           // Triangles must be expressed anti-clockwise
           t1.CheckTriWinding(allowReversed);
           t2.CheckTriWinding(allowReversed);
           // 'onBoundary' determines whether points on boundary are considered as colliding or not
           var chkEdge = onBoundary
               ? (Func<Triangle, double, bool>)BoundaryCollideChk
               : BoundaryDoesntCollideChk;
           List<Tuple<double, double>> lp1 = new List<Tuple<double, double>>() { t1.P1, t1.P2, t1.P3 };
           List<Tuple<double, double>> lp2 = new List<Tuple<double, double>>() { t2.P1, t2.P2, t2.P3 };

           // for each edge E of t1
           for (int i = 0; i < 3; i++) {
               var 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(new Triangle(lp1[i], lp1[j], lp2[0]), eps) &&
                   chkEdge(new Triangle(lp1[i], lp1[j], lp2[1]), eps) &&
                   chkEdge(new Triangle(lp1[i], lp1[j], lp2[2]), eps)) {
                   return false;
               }
           }

           // for each edge E of t2
           for (int i = 0; i < 3; i++) {
               var 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(new Triangle(lp2[i], lp2[j], lp1[0]), eps) &&
                   chkEdge(new Triangle(lp2[i], lp2[j], lp1[1]), eps) &&
                   chkEdge(new Triangle(lp2[i], lp2[j], lp1[2]), eps)) {
                   return false;
               }
           }

           // The triangles overlap
           return true;
       }

       static void Overlap(Triangle t1, Triangle t2, double eps = 0.0, bool allowReversed = false, bool onBoundary = true) {
           if (TriTri2D(t1, t2, eps, allowReversed, onBoundary)) {
               Console.WriteLine("overlap");
           } else {
               Console.WriteLine("do not overlap");
           }
       }

       static void Main(string[] args) {
           var t1 = new Triangle(new Tuple<double, double>(0.0, 0.0), new Tuple<double, double>(5.0, 0.0), new Tuple<double, double>(0.0, 5.0));
           var t2 = new Triangle(new Tuple<double, double>(0.0, 0.0), new Tuple<double, double>(5.0, 0.0), new Tuple<double, double>(0.0, 6.0));
           Console.WriteLine("{0} and\n{1}", t1, t2);
           Overlap(t1, t2);
           Console.WriteLine();

           // need to allow reversed for this pair to avoid exception
           t1 = new Triangle(new Tuple<double, double>(0.0, 0.0), new Tuple<double, double>(0.0, 5.0), new Tuple<double, double>(5.0, 0.0));
           t2 = t1;
           Console.WriteLine("{0} and\n{1}", t1, t2);
           Overlap(t1, t2, 0.0, true);
           Console.WriteLine();

           t1 = new Triangle(new Tuple<double, double>(0.0, 0.0), new Tuple<double, double>(5.0, 0.0), new Tuple<double, double>(0.0, 5.0));
           t2 = new Triangle(new Tuple<double, double>(-10.0, 0.0), new Tuple<double, double>(-5.0, 0.0), new Tuple<double, double>(-1.0, 6.0));
           Console.WriteLine("{0} and\n{1}", t1, t2);
           Overlap(t1, t2);
           Console.WriteLine();

           t1.P3 = new Tuple<double, double>(2.5, 5.0);
           t2 = new Triangle(new Tuple<double, double>(0.0, 4.0), new Tuple<double, double>(2.5, -1.0), new Tuple<double, double>(5.0, 4.0));
           Console.WriteLine("{0} and\n{1}", t1, t2);
           Overlap(t1, t2);
           Console.WriteLine();

           t1 = new Triangle(new Tuple<double, double>(0.0, 0.0), new Tuple<double, double>(1.0, 1.0), new Tuple<double, double>(0.0, 2.0));
           t2 = new Triangle(new Tuple<double, double>(2.0, 1.0), new Tuple<double, double>(3.0, 0.0), new Tuple<double, double>(3.0, 2.0));
           Console.WriteLine("{0} and\n{1}", t1, t2);
           Overlap(t1, t2);
           Console.WriteLine();

           t2 = new Triangle(new Tuple<double, double>(2.0, 1.0), new Tuple<double, double>(3.0, -2.0), new Tuple<double, double>(3.0, 4.0));
           Console.WriteLine("{0} and\n{1}", t1, t2);
           Overlap(t1, t2);
           Console.WriteLine();

           t1 = new Triangle(new Tuple<double, double>(0.0, 0.0), new Tuple<double, double>(1.0, 0.0), new Tuple<double, double>(0.0, 1.0));
           t2 = new Triangle(new Tuple<double, double>(1.0, 0.0), new Tuple<double, double>(2.0, 0.0), new Tuple<double, double>(1.0, 1.1));
           Console.WriteLine("{0} and\n{1}", t1, t2);
           Console.WriteLine("which have only a single corner in contact, if boundary points collide");
           Overlap(t1, t2);
           Console.WriteLine();

           Console.WriteLine("{0} and\n{1}", t1, t2);
           Console.WriteLine("which have only a single corner in contact, if boundary points do not collide");
           Overlap(t1, t2, 0.0, false, false);
       }
   }

}</lang>

Output:

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
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 do not collide
do not overlap

D

Translation of: 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>

Output:

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

F#

Translation of: Kotlin

<lang fsharp>open System

type Point = double * double type Triangle = Point * Point * Point

let Det2D (t:Triangle) =

   let (p1, p2, p3) = t
   let (p1x, p1y) = p1
   let (p2x, p2y) = p2
   let (p3x, p3y) = p3

   p1x * (p2y - p3y) +
   p2x * (p3y - p1y) +
   p3x * (p1y - p2y)

let CheckTriWinding allowReversed t =

   let detTri = Det2D t
   if detTri < 0.0 then
       if allowReversed then
           let (p1, p2, p3) = t
           (p1, p3, p2)
       else
           raise (Exception "Triangle has wrong winding direction")
   else
       t

let boundaryCollideChk eps t =

   (Det2D t) < eps

let boundaryDoesntCollideChk eps t =

   (Det2D t) <= eps

let TriTri2D eps allowReversed onBoundary t1 t2 =

   // Triangles must be expressed anti-clockwise
   let t3 = CheckTriWinding allowReversed t1
   let t4 = CheckTriWinding allowReversed t2

   // 'onBoundary' determines whether points on boundary are considered as colliding or not
   let chkEdge = if onBoundary then boundaryCollideChk else boundaryDoesntCollideChk
   let (t1p1, t1p2, t1p3) = t3
   let (t2p1, t2p2, t2p3) = t4

   // Check all points of t2 lay on the external side of edge E.
   // If they do, the triangles do not overlap.
   if (chkEdge eps (t1p1, t1p2, t2p1)) && (chkEdge eps (t1p1, t1p2, t2p2)) && (chkEdge eps (t1p1, t1p2, t2p3)) then
       false
   else if (chkEdge eps (t1p2, t1p3, t2p1)) && (chkEdge eps (t1p2, t1p3, t2p2)) && (chkEdge eps (t1p2, t1p3, t2p3)) then
       false
   else if (chkEdge eps (t1p3, t1p1, t2p1)) && (chkEdge eps (t1p3, t1p1, t2p2)) && (chkEdge eps (t1p3, t1p1, t2p3)) then
       false

   // Check all points of t1 lay on the external side of edge E.
   // If they do, the triangles do not overlap.
   else if (chkEdge eps (t2p1, t2p2, t1p1)) && (chkEdge eps (t2p1, t2p2, t1p2)) && (chkEdge eps (t2p1, t2p2, t1p3)) then
       false
   else if (chkEdge eps (t2p2, t2p3, t1p1)) && (chkEdge eps (t2p2, t2p3, t1p2)) && (chkEdge eps (t2p2, t2p3, t1p3)) then
       false
   else if (chkEdge eps (t2p3, t2p1, t1p1)) && (chkEdge eps (t2p3, t2p1, t1p2)) && (chkEdge eps (t2p3, t2p1, t1p3)) then
       false

   else
       // The triangles overlap
       true

let Print t1 t2 =

   Console.WriteLine("{0} and\n{1}\n{2}\n", t1, t2, if TriTri2D 0.0 false true t1 t2 then "overlap" else "do not overlap")

[<EntryPoint>] let main _ =

   let t1 = ((0.0, 0.0), (5.0, 0.0), (0.0, 5.0))
   let t2 = ((0.0, 0.0), (5.0, 0.0), (0.0, 6.0))
   Print t1 t2

   let t3 = ((0.0, 0.0), (0.0, 5.0), (5.0, 0.0))
   Console.WriteLine("{0} and\n{1}\n{2}\n", t3, t3, if TriTri2D 0.0 true true t3 t3 then "overlap (reversed)" else "do not overlap")

   let t4 = ((0.0, 0.0), (5.0, 0.0), (0.0, 5.0))
   let t5 = ((-10.0, 0.0), (-5.0, 0.0), (-1.0, 6.0))
   Print t4 t5

   let t6 = ((0.0, 0.0), (5.0, 0.0), (2.5, 5.0))
   let t7 = ((0.0, 4.0), (2.5, -1.0), (5.0, 4.0))
   Print t6 t7

   let t8 = ((0.0, 0.0), (1.0, 1.0), (0.0, 2.0))
   let t9 = ((2.0, 1.0), (3.0, 0.0), (3.0, 2.0))
   Print t8 t9

   let t10 = ((2.0, 1.0), (3.0, -2.0), (3.0, 4.0))
   Print t8 t10

   let t11 = ((0.0, 0.0), (1.0, 0.0), (0.0, 1.0))
   let t12 = ((1.0, 0.0), (2.0, 0.0), (1.0, 1.1))
   printfn "The following triangles which have only a single corner in contact, if boundary points collide"
   Print t11 t12

   Console.WriteLine("{0} and\n{1}\nwhich have only a single corner in contact, if boundary points do not collide\n{2}", t11, t12, if TriTri2D 0.0 false false t11 t12 then "overlap" else "do not overlap")

   0 // return an integer exit code</lang>

Output:

((0, 0), (5, 0), (0, 5)) and
((0, 0), (5, 0), (0, 6))
overlap

((0, 0), (0, 5), (5, 0)) and
((0, 0), (0, 5), (5, 0))
overlap (reversed)

((0, 0), (5, 0), (0, 5)) and
((-10, 0), (-5, 0), (-1, 6))
do not overlap

((0, 0), (5, 0), (2.5, 5)) and
((0, 4), (2.5, -1), (5, 4))
overlap

((0, 0), (1, 1), (0, 2)) and
((2, 1), (3, 0), (3, 2))
do not overlap

((0, 0), (1, 1), (0, 2)) and
((2, 1), (3, -2), (3, 4))
do not overlap

The following triangles which have only a single corner in contact, if boundary points collide
((0, 0), (1, 0), (0, 1)) and
((1, 0), (2, 0), (1, 1.1))
overlap

((0, 0), (1, 0), (0, 1)) and
((1, 0), (2, 0), (1, 1.1))
which have only a single corner in contact, if boundary points do not collide
do not overlap

Go

Translation of: Kotlin

<lang go>package main

import "fmt"

type point struct {

   x, y float64

}

func (p point) String() string {

   return fmt.Sprintf("(%.1f, %.1f)", p.x, p.y)

}

type triangle struct {

   p1, p2, p3 point

}

func (t *triangle) String() string {

   return fmt.Sprintf("Triangle %s, %s, %s", t.p1, t.p2, t.p3)

}

func (t *triangle) det2D() float64 {

   return t.p1.x * (t.p2.y - t.p3.y) +
          t.p2.x * (t.p3.y - t.p1.y) +
          t.p3.x * (t.p1.y - t.p2.y)

}

func (t *triangle) checkTriWinding(allowReversed bool) {

   detTri := t.det2D()
   if detTri < 0.0 {
       if allowReversed {
           a := t.p3
           t.p3 = t.p2
           t.p2 = a
       } else {
           panic("Triangle has wrong winding direction.")
       }
   }

}

func boundaryCollideChk(t *triangle, eps float64) bool {

   return t.det2D() < eps

}

func boundaryDoesntCollideChk(t *triangle, eps float64) bool {

   return t.det2D() <= eps

}

func triTri2D(t1, t2 *triangle, eps float64, allowReversed, onBoundary bool) bool {

   // Triangles must be expressed anti-clockwise.
   t1.checkTriWinding(allowReversed)
   t2.checkTriWinding(allowReversed)

   // 'onBoundary' determines whether points on boundary are considered as colliding or not.
   var chkEdge func (*triangle, float64) bool
   if onBoundary {
       chkEdge = boundaryCollideChk
   } else {
       chkEdge = boundaryDoesntCollideChk
   }
   lp1 := [3]point{t1.p1, t1.p2, t1.p3}
   lp2 := [3]point{t2.p1, t2.p2, t2.p3}

   // for each edge E of t1
   for i := 0; i < 3; i++ {
       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.
       tri1 := &triangle{lp1[i], lp1[j], lp2[0]}
       tri2 := &triangle{lp1[i], lp1[j], lp2[1]}
       tri3 := &triangle{lp1[i], lp1[j], lp2[2]}
       if chkEdge(tri1, eps) && chkEdge(tri2, eps) && chkEdge(tri3, eps) {
           return false
       }
   }

   // for each edge E of t2
   for i := 0; i < 3; i++ {
       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.
       tri1 := &triangle{lp2[i], lp2[j], lp1[0]}
       tri2 := &triangle{lp2[i], lp2[j], lp1[1]}
       tri3 := &triangle{lp2[i], lp2[j], lp1[2]}
       if chkEdge(tri1, eps) && chkEdge(tri2, eps) && chkEdge(tri3, eps) {
           return false
       }
   }

   // The triangles overlap.
   return true

}

func iff(cond bool, s1, s2 string) string {

   if cond {
       return s1
   }
   return s2

}

func main() {

   t1 := &triangle{point{0.0, 0.0}, point{5.0, 0.0}, point{0.0, 5.0}}
   t2 := &triangle{point{0.0, 0.0}, point{5.0, 0.0}, point{0.0, 6.0}}
   fmt.Printf("%s and\n%s\n", t1, t2)
   overlapping := triTri2D(t1, t2, 0.0, false, true)
   fmt.Println(iff(overlapping, "overlap", "do not overlap"))

   // Need to allow reversed for this pair to avoid panic.
   t1 = &triangle{point{0.0, 0.0}, point{0.0, 5.0}, point{5.0, 0.0}}
   t2 = t1
   fmt.Printf("\n%s and\n%s\n", t1, t2)
   overlapping = triTri2D(t1, t2, 0.0, true, true)
   fmt.Println(iff(overlapping, "overlap (reversed)", "do not overlap"))

   t1 = &triangle{point{0.0, 0.0}, point{5.0, 0.0}, point{0.0, 5.0}}
   t2 = &triangle{point{-10.0, 0.0}, point{-5.0, 0.0}, point{-1.0, 6.0}}
   fmt.Printf("\n%s and\n%s\n", t1, t2)
   overlapping = triTri2D(t1, t2, 0.0, false, true)
   fmt.Println(iff(overlapping, "overlap", "do not overlap"))

   t1.p3 = point{2.5, 5.0}
   t2 = &triangle{point{0.0, 4.0}, point{2.5, -1.0}, point{5.0, 4.0}}
   fmt.Printf("\n%s and\n%s\n", t1, t2)
   overlapping = triTri2D(t1, t2, 0.0, false, true)
   fmt.Println(iff(overlapping, "overlap", "do not overlap"))

   t1 = &triangle{point{0.0, 0.0}, point{1.0, 1.0}, point{0.0, 2.0}}
   t2 = &triangle{point{2.0, 1.0}, point{3.0, 0.0}, point{3.0, 2.0}}
   fmt.Printf("\n%s and\n%s\n", t1, t2)
   overlapping = triTri2D(t1, t2, 0.0, false, true)
   fmt.Println(iff(overlapping, "overlap", "do not overlap"))

   t2 = &triangle{point{2.0, 1.0}, point{3.0, -2.0}, point{3.0, 4.0}}
   fmt.Printf("\n%s and\n%s\n", t1, t2)
   overlapping = triTri2D(t1, t2, 0.0, false, true)
   fmt.Println(iff(overlapping, "overlap", "do not overlap"))

   t1 = &triangle{point{0.0, 0.0}, point{1.0, 0.0}, point{0.0, 1.0}}
   t2 = &triangle{point{1.0, 0.0}, point{2.0, 0.0}, point{1.0, 1.1}}
   fmt.Printf("\n%s and\n%s\n", t1, t2)
   println("which have only a single corner in contact, if boundary points collide")
   overlapping = triTri2D(t1, t2, 0.0, false, true)
   fmt.Println(iff(overlapping, "overlap", "do not overlap"))

   fmt.Printf("\n%s and\n%s\n", t1, t2)
   fmt.Println("which have only a single corner in contact, if boundary points do not collide")
   overlapping = triTri2D(t1, t2, 0.0, false, false)
   fmt.Println(iff(overlapping, "overlap", "do not overlap"))

}</lang>

Output:

Same as Kotlin entry.

Java

Translation of: Kotlin

Works with: Java version 8

<lang Java>import java.util.function.BiFunction;

public class TriangleOverlap {

   private static class Pair {
       double first;
       double second;

       Pair(double first, double second) {
           this.first = first;
           this.second = second;
       }

       @Override
       public String toString() {
           return String.format("(%s, %s)", first, second);
       }
   }

   private static class Triangle {
       Pair p1, p2, p3;

       Triangle(Pair p1, Pair p2, Pair p3) {
           this.p1 = p1;
           this.p2 = p2;
           this.p3 = p3;
       }

       @Override
       public String toString() {
           return String.format("Triangle: %s, %s, %s", p1, p2, p3);
       }
   }

   private static double det2D(Triangle t) {
       Pair p1 = t.p1;
       Pair p2 = t.p2;
       Pair p3 = t.p3;
       return p1.first * (p2.second - p3.second)
           + p2.first * (p3.second - p1.second)
           + p3.first * (p1.second - p2.second);
   }

   private static void checkTriWinding(Triangle t, boolean allowReversed) {
       double detTri = det2D(t);
       if (detTri < 0.0) {
           if (allowReversed) {
               Pair a = t.p3;
               t.p3 = t.p2;
               t.p2 = a;
           } else throw new RuntimeException("Triangle has wrong winding direction");
       }
   }

   private static boolean boundaryCollideChk(Triangle t, double eps) {
       return det2D(t) < eps;
   }

   private static boolean boundaryDoesntCollideChk(Triangle t, double eps) {
       return det2D(t) <= eps;
   }

   private static boolean triTri2D(Triangle t1, Triangle t2) {
       return triTri2D(t1, t2, 0.0, false, true);
   }

   private static boolean triTri2D(Triangle t1, Triangle t2, double eps, boolean allowedReversed) {
       return triTri2D(t1, t2, eps, allowedReversed, true);
   }

   private static boolean triTri2D(Triangle t1, Triangle t2, double eps, boolean allowedReversed, boolean onBoundary) {
       // Triangles must be expressed anti-clockwise
       checkTriWinding(t1, allowedReversed);
       checkTriWinding(t2, allowedReversed);
       // 'onBoundary' determines whether points on boundary are considered as colliding or not
       BiFunction<Triangle, Double, Boolean> chkEdge = onBoundary ? TriangleOverlap::boundaryCollideChk : TriangleOverlap::boundaryDoesntCollideChk;
       Pair[] lp1 = new Pair[]{t1.p1, t1.p2, t1.p3};
       Pair[] lp2 = new Pair[]{t2.p1, t2.p2, t2.p3};

       // for each edge E of t1
       for (int i = 0; i < 3; ++i) {
           int 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.apply(new Triangle(lp1[i], lp1[j], lp2[0]), eps) &&
               chkEdge.apply(new Triangle(lp1[i], lp1[j], lp2[1]), eps) &&
               chkEdge.apply(new Triangle(lp1[i], lp1[j], lp2[2]), eps)) return false;
       }

       // for each edge E of t2
       for (int i = 0; i < 3; ++i) {
           int 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.apply(new Triangle(lp2[i], lp2[j], lp1[0]), eps) &&
               chkEdge.apply(new Triangle(lp2[i], lp2[j], lp1[1]), eps) &&
               chkEdge.apply(new Triangle(lp2[i], lp2[j], lp1[2]), eps)) return false;
       }

       // The triangles overlap
       return true;
   }

   public static void main(String[] args) {
       Triangle t1 = new Triangle(new Pair(0.0, 0.0), new Pair(5.0, 0.0), new Pair(0.0, 5.0));
       Triangle t2 = new Triangle(new Pair(0.0, 0.0), new Pair(5.0, 0.0), new Pair(0.0, 6.0));
       System.out.printf("%s and\n%s\n", t1, t2);
       if (triTri2D(t1, t2)) {
           System.out.println("overlap");
       } else {
           System.out.println("do not overlap");
       }

       // need to allow reversed for this pair to avoid exception
       t1 = new Triangle(new Pair(0.0, 0.0), new Pair(0.0, 5.0), new Pair(5.0, 0.0));
       t2 = t1;
       System.out.printf("\n%s and\n%s\n", t1, t2);
       if (triTri2D(t1, t2, 0.0, true)) {
           System.out.println("overlap (reversed)");
       } else {
           System.out.println("do not overlap");
       }

       t1 = new Triangle(new Pair(0.0, 0.0), new Pair(5.0, 0.0), new Pair(0.0, 5.0));
       t2 = new Triangle(new Pair(-10.0, 0.0), new Pair(-5.0, 0.0), new Pair(-1.0, 6.0));
       System.out.printf("\n%s and\n%s\n", t1, t2);
       if (triTri2D(t1, t2)) {
           System.out.println("overlap");
       } else {
           System.out.println("do not overlap");
       }

       t1.p3 = new Pair(2.5, 5.0);
       t2 = new Triangle(new Pair(0.0, 4.0), new Pair(2.5, -1.0), new Pair(5.0, 4.0));
       System.out.printf("\n%s and\n%s\n", t1, t2);
       if (triTri2D(t1, t2)) {
           System.out.println("overlap");
       } else {
           System.out.println("do not overlap");
       }

       t1 = new Triangle(new Pair(0.0, 0.0), new Pair(1.0, 1.0), new Pair(0.0, 2.0));
       t2 = new Triangle(new Pair(2.0, 1.0), new Pair(3.0, 0.0), new Pair(3.0, 2.0));
       System.out.printf("\n%s and\n%s\n", t1, t2);
       if (triTri2D(t1, t2)) {
           System.out.println("overlap");
       } else {
           System.out.println("do not overlap");
       }

       t2 = new Triangle(new Pair(2.0, 1.0), new Pair(3.0, -2.0), new Pair(3.0, 4.0));
       System.out.printf("\n%s and\n%s\n", t1, t2);
       if (triTri2D(t1, t2)) {
           System.out.println("overlap");
       } else {
           System.out.println("do not overlap");
       }

       t1 = new Triangle(new Pair(0.0, 0.0), new Pair(1.0, 0.0), new Pair(0.0, 1.0));
       t2 = new Triangle(new Pair(1.0, 0.0), new Pair(2.0, 0.0), new Pair(1.0, 1.1));
       System.out.printf("\n%s and\n%s\n", t1, t2);
       System.out.println("which have only a single corner in contact, if boundary points collide");
       if (triTri2D(t1, t2)) {
           System.out.println("overlap");
       } else {
           System.out.println("do not overlap");
       }

       System.out.printf("\n%s and\n%s\n", t1, t2);
       System.out.println("which have only a single corner in contact, if boundary points do not collide");
       if (triTri2D(t1, t2, 0.0, false, false)) {
           System.out.println("overlap");
       } else {
           System.out.println("do not overlap");
       }
   }

}</lang>

Output:

Triangle: (0.0, 0.0), (5.0, 0.0), (0.0, 5.0) and
Triangle: (0.0, 0.0), (5.0, 0.0), (0.0, 6.0)
overlap

Triangle: (0.0, 0.0), (0.0, 5.0), (5.0, 0.0) and
Triangle: (0.0, 0.0), (0.0, 5.0), (5.0, 0.0)
overlap (reversed)

Triangle: (0.0, 0.0), (5.0, 0.0), (0.0, 5.0) and
Triangle: (-10.0, 0.0), (-5.0, 0.0), (-1.0, 6.0)
do not overlap

Triangle: (0.0, 0.0), (5.0, 0.0), (2.5, 5.0) and
Triangle: (0.0, 4.0), (2.5, -1.0), (5.0, 4.0)
overlap

Triangle: (0.0, 0.0), (1.0, 1.0), (0.0, 2.0) and
Triangle: (2.0, 1.0), (3.0, 0.0), (3.0, 2.0)
do not overlap

Triangle: (0.0, 0.0), (1.0, 1.0), (0.0, 2.0) and
Triangle: (2.0, 1.0), (3.0, -2.0), (3.0, 4.0)
do not overlap

Triangle: (0.0, 0.0), (1.0, 0.0), (0.0, 1.0) and
Triangle: (1.0, 0.0), (2.0, 0.0), (1.0, 1.1)
which have only a single corner in contact, if boundary points collide
overlap

Triangle: (0.0, 0.0), (1.0, 0.0), (0.0, 1.0) and
Triangle: (1.0, 0.0), (2.0, 0.0), (1.0, 1.1)
which have only a single corner in contact, if boundary points do not collide
do not overlap

Julia

Translation of: Python

Module: <lang julia>module Triangles

using LinearAlgebra

export AntiClockwise, Both, StrictCheck, MildCheck

abstract type Widing end struct AntiClockwise <: Widing end struct Both <: Widing end

function _check_triangle_winding(t, widing::AntiClockwise)

   trisq = fill!(Matrix{eltype(t)}(undef, 3, 3), 1)
   trisq[:, 1:2] .= t
   det(trisq) < 0 && throw(ArgumentError("triangle has wrong winding direction"))
   return trisq

end

function _check_triangle_winding(t, widing::Both)

   trisq = fill!(Matrix{eltype(t)}(undef, 3, 3), 1)
   trisq[:, 1:2] .= t
   if det(trisq) < 0
       tmp = trisq[2, :]
       trisq[2, :] .= trisq[1, :]
       trisq[1, :] .= tmp
   end
   return trisq

end

abstract type OnBoundaryCheck end struct StrictCheck <: OnBoundaryCheck end struct MildCheck <: OnBoundaryCheck end

_checkedge(::StrictCheck, x, ϵ) = det(x) < ϵ _checkedge(::MildCheck, x, ϵ) = det(x) ≤ ϵ

function overlap(T₁, T₂, onboundary::OnBoundaryCheck=MildCheck(),; ϵ=0.0, widing::Widing=AntiClockwise())

   # Trangles must be expressed anti-clockwise
   T₁ = _check_triangle_winding(T₁, widing)
   T₂ = _check_triangle_winding(T₂, widing)

   edge = similar(T₁)
   for (A, B) in ((T₁, T₂), (T₂, T₁)), i in 1:3
       circshift!(edge, A, (i, 0))
       @views if all(_checkedge(onboundary, vcat(edge[1:2, :], B[r, :]'), ϵ) for r in 1:3)
           return false
       end
   end

   return true

end

end # module Triangles</lang>

Main: <lang julia>using .Triangles

t1 = [0 0; 5 0; 0 5] t2 = [0 0; 5 0; 0 6] @show Triangles.overlap(t1, t2)

t1 = [0 0; 0 5; 5 0] t2 = [0 0; 0 6; 5 0] @show Triangles.overlap(t1, t2, widing=Both())

t1 = [0 0; 5 0; 0 5] t2 = [-10 0; -5 0; -1 6] @show Triangles.overlap(t1, t2)

t1 = [0 0; 5 0; 2.5 5] t2 = [0 4; 2.5 -1; 5 4] @show Triangles.overlap(t1, t2)

t1 = [0 0; 1 1; 0 2] t2 = [2 1; 3 0; 3 2] @show Triangles.overlap(t1, t2)

t1 = [0 0; 1 1; 0 2] t2 = [2 1; 3 -2; 3 4] @show Triangles.overlap(t1, t2)

Barely touching

t1 = [0 0; 1 0; 0 1] t2 = [1 0; 2 0; 1 1] @show Triangles.overlap(t1, t2, StrictCheck())

Barely touching

t1 = [0 0; 1 0; 0 1] t2 = [1 0; 2 0; 1 1] @show Triangles.overlap(t1, t2, MildCheck())</lang>

Output:

Triangles.overlap(t1, t2) = true
Triangles.overlap(t1, t2, widing=Both()) = true
Triangles.overlap(t1, t2) = false
Triangles.overlap(t1, t2) = true
Triangles.overlap(t1, t2) = false
Triangles.overlap(t1, t2) = false
Triangles.overlap(t1, t2, StrictCheck()) = true
Triangles.overlap(t1, t2, MildCheck()) = false

Kotlin

Translation of: C++

<lang scala>// version 1.1.0

typealias Point = Pair<Double, Double>

data class Triangle(var p1: Point, var p2: Point, var p3: Point) {

   override fun toString() = "Triangle: $p1, $p2, $p3"

}

fun det2D(t: Triangle): Double {

   val (p1, p2, p3) = t
   return  p1.first * (p2.second - p3.second) +
           p2.first * (p3.second - p1.second) +
           p3.first * (p1.second - p2.second)

}

fun checkTriWinding(t: Triangle, allowReversed: Boolean) {

   val detTri = det2D(t)
   if (detTri < 0.0) {
       if (allowReversed) {
          val a = t.p3

t.p3 = t.p2 t.p2 = a

       }
       else throw RuntimeException("Triangle has wrong winding direction")
   }

}

fun boundaryCollideChk(t: Triangle, eps: Double) = det2D(t) < eps

fun boundaryDoesntCollideChk(t: Triangle, eps: Double) = det2D(t) <= eps

fun triTri2D(t1: Triangle, t2: Triangle, eps: Double = 0.0,

            allowReversed: Boolean = false, onBoundary: Boolean = true): Boolean {
   // Triangles must be expressed anti-clockwise
   checkTriWinding(t1, allowReversed)
   checkTriWinding(t2, allowReversed)
   // 'onBoundary' determines whether points on boundary are considered as colliding or not
   val chkEdge = if (onBoundary) ::boundaryCollideChk else ::boundaryDoesntCollideChk
   val lp1 = listOf(t1.p1, t1.p2, t1.p3)
   val lp2 = listOf(t2.p1, t2.p2, t2.p3)

   // for each edge E of t1
   for (i in 0 until 3) {
       val 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
   for (i in 0 until 3) {
       val 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

}

fun main(args: Array<String>) {

   var t1 = Triangle(0.0 to 0.0, 5.0 to 0.0, 0.0 to 5.0)
   var t2 = Triangle(0.0 to 0.0, 5.0 to 0.0, 0.0 to 6.0)
   println("$t1 and\n$t2")
   println(if (triTri2D(t1, t2)) "overlap" else "do not overlap")

   // need to allow reversed for this pair to avoid exception
   t1 = Triangle(0.0 to 0.0, 0.0 to 5.0, 5.0 to 0.0)
   t2 = t1
   println("\n$t1 and\n$t2")
   println(if (triTri2D(t1, t2, 0.0, true)) "overlap (reversed)" else "do not overlap")

   t1 = Triangle(0.0 to 0.0, 5.0 to 0.0, 0.0 to 5.0)
   t2 = Triangle(-10.0 to 0.0, -5.0 to 0.0, -1.0 to 6.0)
   println("\n$t1 and\n$t2")
   println(if (triTri2D(t1, t2)) "overlap" else "do not overlap")

   t1.p3 = 2.5 to 5.0
   t2 = Triangle(0.0 to 4.0, 2.5 to -1.0, 5.0 to 4.0)
   println("\n$t1 and\n$t2")
   println(if (triTri2D(t1, t2)) "overlap" else "do not overlap")

   t1 = Triangle(0.0 to 0.0, 1.0 to 1.0, 0.0 to 2.0)
   t2 = Triangle(2.0 to 1.0, 3.0 to 0.0, 3.0 to 2.0)
   println("\n$t1 and\n$t2")
   println(if (triTri2D(t1, t2)) "overlap" else "do not overlap")

   t2 = Triangle(2.0 to 1.0, 3.0 to -2.0, 3.0 to 4.0)
   println("\n$t1 and\n$t2")
   println(if (triTri2D(t1, t2)) "overlap" else "do not overlap")

   t1 = Triangle(0.0 to 0.0, 1.0 to 0.0, 0.0 to 1.0)
   t2 = Triangle(1.0 to 0.0, 2.0 to 0.0, 1.0 to 1.1)
   println("\n$t1 and\n$t2")
   println("which have only a single corner in contact, if boundary points collide")
   println(if (triTri2D(t1, t2)) "overlap" else "do not overlap")

   println("\n$t1 and\n$t2")
   println("which have only a single corner in contact, if boundary points do not collide")
   println(if (triTri2D(t1, t2, 0.0, false, false)) "overlap" else "do not overlap")

}</lang>

Output:

Triangle: (0.0, 0.0), (5.0, 0.0), (0.0, 5.0) and
Triangle: (0.0, 0.0), (5.0, 0.0), (0.0, 6.0)
overlap

Triangle: (0.0, 0.0), (0.0, 5.0), (5.0, 0.0) and
Triangle: (0.0, 0.0), (0.0, 5.0), (5.0, 0.0)
overlap (reversed)

Triangle: (0.0, 0.0), (5.0, 0.0), (0.0, 5.0) and
Triangle: (-10.0, 0.0), (-5.0, 0.0), (-1.0, 6.0)
do not overlap

Triangle: (0.0, 0.0), (5.0, 0.0), (2.5, 5.0) and
Triangle: (0.0, 4.0), (2.5, -1.0), (5.0, 4.0)
overlap

Triangle: (0.0, 0.0), (1.0, 1.0), (0.0, 2.0) and
Triangle: (2.0, 1.0), (3.0, 0.0), (3.0, 2.0)
do not overlap

Triangle: (0.0, 0.0), (1.0, 1.0), (0.0, 2.0) and
Triangle: (2.0, 1.0), (3.0, -2.0), (3.0, 4.0)
do not overlap

Triangle: (0.0, 0.0), (1.0, 0.0), (0.0, 1.0) and
Triangle: (1.0, 0.0), (2.0, 0.0), (1.0, 1.1)
which have only a single corner in contact, if boundary points collide
overlap

Triangle: (0.0, 0.0), (1.0, 0.0), (0.0, 1.0) and
Triangle: (1.0, 0.0), (2.0, 0.0), (1.0, 1.1)
which have only a single corner in contact, if boundary points do not collide
do not overlap

Modula-2

<lang modula2>MODULE Overlap; FROM EXCEPTIONS IMPORT AllocateSource,ExceptionSource,GetMessage,RAISE; FROM LongStr IMPORT RealToFixed; FROM Terminal IMPORT WriteString,WriteLn,ReadChar;

TYPE

   Point = RECORD
       x,y : LONGREAL;
   END;
   Triangle = RECORD
       p1,p2,p3 : Point;
   END;

VAR

   TextWinExSrc : ExceptionSource;

PROCEDURE WritePoint(p : Point); VAR buf : ARRAY[0..31] OF CHAR; BEGIN

   WriteString("(");
   RealToFixed(p.x, 2, buf);
   WriteString(buf);
   WriteString(", ");
   RealToFixed(p.y, 2, buf);
   WriteString(buf);
   WriteString(")")

END WritePoint;

PROCEDURE WriteTriangle(t : Triangle); BEGIN

   WriteString("Triangle: ");
   WritePoint(t.p1);
   WriteString(", ");
   WritePoint(t.p2);
   WriteString(", ");
   WritePoint(t.p3)

END WriteTriangle;

PROCEDURE Det2D(p1,p2,p3 : Point) : LONGREAL; BEGIN

   RETURN p1.x * (p2.y - p3.y)
        + p2.x * (p3.y - p1.y)
        + p3.x * (p1.y - p2.y)

END Det2D;

PROCEDURE CheckTriWinding(VAR p1,p2,p3 : Point; allowReversed : BOOLEAN); VAR

   detTri : LONGREAL;
   t : Point;

BEGIN

   detTri := Det2D(p1, p2, p3);
   IF detTri < 0.0 THEN
       IF allowReversed THEN
           t := p3;
           p3 := p2;
           p2 := t
       ELSE
           RAISE(TextWinExSrc, 0, "triangle has wrong winding direction")
       END
   END

END CheckTriWinding;

PROCEDURE BoundaryCollideChk(p1,p2,p3 : Point; eps : LONGREAL) : BOOLEAN; BEGIN

   RETURN Det2D(p1, p2, p3) < eps

END BoundaryCollideChk;

PROCEDURE BoundaryDoesntCollideChk(p1,p2,p3 : Point; eps : LONGREAL) : BOOLEAN; BEGIN

   RETURN Det2D(p1, p2, p3) <= eps

END BoundaryDoesntCollideChk;

PROCEDURE TriTri2D(t1,t2 : Triangle; eps : LONGREAL; allowReversed,onBoundary : BOOLEAN) : BOOLEAN; TYPE

   Points = ARRAY[0..2] OF Point;

VAR

   chkEdge : PROCEDURE(Point, Point, Point, LONGREAL) : BOOLEAN;
   lp1,lp2 : Points;
   i,j : CARDINAL;

BEGIN

   (* Triangles must be expressed anti-clockwise *)
   CheckTriWinding(t1.p1, t1.p2, t1.p3, allowReversed);
   CheckTriWinding(t2.p1, t2.p2, t2.p3, allowReversed);

   (* 'onBoundary' determines whether points on boundary are considered as colliding or not *)
   IF onBoundary THEN
       chkEdge := BoundaryCollideChk
   ELSE
       chkEdge := BoundaryDoesntCollideChk
   END;

   lp1 := Points{t1.p1, t1.p2, t1.p3};
   lp2 := Points{t2.p1, t2.p2, t2.p3};

   (* for each edge E of t1 *)
   FOR i:=0 TO 2 DO
       j := (i + 1) MOD 3;
       (* Check all points of t2 lay on the external side of edge E.
          If they do, the triangles do not overlap. *)
       IF     chkEdge(lp1[i], lp1[j], lp2[0], eps)
          AND chkEdge(lp1[i], lp1[j], lp2[1], eps)
          AND chkEdge(lp1[i], lp1[j], lp2[2], eps)
       THEN
           RETURN FALSE
       END
   END;

   (* for each edge E of t2 *)
   FOR i:=0 TO 2 DO
       j := (i + 1) MOD 3;
       (* Check all points of t1 lay on the external side of edge E.
          If they do, the triangles do not overlap. *)
       IF     chkEdge(lp2[i], lp2[j], lp1[0], eps)
          AND chkEdge(lp2[i], lp2[j], lp1[1], eps)
          AND chkEdge(lp2[i], lp2[j], lp1[2], eps)
       THEN
           RETURN FALSE
       END
   END;

   (* The triangles overlap *)
   RETURN TRUE

END TriTri2D;

PROCEDURE CheckOverlap(t1,t2 : Triangle; eps : LONGREAL; allowReversed,onBoundary : BOOLEAN); BEGIN

   WriteTriangle(t1);
   WriteString(" and");
   WriteLn;
   WriteTriangle(t2);
   WriteLn;

   IF TriTri2D(t1, t2, eps, allowReversed, onBoundary) THEN
       WriteString("overlap")
   ELSE
       WriteString("do not overlap")
   END;
   WriteLn

END CheckOverlap;

(* main *) VAR

   t1,t2 : Triangle;

BEGIN

   t1 := Triangle{{0.0,0.0},{5.0,0.0},{0.0,5.0}};
   t2 := Triangle{{0.0,0.0},{5.0,0.0},{0.0,6.0}};
   CheckOverlap(t1, t2, 0.0, FALSE, TRUE);
   WriteLn;

   t1 := Triangle{{0.0,0.0},{0.0,5.0},{5.0,0.0}};
   t2 := Triangle{{0.0,0.0},{0.0,5.0},{5.0,0.0}};
   CheckOverlap(t1, t2, 0.0, TRUE, TRUE);
   WriteLn;

   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}};
   CheckOverlap(t1, t2, 0.0, FALSE, TRUE);
   WriteLn;

   t1 := Triangle{{0.0,0.0},{5.0,0.0},{2.5,5.0}};
   t2 := Triangle{{0.0,4.0},{2.5,-1.0},{5.0,4.0}};
   CheckOverlap(t1, t2, 0.0, FALSE, TRUE);
   WriteLn;

   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}};
   CheckOverlap(t1, t2, 0.0, FALSE, TRUE);
   WriteLn;

   t1 := Triangle{{0.0,0.0},{1.0,1.0},{0.0,2.0}};
   t2 := Triangle{{2.0,1.0},{3.0,-2.0},{3.0,4.0}};
   CheckOverlap(t1, t2, 0.0, FALSE, TRUE);
   WriteLn;

   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}};
   CheckOverlap(t1, t2, 0.0, FALSE, TRUE);
   WriteLn;

   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}};
   CheckOverlap(t1, t2, 0.0, FALSE, FALSE);
   WriteLn;

   ReadChar

END Overlap.</lang>

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:

0 0 4 0 0 4 1 1 2 1 1 2
Triangle: ABC:  (0,0) (4,0) (0,4)
Triangle: DEF:  (1,1) (2,1) (1,2)
 (1,1) (2,1) (1,2) is fully contained in  (0,0) (4,0) (0,4)

2 1 1 2 1 1 4 0 0 4 0 0
Triangle: ABC:  (2,1) (1,2) (1,1)
Triangle: DEF:  (4,0) (0,4) (0,0)
 (2,1) (1,2) (1,1) is fully contained in  (4,0) (0,4) (0,0)

1 2 2 1 1 1 0 4 4 0 0 0
Triangle: ABC:  (1,2) (2,1) (1,1)
Triangle: DEF:  (0,4) (4,0) (0,0)
 (1,2) (2,1) (1,1) is fully contained in  (0,4) (4,0) (0,0)

0 0 0 4 4 0 1 1 1 2 2 1
Triangle: ABC:  (0,0) (0,4) (4,0)
Triangle: DEF:  (1,1) (1,2) (2,1)
 (1,1) (1,2) (2,1) is fully contained in  (0,0) (0,4) (4,0)

1 1 1 2 2 1 0 0 0 4 4 0
Triangle: ABC:  (1,1) (1,2) (2,1)
Triangle: DEF:  (0,0) (0,4) (4,0)
 (1,1) (1,2) (2,1) is fully contained in  (0,0) (0,4) (4,0)

0 0 0 4 4 0 1 1 1 2 2 1
Triangle: ABC:  (0,0) (0,4) (4,0)
Triangle: DEF:  (1,1) (1,2) (2,1)
 (1,1) (1,2) (2,1) is fully contained in  (0,0) (0,4) (4,0)

0 0 0 6 8 3 8 0 8 8 0 3
Triangle: ABC:  (0,0) (0,6) (8,3)
Triangle: DEF:  (8,0) (8,8) (0,3)
Corner(s) that touch the other triangle:  (0,3) (8,3)
Triangles overlap and touch on  (0,3) (8,3)
3 0 8 8 0 8 3 8 6 0 0 0
Triangle: ABC:  (3,0) (8,8) (0,8)
Triangle: DEF:  (3,8) (6,0) (0,0)
Corner(s) that touch the other triangle:  (3,8) (3,0)
Triangles overlap and touch on  (3,8) (3,0)
0 3 8 8 8 0 8 3 0 6 0 0
Triangle: ABC:  (0,3) (8,8) (8,0)
Triangle: DEF:  (8,3) (0,6) (0,0)
Corner(s) that touch the other triangle:  (8,3) (0,3)
Triangles overlap and touch on  (8,3) (0,3)
0 0 6 0 3 8 0 8 8 8 3 0
Triangle: ABC:  (0,0) (6,0) (3,8)
Triangle: DEF:  (0,8) (8,8) (3,0)
Corner(s) that touch the other triangle:  (3,0) (3,8)
Triangles overlap and touch on  (3,0) (3,8)
0 8 8 8 3 0 0 0 6 0 3 8
Triangle: ABC:  (0,8) (8,8) (3,0)
Triangle: DEF:  (0,0) (6,0) (3,8)
Corner(s) that touch the other triangle:  (3,8) (3,0)
Triangles overlap and touch on  (3,8) (3,0)
0 0 6 0 3 8 0 8 8 8 3 0
Triangle: ABC:  (0,0) (6,0) (3,8)
Triangle: DEF:  (0,8) (8,8) (3,0)
Corner(s) that touch the other triangle:  (3,0) (3,8)
Triangles overlap and touch on  (3,0) (3,8)
0 0 0 2 2 0 0 0 4 0 0 6
Triangle: ABC:  (0,0) (0,2) (2,0)
Triangle: DEF:  (0,0) (4,0) (0,6)
Corner(s) that touch the other triangle:  (0,0) (0,2) (2,0)
Triangles overlap and touch on  (0,0) (0,2) (2,0)

6 0 0 4 0 0 0 2 2 0 0 0
Triangle: ABC:  (6,0) (0,4) (0,0)
Triangle: DEF:  (0,2) (2,0) (0,0)
Corner(s) that touch the other triangle:  (0,2) (2,0) (0,0)
Triangles overlap and touch on  (0,2) (2,0) (0,0)

0 6 4 0 0 0 2 0 0 2 0 0
Triangle: ABC:  (0,6) (4,0) (0,0)
Triangle: DEF:  (2,0) (0,2) (0,0)
Corner(s) that touch the other triangle:  (2,0) (0,2) (0,0)
Triangles overlap and touch on  (2,0) (0,2) (0,0)

0 0 2 0 0 2 0 0 0 4 6 0
Triangle: ABC:  (0,0) (2,0) (0,2)
Triangle: DEF:  (0,0) (0,4) (6,0)
Corner(s) that touch the other triangle:  (0,0) (2,0) (0,2)
Triangles overlap and touch on  (0,0) (2,0) (0,2)

0 0 0 4 6 0 0 0 2 0 0 2
Triangle: ABC:  (0,0) (0,4) (6,0)
Triangle: DEF:  (0,0) (2,0) (0,2)
Corner(s) that touch the other triangle:  (0,0) (2,0) (0,2)
Triangles overlap and touch on  (0,0) (2,0) (0,2)

0 0 2 0 0 2 0 0 0 4 6 0
Triangle: ABC:  (0,0) (2,0) (0,2)
Triangle: DEF:  (0,0) (0,4) (6,0)
Corner(s) that touch the other triangle:  (0,0) (2,0) (0,2)
Triangles overlap and touch on  (0,0) (2,0) (0,2)

0 0 5 0 0 5 0 0 5 0 0 6
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)

6 0 0 5 0 0 5 0 0 5 0 0
Triangle: ABC:  (6,0) (0,5) (0,0)
Triangle: DEF:  (5,0) (0,5) (0,0)
Corner(s) that touch the other triangle:  (5,0) (0,5) (0,0)
Triangles have an edge in common:  (0,5) (0,0)

0 6 5 0 0 0 0 5 5 0 0 0
Triangle: ABC:  (0,6) (5,0) (0,0)
Triangle: DEF:  (0,5) (5,0) (0,0)
Corner(s) that touch the other triangle:  (0,5) (5,0) (0,0)
Triangles have an edge in common:  (5,0) (0,0)

0 0 0 5 5 0 0 0 0 5 6 0
Triangle: ABC:  (0,0) (0,5) (5,0)
Triangle: DEF:  (0,0) (0,5) (6,0)
Corner(s) that touch the other triangle:  (0,0) (0,5) (5,0)
Triangles have an edge in common:  (0,0) (0,5)

0 0 0 5 6 0 0 0 0 5 5 0
Triangle: ABC:  (0,0) (0,5) (6,0)
Triangle: DEF:  (0,0) (0,5) (5,0)
Corner(s) that touch the other triangle:  (0,0) (0,5) (5,0)
Triangles have an edge in common:  (0,0) (0,5)

0 0 0 5 5 0 0 0 0 5 6 0
Triangle: ABC:  (0,0) (0,5) (5,0)
Triangle: DEF:  (0,0) (0,5) (6,0)
Corner(s) that touch the other triangle:  (0,0) (0,5) (5,0)
Triangles have an edge in common:  (0,0) (0,5)

0 0 0 5 5 0 0 0 0 5 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

0 5 5 0 0 0 0 5 5 0 0 0
Triangle: ABC:  (0,5) (5,0) (0,0)
Triangle: DEF:  (0,5) (5,0) (0,0)
Corner(s) that touch the other triangle:  (0,5) (5,0) (0,0)
Triangles are identical

5 0 0 5 0 0 5 0 0 5 0 0
Triangle: ABC:  (5,0) (0,5) (0,0)
Triangle: DEF:  (5,0) (0,5) (0,0)
Corner(s) that touch the other triangle:  (5,0) (0,5) (0,0)
Triangles are identical

0 0 5 0 0 5 0 0 5 0 0 5
Triangle: ABC:  (0,0) (5,0) (0,5)
Triangle: DEF:  (0,0) (5,0) (0,5)
Corner(s) that touch the other triangle:  (0,0) (5,0) (0,5)
Triangles are identical

0 0 5 0 0 5 0 0 5 0 0 5
Triangle: ABC:  (0,0) (5,0) (0,5)
Triangle: DEF:  (0,0) (5,0) (0,5)
Corner(s) that touch the other triangle:  (0,0) (5,0) (0,5)
Triangles are identical

0 0 5 0 0 5 0 0 5 0 0 5
Triangle: ABC:  (0,0) (5,0) (0,5)
Triangle: DEF:  (0,0) (5,0) (0,5)
Corner(s) that touch the other triangle:  (0,0) (5,0) (0,5)
Triangles are identical

0 0 5 0 0 5 -10 0 -5 0 -1 6
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

6 -1 0 -5 0 -10 5 0 0 5 0 0
Triangle: ABC:  (6,-1) (0,-5) (0,-10)
Triangle: DEF:  (5,0) (0,5) (0,0)
 (6,-1) (0,-5) (0,-10) and  (5,0) (0,5) (0,0) don't overlap

-1 6 -5 0 -10 0 0 5 5 0 0 0
Triangle: ABC:  (-1,6) (-5,0) (-10,0)
Triangle: DEF:  (0,5) (5,0) (0,0)
 (-1,6) (-5,0) (-10,0) and  (0,5) (5,0) (0,0) don't overlap

0 0 0 5 5 0 0 -10 0 -5 6 -1
Triangle: ABC:  (0,0) (0,5) (5,0)
Triangle: DEF:  (0,-10) (0,-5) (6,-1)
 (0,0) (0,5) (5,0) and  (0,-10) (0,-5) (6,-1) don't overlap

0 -10 0 -5 6 -1 0 0 0 5 5 0
Triangle: ABC:  (0,-10) (0,-5) (6,-1)
Triangle: DEF:  (0,0) (0,5) (5,0)
 (0,-10) (0,-5) (6,-1) and  (0,0) (0,5) (5,0) don't overlap

0 0 0 5 5 0 0 -10 0 -5 6 -1
Triangle: ABC:  (0,0) (0,5) (5,0)
Triangle: DEF:  (0,-10) (0,-5) (6,-1)
 (0,0) (0,5) (5,0) and  (0,-10) (0,-5) (6,-1) don't overlap

0 0 5 0 2.5 5 0 4 2.5 -1 5 4
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

4 5 -1 2.5 4 0 5 2.5 0 5 0 0
Triangle: ABC:  (4,5) (-1,2.5) (4,0)
Triangle: DEF:  (5,2.5) (0,5) (0,0)
 (4,5) (-1,2.5) (4,0) and  (5,2.5) (0,5) (0,0) overlap

5 4 2.5 -1 0 4 2.5 5 5 0 0 0
Triangle: ABC:  (5,4) (2.5,-1) (0,4)
Triangle: DEF:  (2.5,5) (5,0) (0,0)
 (5,4) (2.5,-1) (0,4) and  (2.5,5) (5,0) (0,0) overlap

0 0 0 5 5 2.5 4 0 -1 2.5 4 5
Triangle: ABC:  (0,0) (0,5) (5,2.5)
Triangle: DEF:  (4,0) (-1,2.5) (4,5)
 (0,0) (0,5) (5,2.5) and  (4,0) (-1,2.5) (4,5) overlap

4 0 -1 2.5 4 5 0 0 0 5 5 2.5
Triangle: ABC:  (4,0) (-1,2.5) (4,5)
Triangle: DEF:  (0,0) (0,5) (5,2.5)
 (4,0) (-1,2.5) (4,5) and  (0,0) (0,5) (5,2.5) overlap

0 0 0 5 5 2.5 4 0 -1 2.5 4 5
Triangle: ABC:  (0,0) (0,5) (5,2.5)
Triangle: DEF:  (4,0) (-1,2.5) (4,5)
 (0,0) (0,5) (5,2.5) and  (4,0) (-1,2.5) (4,5) overlap

0 0 1 1 0 2 2 1 3 0 3 2
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

2 3 0 3 1 2 2 0 1 1 0 0
Triangle: ABC:  (2,3) (0,3) (1,2)
Triangle: DEF:  (2,0) (1,1) (0,0)
 (2,3) (0,3) (1,2) and  (2,0) (1,1) (0,0) don't overlap

3 2 3 0 2 1 0 2 1 1 0 0
Triangle: ABC:  (3,2) (3,0) (2,1)
Triangle: DEF:  (0,2) (1,1) (0,0)
 (3,2) (3,0) (2,1) and  (0,2) (1,1) (0,0) don't overlap

0 0 1 1 2 0 1 2 0 3 2 3
Triangle: ABC:  (0,0) (1,1) (2,0)
Triangle: DEF:  (1,2) (0,3) (2,3)
 (0,0) (1,1) (2,0) and  (1,2) (0,3) (2,3) don't overlap

1 2 0 3 2 3 0 0 1 1 2 0
Triangle: ABC:  (1,2) (0,3) (2,3)
Triangle: DEF:  (0,0) (1,1) (2,0)
 (1,2) (0,3) (2,3) and  (0,0) (1,1) (2,0) don't overlap

0 0 1 1 2 0 1 2 0 3 2 3
Triangle: ABC:  (0,0) (1,1) (2,0)
Triangle: DEF:  (1,2) (0,3) (2,3)
 (0,0) (1,1) (2,0) and  (1,2) (0,3) (2,3) don't overlap

0 0 1 1 0 2 2 1 3 -2 3 4
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

4 3 -2 3 1 2 2 0 1 1 0 0
Triangle: ABC:  (4,3) (-2,3) (1,2)
Triangle: DEF:  (2,0) (1,1) (0,0)
 (4,3) (-2,3) (1,2) and  (2,0) (1,1) (0,0) don't overlap

3 4 3 -2 2 1 0 2 1 1 0 0
Triangle: ABC:  (3,4) (3,-2) (2,1)
Triangle: DEF:  (0,2) (1,1) (0,0)
 (3,4) (3,-2) (2,1) and  (0,2) (1,1) (0,0) don't overlap

0 0 1 1 2 0 1 2 -2 3 4 3
Triangle: ABC:  (0,0) (1,1) (2,0)
Triangle: DEF:  (1,2) (-2,3) (4,3)
 (0,0) (1,1) (2,0) and  (1,2) (-2,3) (4,3) don't overlap

1 2 -2 3 4 3 0 0 1 1 2 0
Triangle: ABC:  (1,2) (-2,3) (4,3)
Triangle: DEF:  (0,0) (1,1) (2,0)
 (1,2) (-2,3) (4,3) and  (0,0) (1,1) (2,0) don't overlap

0 0 1 1 2 0 1 2 -2 3 4 3
Triangle: ABC:  (0,0) (1,1) (2,0)
Triangle: DEF:  (1,2) (-2,3) (4,3)
 (0,0) (1,1) (2,0) and  (1,2) (-2,3) (4,3) don't overlap

0 0 1 0 0 1 1 0 2 0 1 1
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)

1 1 0 2 0 1 1 0 0 1 0 0
Triangle: ABC:  (1,1) (0,2) (0,1)
Triangle: DEF:  (1,0) (0,1) (0,0)
Corner(s) that touch the other triangle:  (0,1)
Triangles touch on  (0,1)
  we analyze further
 (1,1) (0,2) (0,1) and  (1,0) (0,1) (0,0) don't overlap but touch on  (0,1)

1 1 2 0 1 0 0 1 1 0 0 0
Triangle: ABC:  (1,1) (2,0) (1,0)
Triangle: DEF:  (0,1) (1,0) (0,0)
Corner(s) that touch the other triangle:  (1,0)
Triangles touch on  (1,0)
  we analyze further
 (1,1) (2,0) (1,0) and  (0,1) (1,0) (0,0) overlap and touch on  (1,0)

0 0 0 1 1 0 0 1 0 2 1 1
Triangle: ABC:  (0,0) (0,1) (1,0)
Triangle: DEF:  (0,1) (0,2) (1,1)
Corner(s) that touch the other triangle:  (0,1)
Triangles touch on  (0,1)
  we analyze further
 (0,0) (0,1) (1,0) and  (0,1) (0,2) (1,1) don't overlap but touch on  (0,1)

0 1 0 2 1 1 0 0 0 1 1 0
Triangle: ABC:  (0,1) (0,2) (1,1)
Triangle: DEF:  (0,0) (0,1) (1,0)
Corner(s) that touch the other triangle:  (0,1)
Triangles touch on  (0,1)
  we analyze further
 (0,1) (0,2) (1,1) and  (0,0) (0,1) (1,0) don't overlap but touch on  (0,1)

0 0 0 1 1 0 0 1 0 2 1 1
Triangle: ABC:  (0,0) (0,1) (1,0)
Triangle: DEF:  (0,1) (0,2) (1,1)
Corner(s) that touch the other triangle:  (0,1)
Triangles touch on  (0,1)
  we analyze further
 (0,0) (0,1) (1,0) and  (0,1) (0,2) (1,1) don't overlap but touch on  (0,1)

Phix

Translation of: zkl

Plus draw all eight pairs of triangles for visual confirmation. <lang Phix>include pGUI.e

Ihandle dlg, canvas cdCanvas cddbuffer, cdcanvas

constant triangles = {{{{0,0},{5,0},{0,5}},{{0,0},{5,0},{0,6}}},

                     {{{0,0},{0,5},{5,0}},{{0,0},{0,5},{5,0}}},
                     {{{0,0},{5,0},{0,5}},{{-10,0},{-5,0},{-1,6}}},
                     {{{0,0},{5,0},{2.5,5}},{{0,4},{2.5,-1},{5,4}}},
                     {{{0,0},{1,1},{0,2}},{{2,1},{3,0},{3,2}}},
                     {{{0,0},{1,1},{0,2}},{{2,1},{3,-2},{3,4}}},
                     {{{0,0},{1,0},{0,1}},{{1,0},{2,0},{1,1}}},
                     {{{0,0},{1,0},{0,1}},{{1,0},{2,0},{1,1}}}}

procedure draw_triangle(sequence t, integer cx,cy, c)

   cdCanvasSetForeground(cddbuffer, c)
   cdCanvasBegin(cddbuffer,CD_CLOSED_LINES)
   for c=1 to 3 do
       atom {x,y} = t[c]
       cdCanvasVertex(cddbuffer, cx+x*10, cy+y*10)
   end for
   cdCanvasEnd(cddbuffer)

end procedure

function det2D(sequence triangle)

  atom {{p1x,p1y},{p2x,p2y},{p3x,p3y}} := triangle
  return p1x*(p2y-p3y) + p2x*(p3y-p1y) + p3x*(p1y-p2y)

end function

bool bReversed function checkWinding(sequence triangle, bool allowReversed)

   atom detTri := det2D(triangle);
   if detTri<0.0 then
       if allowReversed then
           bReversed = true
           triangle = extract(triangle,{1,3,2})
       else
           throw("triangle has wrong winding direction")
       end if
   end if
   return triangle

end function

function overlap(sequence t1, t2, atom epsilon=0.0, bool allowReversed=false, onBoundary=true)

   -- Trangles must be expressed anti-clockwise
   bReversed = false
   t1 = checkWinding(t1, allowReversed)
   t2 = checkWinding(t2, allowReversed)

   for t=1 to 2 do                     -- check t1 then t2
       for edge=1 to 3 do              -- check each edge
           sequence p1 = t1[edge],
                    p2 = t1[mod(edge,3)+1]
           -- Check all points of trangle 2 lay on the external side 
           -- of the edge E. If they do, the triangles do not collide.
           integer onside = 0
           for k=1 to 3 do
               integer c = compare(det2D({p1,p2,t2[k]}),epsilon)
               if onBoundary then
                   if not (c<0) then exit end if
               else
                   if not (c<=0) then exit end if
               end if

-- -- (the following incomprehensible one-liner is equivalent:) -- if compare(det2D({p1,p2,t2[k]}),epsilon)>-onBoundary then exit end if

               onside += 1
           end for
           if onside=3 then
               return iff(onBoundary?"no overlap":"no overlap (no boundary)")
           end if
       end for
       {t2,t1} = {t1,t2}           -- flip and re-test
   end for
   return iff(bReversed?"overlap (reversed)":"overlap")

end function

function redraw_cb(Ihandle /*ih*/, integer /*posx*/, integer /*posy*/)

   cdCanvasActivate(cddbuffer)
   integer cy = 200, cx = 100
   for i=1 to length(triangles) do
       sequence {t1,t2} = triangles[i]
       draw_triangle(t1,cx,cy,CD_RED)
       integer s = (i<=2)  -- (smudge tests[1..2] by one 
                           --  pixel to show them better)
       draw_triangle(t2,cx+s,cy+s,CD_BLUE)
       cdCanvasSetForeground(cddbuffer, CD_BLACK)
       cdCanvasText(cddbuffer,cx+10,cy-40,overlap(t1,t2,0,i=2,i!=8))
       if i=4 then
           cy = 100
           cx = 100
       else
           cx += 300
       end if
   end for
   cdCanvasFlush(cddbuffer)
   return IUP_DEFAULT

end function

function map_cb(Ihandle ih)

   cdcanvas = cdCreateCanvas(CD_IUP, ih)
   cddbuffer = cdCreateCanvas(CD_DBUFFER, cdcanvas)
   cdCanvasSetBackground(cddbuffer, CD_WHITE)
   return IUP_DEFAULT

end function

procedure main()

   IupOpen()
   
   canvas = IupCanvas(NULL)
   IupSetAttribute(canvas, "RASTERSIZE", "1250x300")
   IupSetCallback(canvas, "MAP_CB", Icallback("map_cb"))

   dlg = IupDialog(canvas,"DIALOGFRAME=YES")
   IupSetAttribute(dlg, "TITLE", "Triangle overlap")
   IupSetCallback(canvas, "ACTION", Icallback("redraw_cb"))
   IupCloseOnEscape(dlg)

   IupMap(dlg)
   IupSetAttribute(canvas, "RASTERSIZE", NULL)
   IupShowXY(dlg,IUP_CENTER,IUP_CENTER)
   IupMainLoop()
   IupClose()

end procedure

main()</lang>

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 ?

QB64

<lang QB64> DATA 0,0,5,0,0,5,0,0,5,0,0,6 DATA 0,0,0,5,5,0,0,0,0,5,5,0 DATA 0,0,5,0,0,5,-10,0,-5,0,-1,6 DATA 0,0,5,0,2.5,5,0,4,2.5,-1,5,4 DATA 0,0,1,1,0,2,2,1,3,0,3,2 DATA 0,0,1,1,0,2,2,1,3,-2,3,4

TYPE point

   x AS INTEGER
   y AS INTEGER

END TYPE

DIM coord(12, 3) AS point

workscreen = _NEWIMAGE(800, 800, 32) backscreen = _NEWIMAGE(800, 800, 32)

SCREEN workscreen FOR i = 1 TO 12 '12 triangles

   FOR j = 1 TO 3 'with 3 coordinates for each
       READ coord(i, j).x 'X coord
       READ coord(i, j).y 'Y coord
       FixCoord coord(i, j)
   NEXT

NEXT _DELAY .5 _SCREENMOVE _MIDDLE

FOR i = 1 TO 12

   _DEST workscreen
   CLS
   _DEST backscreen
   _DONTBLEND
   CLS , 0
   PSET (coord(i, 1).x, coord(i, 1).y), _RGBA32(255, 255, 255, 128)
   FOR j = 2 TO 3
       LINE -(coord(i, j).x, coord(i, j).y), _RGBA32(255, 255, 255, 128)
   NEXT
   LINE -(coord(i, 1).x, coord(i, 1).y), _RGBA32(255, 255, 255, 128)
   xinside = (coord(i, 1).x + coord(i, 2).x + coord(i, 3).x) / 3
   yinside = (coord(i, 1).y + coord(i, 2).y + coord(i, 3).y) / 3
   PAINT (xinside, yinside), _RGBA32(255, 255, 255, 128)
   _BLEND
   _PUTIMAGE , backscreen, 0
   CLS , 0
   _DONTBLEND
   i = i + 1
   PSET (coord(i, 1).x, coord(i, 1).y), _RGBA32(255, 0, 0, 128)
   FOR j = 2 TO 3
       LINE -(coord(i, j).x, coord(i, j).y), _RGBA32(255, 0, 0, 128)
   NEXT
   LINE -(coord(i, 1).x, coord(i, 1).y), _RGBA32(255, 0, 0, 128)
   xinside = (coord(i, 1).x + coord(i, 2).x + coord(i, 3).x) / 3
   yinside = (coord(i, 1).y + coord(i, 2).y + coord(i, 3).y) / 3
   PAINT (xinside, yinside), _RGBA32(255, 0, 0, 128)
   _BLEND
   _PUTIMAGE , backscreen, 0
   _DEST workscreen
   _SOURCE workscreen
   overlap = 0
   FOR x = 0 TO 999
       FOR y = 0 TO 999
           IF POINT(x, y) = _RGBA32(190, 63, 63, 255) THEN overlap = -1: GOTO overlap
       NEXT
   NEXT
   overlap:
   IF overlap THEN PRINT "OVERLAP" ELSE PRINT "NO OVERLAP"
   SLEEP

NEXT SYSTEM

SUB FixCoord (p AS point)

   p.x = (10 + p.x) * 30 + 100
   p.y = (10 + p.y) * 30

END SUB </lang>

Racket

Translation of: Zkl

<lang racket>#lang racket

A triangle is a list of three pairs of points

'((x . y) (x . y) (x . y))

(define (to-tri x1 y1 x2 y2 x3 y3) `((,x1 . ,y1) (,x2 . ,y2) (,x3 . ,y3)))

(define det-2D

 (match-lambda
   [`((,x1 . ,y1) (,x2 . ,y2) (,x3 . ,y3)) (+ (* x1 (- y2 y3)) (* x2 (- y3 y1)) (* x3 (- y1 y2)))]))

(define (assert-triangle-winding triangle allow-reversed?)

 (cond
   [(>= (det-2D triangle) 0) triangle]
   [allow-reversed? (match triangle [(list p1 p2 p3) (list p1 p3 p2)])]
   [else (error 'assert-triangle-winding "triangle is wound in wrong direction")]))

(define (tri-tri-2d? triangle1 triangle2

                    #:ϵ (ϵ 0)
                    #:allow-reversed? (allow-reversed? #f)
                    #:on-boundary? (on-boundary? #t))
 (define check-edge
   (if on-boundary? ; Points on the boundary are considered as colliding
       (λ (triangle) (< (det-2D triangle) ϵ))
       (λ (triangle) (<= (det-2D triangle) ϵ))))
 
 (define (inr t1 t2)
   (for*/and ((i (in-range 3)))
     ;; Check all points of trangle 2 lay on the external side 
     ;; of the edge E. If they do, the triangles do not collide.
     (define t1.i (list-ref t1 i))
     (define t1.j (list-ref t1 (modulo (add1 i) 3)))
     (not (for/and ((k (in-range 3))) (check-edge (list (list-ref t2 k) t1.i t1.j))))))
 
 (let (;; Trangles must be expressed anti-clockwise
       (tri1 (assert-triangle-winding triangle1 allow-reversed?))
       (tri2 (assert-triangle-winding triangle2 allow-reversed?)))
   (and (inr tri1 tri2) (inr tri2 tri1))))

---------------------------------------------------------------------------------------------------

(module+ test

 (require rackunit)
 
 (define triangleses ; pairs of triangles
   (for/list ((a.b (in-list '(((0 0  5 0  0   5) (  0 0   5    0   0 6))
                              ((0 0  0 5  5   0) (  0 0   0    5   5 0))
                              ((0 0  5 0  0   5) (-10 0  -5    0  -1 6))
                              ((0 0  5 0  2.5 5) (  0 4   2.5 -1   5 4))
                              ((0 0  1 1  0   2) (  2 1   3    0   3 2))
                              ((0 0  1 1  0   2) (  2 1   3   -2   3 4))))))
     (map (curry apply to-tri) a.b)))

 (check-equal?
  (for/list ((t1.t2 (in-list triangleses)))
    (define t1 (first t1.t2))
    (define t2 (second t1.t2))
    (define-values (r reversed?)
      (with-handlers ([exn:fail? (λ (_) (values (tri-tri-2d? t1 t2 #:allow-reversed? #t) #t))])
        (values (tri-tri-2d? t1 t2) #f)))
    (cons r reversed?))
  '((#t . #f) (#t . #t) (#f . #f) (#t . #f) (#f . #f) (#f . #f)))

 (let ((c1 (to-tri 0 0  1 0  0 1)) (c2 (to-tri 1 0  2 0  1 1)))
   (check-true (tri-tri-2d? c1 c2 #:on-boundary? #t))
   (check-false (tri-tri-2d? c1 c2 #:on-boundary? #f))))

</lang>

No output → all tests passed

REXX

Note: The triangles must be real triangles (no edge of length 0) <lang rexx>/* 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

Translation of: C++

<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