java - 如何检查 triangle2D 是否在另一个内部或重叠？

Question

我正在尝试检查 triangle2D 是否包含另一个三角形或重叠它。

我可以用圆圈来做到这一点，例如:

/** 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();
}

但我不知道如何用三角形来做。

我找到了 this question仅用于点，但如果三角形包含其他三角形或与其重叠，我不知道该怎么做。

Answer 1

您可以在java.awt.geom.Line2D 中使用Line2D#contains、Line2D#linesIntersect 方法.

编辑:

数学思维:

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.

所以我们可以像下面这样使用另一个问题(你提到的)中的方式:

    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)

    }

但这不是有效的方法，所以我们将按以下方式实现它，以便在其他情况下重用。

我们应该有三种方法，一种用于检查max x, y，一种用于检查min x, y 和其他检查 lineSegment。

lineSegment 看起来像:

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.

}

所以要检查三角形是否包含其他三角形，我们的方法如下所示:

public boolean contains(Triangle t) {

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

或者简单地使用我上面提到的 Line2D 类:

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