LIBGDX Where does a Polygon and a Line collide?

Question

I want to get the Point where a Polygon and a Line collides. I know there is a class called Intersector, but in this there is only a method for checking wether they collide or not, but I need the point where they are colliding.

I am happy with any help

public static List<RayTrace> rayTrace(Line2D line, boolean quick, Collisions... collisions) {
    List<RayTrace> l = new ArrayList<RayTrace>();
    for (Collisions collisions1 : collisions) {
        for (Collision3D collision3D : collisions1) {
            RayTrace rayTrace = new RayTrace();
            if (quick) {
                if (Intersector.intersectLinePolygon(line.getStartV(), line.getEndV(), collision3D.getBoundingPolygon())) {
                    rayTrace.collisionHit = collision3D;
                    rayTrace.hasHit = true;
                    l.add(rayTrace);
                }
            } else {
                Point2f hit = new Point2f();
                if (CollisionHelper.getLinePolygonIntersection(collision3D.getBoundingPolygon(), line, hit)) {
                    rayTrace.collisionHit = collision3D;
                    rayTrace.hasHit = true;
                    rayTrace.hitX = hit.x;
                    rayTrace.hitZ = hit.y;
                    l.add(rayTrace);
                }
            }
        }
    }
    return l;
}

public static List<Vector2> getLinePolygonIntersections(Polygon polygon, Line2D line) {
    float f[] = polygon.getTransformedVertices();
    //Go through every side
    List<Vector2> intersections = new ArrayList<Vector2>();
    for (int i = 0; i < f.length - 2; i += 2) {
        Vector2 intersection = new Vector2();
        Intersector.intersectLines(line.x, line.y, line.x2, line.y2, f[i], f[i + 1], f[i + 2], f[i + 3], intersection);
        intersections.add(intersection);
    }
    return intersections;
}

public static boolean getLinePolygonIntersection(@NotNull Polygon polygon, @NotNull Line2D line, @NotNull Point2f point) {
    List<Vector2> list = getLinePolygonIntersections(polygon, line);
    if (list.size() == 0) return false;
    double shortestDistance = line.getStart().distance(new Point2f(list.get(0).x, list.get(0).y));
    int indexClosest = 0;
    for (int i = 1; i < list.size(); i++) {
        double d = new Point2f(list.get(i).x, list.get(i).y).distance(line.getStart());
        if (shortestDistance > d) {
            indexClosest = i;
            shortestDistance = d;
        }
    }
    point.set(list.get(indexClosest).x, list.get(indexClosest).y);
    return true;
}

Answer 1

Here is the method from the LibGDX Intersector class that could be modified:

public static boolean intersectLinePolygon (Vector2 p1, Vector2 p2, Polygon polygon) {
     float[] vertices = polygon.getTransformedVertices();
     float x1 = p1.x, y1 = p1.y, x2 = p2.x, y2 = p2.y;
     int n = vertices.length;
     float x3 = vertices[n - 2], y3 = vertices[n - 1];
     for (int i = 0; i < n; i += 2) {
          float x4 = vertices[i], y4 = vertices[i + 1];
          float d = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1);
          if (d != 0) {
                float yd = y1 - y3;
                float xd = x1 - x3;
                float ua = ((x4 - x3) * yd - (y4 - y3) * xd) / d;
                if (ua >= 0 && ua <= 1) {
                     return true;
                }
          }
          x3 = x4;
          y3 = y4;
     }
     return false;
}

What this method is actually doing is finding the intersection between the line segment from p1 to p2 with the edge of the polygon. (In particular, it is determining if there is any intersection between the given line segments, which will be important later.) In particular, the computations are being performed on the parametric equation of these two line segments; for example, the line segment from (x1,y1) to (x2,y2) has parametric equation

L(t) = [ x2-x1, y2-y1 ] * t + [ x1, y1 ] 

where t ranges from 0 to 1.

The intersection of the the lines is calculated using Cramer's rule; the variable d above represents the determinant of the matrix appearing in the denominator of that formula. When d is nonzero, there is guaranteed to be an intersection between the lines, but we aren't done yet, because we are interested in the intersection of the line segments. The variable ua in the method yields the value of t in the parametric equation above when the intersection occurs; it must be between 0 and 1 for the intersection point to lie between the endpoints of the line segment.

Thus, the coordinates of the point of intersection can be calculated by evaluating L(t) when t = ua. To find the point of intersection, therefore, you could create your own version of this function that returns the value

Vector2( (x2-x1)*ua + x1, (y2-y1)*ua + y1)

Hope this helps!

Answer 2

IMHO: In the Intersector class many methods calculate collisions and generally the last parameter is a Vector3 filled with the coordinates of the collision.

I've never used this library, but at first glance, it's the way it works.