CODEWITHSUNDEEP
javamathgeometrycomputational-geometryjava-2d
Mihir
Mihir

Reputation: 2520

Get intersection points of line and shape

I have a custom shape as shown in image. Suppose the blue rectangle covering the shape in the image depicts the bounding box of that shape.

If I draw line at one of the diagonal of the bounding rectangle, how can I get the intersection points (in image they were drawn using green color)?

I am using Java2D, I have a GeneralPath with all the coordinates from which I draw the shape on the screen.

Custom Shape

Upvotes: 4

Views: 5385

Answers (2)

Matthias
Matthias

Reputation: 1005

Idea

You can deconstruct the GenenralPath into its segments (move-to, line-to, quad-to, cubic-to, close) by using the getPathIterator() method. Now you can search per segment for intersections with the line.

public static Point[] getIntersections(Path path, Line line) {
    List<Point> intersections = new ArrayList<Point>();
    PathIterator it = path.getPathIterator();
    double[] coords = new double[6];
    double[] pos = new double[2];
    while (!it.isDone()) {
        int type = it.currentSegment(coords);
        switch (type) {
        case PathIterator.SEG_MOVETO:
            pos[0] = coords[0];
            pos[1] = coords[1];
            break;
        case PathIterator.SEG_LINETO:
            Line l = new Line(pos[0], pos[1], coords[0], coords[1]);
            pos[0] = coords[0];
            pos[1] = coords[1];
            Point intersection = getIntersection(line, l);
            if (intersection != null)
                intersections.add(intersection);
            break;
        //...
        default:
            throw new IllegalStateException("unknown PathIterator segment type: " + type);
        }
        it.next();
    }
    return intersections.toArray(new Point[] {});
}

Line/Line intersections

Line/Line intersections can be computed directly, for example, using vector algebra:

  • a 2d point/line is represented by a 3d vector (x, y, w)
  • the point (x, y) is represented by (x, y, 1)
  • the line through the points p1 and p2 is given by p1 x p2 (cross-product)
  • for two lines l1 = (a, b, c) and l2 = (d, e, f) the intersection is given by l1 x l2 (cross-product)
  • to project the intersection into 2d you have to divide x and y coordinates by w
  • if w = 0 then there is no single point of intersection

Line/Bezier intersections

A Path can contain quadratic and cubic Bezier curves. To find points of intersection between a line and a Bezier curve, there are several algorithms available, for example:

  • de Casteljau subdivision
  • Bezier clipping
  • Newton's method
  • polynomial root finding

De Casteljau subdivision is easy to implement but has some issues in relatively rare cases. If you do not want to use a math library which can compute the intersections for you, I recommend implementing de Casteljau subdivision.

Edit: Another alternative would be to approximate the Bezier curve segments of the Path by a number of line segments. Then you only need to find line/line intersections.

Upvotes: 5

Alptigin Jalayr
Alptigin Jalayr

Reputation: 709

Iterate through the list of points defining the shape. Place the (x,y) in the equation of the line, and see if it 'solves'. Pseudocode - 

int threshold = 0.01
for point in points: 
  if (point.y - m * point.x + c)^2 < threshold : 
    print "solution found"

Upvotes: 0

Related Questions