[ADD EXAMPLE] Determine if two triangles overlap

[jeremydouglass]

URL of task

https://rosettacode.org/wiki/Determine_if_two_triangles_overlap

Next steps

• [x] I will write the .pde sketch and submit as a pull request

[villares]

Hi @jeremydouglass,

I tried to port from Kotlin (I don't speak Kotlin!), would you care to have a look?

def triTri2D(t1, t2, eps=0.0, allow_reversed=False, on_boundary=True):
    # Triangles must be expressed anti-clockwise
    check_winding(t1, allow_reversed)
    check_winding(t2, allow_reversed)
    # 'on_boundary' determines whether points on boundary are considered as colliding or not
    chk_edge = bound_col_chk if on_boundary else bound_notcol_chk
    lp1 = t1.points
    lp2 = t2.points
    # for each edge E of t1
    for i in range(3):
        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 chk_edge(Triangle(lp1[i], lp1[j], lp2[0]), eps) and \
       chk_edge(Triangle(lp1[i], lp1[j], lp2[1]), eps) and \
       chk_edge(Triangle(lp1[i], lp1[j], lp2[2]), eps):
        return False
    # for each edge E of t2
    for i in range(3):
        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 chk_edge(Triangle(lp2[i], lp2[j], lp1[0]), eps) and \
           chk_edge(Triangle(lp2[i], lp2[j], lp1[1]), eps) and \
           chk_edge(Triangle(lp2[i], lp2[j], lp1[2]), eps):
            return False
    # The triangles overlap
    return True

class Triangle:
    def __init__(self, *args):
        if len(args) == 6:
            x1, y1, x2, y2, x3, y3 = args
            self.p1 = PVector(x1, y1)
            self.p2 = PVector(x2, y2)
            self.p3 = PVector(x3, y3)
        else:
            self.p1 = PVector(*args[0])
            self.p2 = PVector(*args[1])
            self.p3 = PVector(*args[2])
        self.points = self.p1, self.p2, self.p3
    def __repr__(self):
        return "Triangle: ({},{}) ({},{}) ({},{})".format(
            self.p1.x, self.p1.y, self.p2.x, self.p2.y, self.p3.x, self.p3.y)

def det2D(t):
    p1, p2, p3 = t.points
    return (p1.x * (p2.y - p3.y) +
            p2.x * (p3.y - p1.y) +
            p3.x * (p1.y - p2.y))

def check_winding(t, allow_reversed):
    detTri = det2D(t)
    if (detTri < 0.0):
        if allow_reversed:
            t.p3, t.p2 = t.p2, t.p3
        else:
            print("Triangle has wrong winding direction")
            exit()

def bound_col_chk(t, eps):
    return det2D(t) < eps

def bound_notcol_chk(t, eps):
    return det2D(t) <= eps

def setup():
    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)
    println("{} and {}".format(t1, t2))
    println("overlap" if triTri2D(t1, t2) else "do not overlap")

    # need, allow reversed for this pair, adef exception
    t1 = Triangle(0.0, 0.0, 0.0, 5.0, 5.0, 0.0)
    t2 = t1
    println("{} and {}".format(t1, t2))
    println("overlap" if triTri2D(t1, t2, allow_reversed=True)
            else "do not overlap")

    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)
    println("{} and {}".format(t1, t2))
    println("overlap" if triTri2D(t1, t2) else "do not overlap")

    t1.p3 = PVector(2.5, 5.0)
    t2 = Triangle(0.0, 4.0, 2.5, -1.0, 5.0, 4.0)
    println("{} and {}".format(t1, t2))
    println("overlap" if triTri2D(t1, t2) else "do not overlap")

    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)
    println("{} and {}".format(t1, t2))
    println("overlap" if triTri2D(t1, t2) else "do not overlap")

    t2 = Triangle(2.0, 1.0, 3.0, -2.0, 3.0, 4.0)
    println("{} and {}".format(t1, t2))
    println("overlap" if triTri2D(t1, t2) else "do not overlap")

    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)
    println("{} and {}".format(t1, t2))
    println("single corner in contact, boundary points collide")
    println("overlap" if triTri2D(t1, t2, on_boundary=True)
            else "do not overlap")

    println("{} and {}".format(t1, t2))
    println("single corner in contact, boundary points don't collide")
    println("overlap" if triTri2D(t1, t2, on_boundary=False)
            else "do not overlap")

[villares]

Processing Java mode attempt, translated from Java (that came from Kotlin...) but using a dirty global and some PVectors to simplify things.

boolean onBoundary;

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

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

boolean triTri2D(Triangle t1, Triangle t2, double eps, boolean allowedReversed, boolean onBcheck) {
  // set global onBoundary
  onBoundary = onBcheck;
  // Triangles must be expressed anti-clockwise
  checkTriWinding(t1, allowedReversed);
  checkTriWinding(t2, allowedReversed);
  // 'onBoundary' determines whether points on boundary are considered as colliding or not
  PVector[] lp1 = new PVector[]{t1.p1, t1.p2, t1.p3};
  PVector[] lp2 = new PVector[]{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(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) {
    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(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;
}

class Triangle {
  PVector p1, p2, p3;

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

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

double det2D(Triangle t) {
  PVector p1 = t.p1;
  PVector p2 = t.p2;
  PVector p3 = t.p3;
  return p1.x * (p2.y - p3.y)
    + p2.x * (p3.y - p1.y)
    + p3.x * (p1.y - p2.y);
}

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

boolean chkEdge(Triangle t, double eps) {
  if (onBoundary) {  // global onBoundary
    return boundaryCollideChk(t, eps);
  } else {
    return boundaryDoesntCollideChk(t, eps);
  }
}

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

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

void setup() {
  Triangle t1 = new Triangle(new PVector(0.0, 0.0), new PVector(5.0, 0.0), new PVector(0.0, 5.0));
  Triangle t2 = new Triangle(new PVector(0.0, 0.0), new PVector(5.0, 0.0), new PVector(0.0, 6.0));
  println(t1, "and \n", t2);
  if (triTri2D(t1, t2)) {
    println("overlap");
  } else {
    println("do not overlap");
  }

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

  t1 = new Triangle(new PVector(0.0, 0.0), new PVector(5.0, 0.0), new PVector(0.0, 5.0));
  t2 = new Triangle(new PVector(-10.0, 0.0), new PVector(-5.0, 0.0), new PVector(-1.0, 6.0));
  println(t1, "and \n", t2);
  if (triTri2D(t1, t2)) {
    println("overlap");
  } else {
    println("do not overlap");
  }

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

  t1 = new Triangle(new PVector(0.0, 0.0), new PVector(1.0, 1.0), new PVector(0.0, 2.0));
  t2 = new Triangle(new PVector(2.0, 1.0), new PVector(3.0, 0.0), new PVector(3.0, 2.0));
  println(t1, "and \n", t2);
  if (triTri2D(t1, t2)) {
    println("overlap");
  } else {
    println("do not overlap");
  }

  t2 = new Triangle(new PVector(2.0, 1.0), new PVector(3.0, -2.0), new PVector(3.0, 4.0));
  println(t1, "and \n", t2);
  if (triTri2D(t1, t2)) {
    println("overlap");
  } else {
    println("do not overlap");
  }

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

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

[jeremydouglass]

Wow -- this looks good! I like the robust test sketch.

I'm not familiar with this approach -- I'm sure it works, but the structure looks a bit odd to me. I wrote a collision detection library for Processing, and in it triangleTraingle() was an alias of polyPoly() -- and that takes the structure

• polypoly()
  • polyLine()
    • lineLine()
    • lineLine()
    • lineLine()
  • polyLine()
    • lineLine()
    • lineLine()
    • lineLine()
  • polyLine()
    • lineLine()
    • lineLine()
    • lineLine()

With that implementation, the question is in essence "do any of the line segments of these two polygons intersect?" If yes, the two polygons (two triangles) are overlapping, if no not. Importantly, because line segments have no interior and no winding the triangle point data can be in arbitrary order with different windings. That would cut a lot of exceptions and test cases.

Still, perhaps we could go ahead with this and then add the other approach as a separate option.

[jeremydouglass]

Here is some of that Processing library code (Java) from toolboxing for reference -- I really need to release that thing.

  public static boolean triTri(float x1, float y1, float x2, float y2, float x3, float y3,
    float x4, float y4, float x5, float y5, float x6, float y6) {
    PVector[] triPoints = new PVector[]{
      new PVector(x1, y1), 
      new PVector(x2, y2), 
      new PVector(x3, y3)
    };
    PVector[] triPoints2 = new PVector[]{
      new PVector(x4, y4), 
      new PVector(x5, y5), 
      new PVector(x6, y6)
    };
    return polyPoly(triPoints, triPoints2);
  }

  // POLYGON/POLYGON
  public static boolean polyPoly(PVector[] p1, PVector[] p2) {

    // go through each of the vertices, plus the next
    // vertex in the list
    int next = 0;
    for (int current=0; current<p1.length; current++) {

      // get next vertex in list
      // if we've hit the end, wrap around to 0
      next = current+1;
      if (next == p1.length) next = 0;

      // get the PVectors at our current position
      // this makes our if statement a little cleaner
      PVector vc = p1[current];    // c for "current"
      PVector vn = p1[next];       // n for "next"

      // now we can use these two points (a line) to compare
      // to the other polygon's vertices using polyLine()
      boolean collision = polyLine(p2, vc.x, vc.y, vn.x, vn.y);
      if (collision) return true;

      //// optional: check if the 2nd polygon is INSIDE the first
      //collision = polyPoint(p1, p2[0].x, p2[0].y);
      //if (collision) return true;
    }
    return false;
  }

  // POLYGON/LINE
  public static boolean polyLine(PVector[] vertices, float x1, float y1, float x2, float y2) {

    // go through each of the vertices, plus the next
    // vertex in the list
    int next = 0;
    for (int current=0; current<vertices.length; current++) {

      // get next vertex in list
      // if we've hit the end, wrap around to 0
      next = current+1;
      if (next == vertices.length) next = 0;

      // get the PVectors at our current position
      // extract X/Y coordinates from each
      float x3 = vertices[current].x;
      float y3 = vertices[current].y;
      float x4 = vertices[next].x;
      float y4 = vertices[next].y;

      // do a Line/Line comparison
      // if true, return 'true' immediately and
      // stop testing (faster)
      boolean hit = lineLine(x1, y1, x2, y2, x3, y3, x4, y4);
      if (hit) {
        return true;
      }
    }
    // never got a hit
    return false;
  }

  /**
   * Line / Line collision detection.
   *
   * @param   x1   line A origin x
   * @param   y1   line A origin y
   * @param   x2   line A endpoint x
   * @param   y2   line A endpoint y
   * @param   x3   line B origin x
   * @param   y3   line B origin y
   * @param   x4   line B endpoint x
   * @param   y4   line B endpoint y
   * @return  true on collision
   *
   * See http://www.jeffreythompson.org/collision-detection/line-line.php
   */
  public static boolean lineLine(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4) {

    // calculate the distance to intersection point
    float uA = ((x4-x3)*(y1-y3) - (y4-y3)*(x1-x3)) / ((y4-y3)*(x2-x1) - (x4-x3)*(y2-y1));
    float uB = ((x2-x1)*(y1-y3) - (y2-y1)*(x1-x3)) / ((y4-y3)*(x2-x1) - (x4-x3)*(y2-y1));

    // if uA and uB are between 0-1, lines are colliding
    if (uA >= 0 && uA <= 1 && uB >= 0 && uB <= 1) {
      return true;
    }
    return false;
  }

[villares]

Yeah, I find it odd too. I like your approach better. I have tried some poly-self-intersect tests doing what you described. But I was hopeful that reading the Kotlin example I would learn to like it... but well... leap of faith really :smirk:

I'd love to see your collision library! There was whole collision site I can't remember the name!

[jeremydouglass]

There was whole collision site I can't remember the name!

It might be http://jeffreythompson.org/collision-detection -- I used his tutorials to learn the building blocks for my collisions primitives -- great material. Here is his lineLine: http://www.jeffreythompson.org/collision-detection/line-line.php

He explicitly doesn't demonstrate triangleTriangle, but gestures at the polygon approach.

http://www.jeffreythompson.org/collision-detection/where_are_the_other_triangle_examples.php

[villares]

Don't you have to test ((y4-y3)*(x2-x1) - (x4-x3)*(y2-y1)) to avoid division by zero? What am I missing?

[jeremydouglass]

No, try it. Here is the trivial case where every point on each triangle is (1,1) -- so both cases reduce to (0-0)/(0-0).

void setup() {
  float x1, y1, x2, y2, x3, y3, x4, y4;
  x1 = y1 = x2 = y2 = x3 = y3 = x4 = y4 = 1;
  print(lineLine(x1, y1, x2, y2, x3, y3, x4, y4));
}

false

Division by 0 returns NaN, NaN fails if (uA >= 0, and the function returns false.

[jeremydouglass]

One could argue that if both triangles are the same point, they should return true -- but that isn't how this implementation works. I haven't tested if there are any other edge cases, though.

[jeremydouglass]

Okay, I thought about it more and realized that this is false any time the lines are parallel -- and not just during NaN, but any parallel, including partially and fully overlapping and identical. That's a problem for lineLine(), because that means line(a,b,c,d) is not intersecting with line(a,b,c,d). So Jeff's approach doesn't measure line collision, it measures line crossing.

This could probably be patched with a case that adds one additional check ( @jeffThompson ).

You can't see it in Jeff's test sketch at http://jeffreythompson.org/collision-detection/line-line.php because the two lines have different anchors. But if you modify the header like this:

float x1 = 0;    // line controlled by mouse
float y1 = 0;
float x2 = 100;   // fixed end
float y2 = 100;
float x3 = 100;  // static line
float y3 = 100;
float x4 = 400;
float y4 = 400;

...then you can move one line on top of the other and watch it not-intersect when they become parallel (in either direction).

This low-level problem only affects certain high-order cases, though. In cases like triTr, etc., if they share a single point, or if they are identical (fully overlapping), they will still show as colliding. It is only in the case where both polygons collapse to parallel lines that they will fail, because all their component lines fail to cross.

[jeremydouglass]

Well, turns out that Jeff actually footnoted that the test for "coincident lines" is left out.

I wrote this version to incorporate Bourke's two tests.

/**
 * Line / Line collision detection.
 *
 * @param   x1   line A origin x
 * @param   y1   line A origin y
 * @param   x2   line A endpoint x
 * @param   y2   line A endpoint y
 * @param   x3   line B origin x
 * @param   y3   line B origin y
 * @param   x4   line B endpoint x
 * @param   y4   line B endpoint y
 * @return  true on collision
 *
 * See http://www.jeffreythompson.org/collision-detection/line-line.php
 */
public static boolean lineLine(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4) {
  // calculate the distance to intersection point
  float uAn = ((x4-x3)*(y1-y3) - (y4-y3)*(x1-x3));
  float uBn = ((x2-x1)*(y1-y3) - (y2-y1)*(x1-x3));
  float denom = ((y4-y3)*(x2-x1) - (x4-x3)*(y2-y1));
  if (denom == 0) {
    // if both denominator and numerators are 0 the lines are coincident
    if (uAn == 0 && uBn == 0) {
      return true;
    }
    // otherwise the lines are parallel and not coincident
    return false;
  }
  float uA = uAn/denom;
  float uB = uBn/denom;
  // if uA and uB are between 0-1, lines are colliding
  if (uA >= 0 && uA <= 1 && uB >= 0 && uB <= 1) {
    return true;
  }
  // if either terms are out of range then lines are non-intersecting
  return false;
}

Also in this code no term is ever NaN -- 0 denominator cases are handled before devision. This means that a Python mode version can use the exact same line structure.

[villares]

Please add your preferred solution to the Rosetta wiki and I'll port it :)