[[Category:Geometry]] [[Category:Collision detection]] {{draft task}}

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)

Ada

WITH Ada.Text_IO; USE Ada.Text_IO;

PROCEDURE Main IS
   TYPE Vertex IS MOD 3;
   TYPE Point IS ARRAY (0 .. 1) OF Float;
   TYPE Triangle IS ARRAY (Vertex) OF Point;
   TYPE Triangle_Vertices IS ARRAY (0 .. 5) OF Float;

   FUNCTION Same_Side (A, B, M, N : Point) RETURN Boolean IS
      FUNCTION Aff (U : Point) RETURN Float IS
        ((B (1) - A (1)) * (U (0) - A (0)) + (A (0) - B (0)) * (U (1) - A (1)));
   BEGIN
      RETURN Aff (M) * Aff (N) >= 0.0;
   END Same_Side;

   FUNCTION In_Side (T1 , T2 : Triangle) RETURN Boolean IS
     (FOR ALL V IN Vertex  =>
        (FOR Some P OF T2 => Same_Side (T1 (V + 1), T1 (V + 2), T1 (V), P)));

   FUNCTION Overlap (T1, T2 : Triangle) RETURN Boolean IS
     (In_Side (T1, T2) AND THEN  In_Side (T2, T1));

   FUNCTION "+" (T : Triangle_Vertices) RETURN Triangle IS
     ((T (0), T (1)), (T (2), T (3)), (T (4), T (5)));

   PROCEDURE Put (T1, T2 : Triangle_Vertices) IS
   BEGIN
      Put_Line (Overlap (+T1, +T2)'Img);
   END Put;

BEGIN
   Put ((0.0, 0.0, 5.0, 0.0, 0.0, 5.0), (0.0, 0.0, 5.0, 0.0, 0.0, 6.0));
   Put ((0.0, 0.0, 0.0, 5.0, 5.0, 0.0), (0.0, 0.0, 0.0, 5.0, 5.0, 0.0));
   Put ((0.0, 0.0, 5.0, 0.0, 0.0, 5.0), (-10.0, 0.0, -5.0, 0.0, -1.0, 6.0));
   Put ((0.0, 0.0, 5.0, 0.0, 2.5, 5.0), (0.0, 4.0, 2.5, -1.0, 5.0, 4.0));
   Put ((0.0, 0.0, 1.0, 1.0, 0.0, 2.0), (2.0, 1.0, 3.0, 0.0, 3.0, 2.0));
   Put ((0.0, 0.0, 1.0, 1.0, 0.0, 2.0), (2.0, 1.0, 3.0, -2.0, 3.0, 4.0));
   Put ((0.0, 0.0, 1.0, 0.0, 0.0, 1.0), (1.0, 0.0, 2.0, 0.0, 1.0, 1.0));
END Main;

{{out}}

true
true
false
true
false
false
true

C

{{trans|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;
}

{{out}}

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

C++

#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;}

}

{{out}}

1,1
1,1
0,0
1,1
0,0
0,0
1,1
0,0

C#

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);
        }
    }
}

{{out}}

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

{{trans|Kotlin}}

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);
}

{{out}}

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

=={{header|F#|F sharp}}== {{trans|Kotlin}}

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

{{out}}

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

{{trans|Kotlin}}

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"))
}

{{out}}

Same as Kotlin entry.

Java

{{trans|Kotlin}} {{works with|Java|8}}

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");
        }
    }
}

{{out}}

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

{{trans|Python}} '''Module''':

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

'''Main''':

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

{{out}}

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

{{trans|C++}}

// 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")
}

{{out}}

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

Lua

{{trans|C++}}

function det2D(p1,p2,p3)
    return p1.x * (p2.y - p3.y)
         + p2.x * (p3.y - p1.y)
         + p3.x * (p1.y - p2.y)
end

function checkTriWinding(p1,p2,p3,allowReversed)
    local detTri = det2D(p1,p2,p3)
    if detTri < 0.0 then
        if allowReversed then
            local t = p3
            p3 = p2
            p2 = t
        else
            error("triangle has wrong winding direction")
        end
    end
    return nil
end

function boundaryCollideChk(p1,p2,p3,eps)
    return det2D(p1,p2,p3) < eps
end

function boundaryDoesntCollideChk(p1,p2,p3,eps)
    return det2D(p1,p2,p3) <= eps
end

function triTri2D(t1,t2,eps,allowReversed,onBoundary)
    eps = eps or 0.0
    allowReversed = allowReversed or false
    onBoundary = onBoundary or true

    -- triangles must be expressed anti-clockwise
    checkTriWinding(t1[1], t1[2], t1[3], allowReversed)
    checkTriWinding(t2[1], t2[2], t2[3], allowReversed)

    local chkEdge
    if onBoundary then
        -- points on the boundary are considered as colliding
        chkEdge = boundaryCollideChk
    else
        -- points on the boundary are not considered as colliding
        chkEdge = boundaryDoesntCollideChk
    end

    -- for edge E of triangle 1
    for i=0,2 do
        local j = (i+1)%3

        -- check all points of triangle 2 lay on the external side of the edge E.
        -- If they do, the triangles do not collide
        if chkEdge(t1[i+1], t1[j+1], t2[1], eps) and
           chkEdge(t1[i+1], t1[j+1], t2[2], eps) and
           chkEdge(t1[i+1], t1[j+1], t2[3], eps) then
            return false
        end
    end

    -- for edge E of triangle 2
    for i=0,2 do
        local j = (i+1)%3

        -- check all points of triangle 1 lay on the external side of the edge E.
        -- If they do, the triangles do not collide
        if chkEdge(t2[i+1], t2[j+1], t1[1], eps) and
           chkEdge(t2[i+1], t2[j+1], t1[2], eps) and
           chkEdge(t2[i+1], t2[j+1], t1[3], eps) then
            return false
        end
    end

    -- the triangles collide
    return true
end

function formatTri(t)
    return "Triangle: ("..t[1].x..", "..t[1].y
                .."), ("..t[2].x..", "..t[2].y
                .."), ("..t[3].x..", "..t[3].y..")"
end

function overlap(t1,t2,eps,allowReversed,onBoundary)
    if triTri2D(t1,t2,eps,allowReversed,onBoundary) then
        return "overlap\n"
    else
        return "do not overlap\n"
    end
end

-- Main
local t1 = {{x=0,y=0},{x=5,y=0},{x=0,y=5}}
local t2 = {{x=0,y=0},{x=5,y=0},{x=0,y=6}}
print(formatTri(t1).." and")
print(formatTri(t2))
print(overlap(t1,t2))

t1 = {{x=0,y=0},{x=0,y=5},{x=5,y=0}}
t2 = {{x=0,y=0},{x=0,y=5},{x=5,y=0}}
print(formatTri(t1).." and")
print(formatTri(t2))
print(overlap(t1,t2,0.0,true))

t1 = {{x=0,y=0},{x=5,y=0},{x=0,y=5}}
t2 = {{x=-10,y=0},{x=-5,y=0},{x=-1,y=6}}
print(formatTri(t1).." and")
print(formatTri(t2))
print(overlap(t1,t2))

t1 = {{x=0,y=0},{x=5,y=0},{x=2.5,y=5}}
t2 = {{x=0,y=4},{x=2.5,y=-1},{x=5,y=4}}
print(formatTri(t1).." and")
print(formatTri(t2))
print(overlap(t1,t2))

t1 = {{x=0,y=0},{x=1,y=1},{x=0,y=2}}
t2 = {{x=2,y=1},{x=3,y=0},{x=3,y=2}}
print(formatTri(t1).." and")
print(formatTri(t2))
print(overlap(t1,t2))

t1 = {{x=0,y=0},{x=1,y=1},{x=0,y=2}}
t2 = {{x=2,y=1},{x=3,y=-2},{x=3,y=4}}
print(formatTri(t1).." and")
print(formatTri(t2))
print(overlap(t1,t2))

-- Barely touching
t1 = {{x=0,y=0},{x=1,y=0},{x=0,y=1}}
t2 = {{x=1,y=0},{x=2,y=0},{x=1,y=1}}
print(formatTri(t1).." and")
print(formatTri(t2))
print(overlap(t1,t2,0.0,false,true))

-- Barely touching
local t1 = {{x=0,y=0},{x=1,y=0},{x=0,y=1}}
local t2 = {{x=1,y=0},{x=2,y=0},{x=1,y=1}}
print(formatTri(t1).." and")
print(formatTri(t2))
print(overlap(t1,t2,0.0,false,false))

{{out}}

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)
overlap

Triangle: (0, 0), (1, 0), (0, 1) and
Triangle: (1, 0), (2, 0), (1, 1)
overlap

=={{header|Modula-2}}==

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.

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 don''t 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 'don''t overlap but touch on' bordl,1
    Else
      call o abc 'and' def 'don''t 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