How to check if triangle2D is inside another one or overlapping it?

Question

I'm trying to check if triangle2D is contain another triangle or overlapping it.

I can do that with circle e.g:

/** Return true if the specified point
 *   (x, y) is inside this circle     */
public boolean contains(double x, double y) {
    return Math.sqrt(Math.pow(x - this.x, 2) +
            Math.pow(y - this.y, 2))
            < radius;
}

/** Return true if the specified
 *   circle is inside this circle */
public boolean contains(Circle2D circle) {
    return Math.sqrt(Math.pow(circle.getX() - x, 2) +
            Math.pow(circle.getY() - y, 2))
            <= Math.abs(radius - circle.getRadius());
}

/** Return true if the specified
 *   circle overlaps with this circle */
public boolean overlaps(Circle2D circle) {
    return Math.sqrt(Math.pow(circle.getX() - x, 2) +
            Math.pow(circle.getY() - y, 2))
            <= radius + circle.getRadius();
}

But I don't know how to do that with triangle.

I've found this question for point only, but I don't how to do that if triangle contain other triangle or overlapping it.

See [What's the most efficient way to detect triangle-triangle intersections?](https://stackoverflow.com/q/1585459/5221149) for high-level answer. See [Find the area of overlap of two triangles](https://math.stackexchange.com/q/154628) for more serious math-answer. — Andreas, Nov 19 '17 at 14:31
are you checking for a specific triangle or simply counting how many triangles are there in other triangles? — Luai Ghunim, Nov 19 '17 at 14:31

score 0 · Answer 1 · answered Nov 19 '17 at 14:30

For the case of containing you can check all vertices of a triangle. If all of them are existed inner of the other, one of them contains the other one.

For the case of overlapping, You should consider is there any intersection between any edge of these two triangle or not. If there is not and the containing case was not happened, they are separated. For the case of intersecting two edges (as two segments) on the plane, you can using this post.

score 0 · Accepted Answer · 2017-11-20T00:28:12.727

You can use Line2D#contains, Line2D#linesIntersect methods inside java.awt.geom.Line2D.

Edit:

Thinking in Math:

To detect whether a point is inside a triangle, draw three dashed lines, if the point is inside a triangle, each dashed line should intersect a side only once. if a dashed line intersect a side twice, then the point must be outside the triangle.

So We can use the way in the other question (you mentioned) like below:

    public boolean contains(MyPoint p) {
//        double area1 = calcArea(p, p1, p2);
//        double area2 = calcArea(p, p2, p3);
//        double area3 = calcArea(p, p3, p1);
//        double area = Math.round((area1 + area2 + area3) * 100) / 100;
//        double triangleArea =  Math.round(getArea() * 100) / 100;
//        return (triangleArea == area)

    }

But it's not efficient way, so we will implement it as below, in order to reuse it with other cases.

We should have three methods one for check max x, y, one for checking min x, y and other for checking the lineSegment.

The lineSegment would be look like:

double position = (x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0);

return position <= 0.0000000001 && ((x0 <= x2 && x2 <= x1) || (x0 >= x2 && x2 >= x1));

  /**
 * returns true if the specified point is inside this triangle
 **/
public boolean contains(MyPoint p) {

    return contains(p.getX(), p.getY());
}

public boolean contains(double x, double y) {

    // Get max X & Y
    double maxX = getMax(p1.getX(), p2.getY(), p3.getX());
    double maxY = getMax(p1.getY(), p2.getY(), p3.getX());

    // Get min X & Y
    double minX = getMin(p1.getX(), p2.getX(), p3.getX());
    double minY = getMin(p1.getY(), p2.getY(), p3.getY());

    // Outside the bounding rectangle of the triangle
    if (x < minX || x > maxX || y < minY || y > maxY) return false;

    // Check if point is the border of the triangle
    MyPoint p = new MyPoint(x, y);
    boolean side1 = p.onTheLineSegment(p1, p2); //assume A to B
    boolean side2 = p.onTheLineSegment(p1, p3); //assume B to C
    boolean side3 = p.onTheLineSegment(p2, p3); //assume C to A
    return side1 || side2 || side3; //return true if any point of these vertices inside triangle.

}

So to check if triangle contain other one, our method would be look like:

public boolean contains(Triangle t) {

    return contains(t.p1) && contains(t.p2) && contains(t.p3); //All three points is inside the triangle
}

Or simply by using Line2D class as I mention above:

Line2D line2D = new Line2D.Double(p1.getX(), p1.getY(), p2.getX(), p2.getY());
return line2D.contains(....); //check if contain triangle or point

score 0 · Answer 3 · answered Nov 19 '17 at 19:22

Use the LeftOf predicate, which is true when the algebraic area of the triangle ABC is positive (using the appropriate sign convention), telling you that C is on the left of the line AB.

Then check if all three vertices of the first triangle lie left of some side of the second one. If not, repeat after exchanging the two triangles.

Finally if yes, the triangles do not interfere.

How to check if triangle2D is inside another one or overlapping it?

3 Answers3