Get intersection points of line and shape

Question

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

If I draw a line on one of the diagonals of the bounding box, how can I get the intersection points (in the image they were painted in green)?

I use Java2D, I have GeneralPath with all the coordinates from which I draw the form on the screen.

Answer 1

Idea

You can deconstruct GenenralPath into your segments (move, straight, square, cubic, close) using the getPathIterator () method. Now you can search for each 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

Intersections of lines / lines can be calculated directly, for example, using vector algebra:

• 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 on 2d you have to divide the x and y coordinates by w
• if w = 0, then there is no unique intersection point

Line Intersections / Beziers

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

• de Casteljau subdivision
• Beziers
• Newton's method
• polynomial root search

De Casteljau unit is easy to implement, but has some problems in relatively rare cases. If you do not want to use a math library that can calculate intersections for you, I recommend using the de Castellau division.

Edit: Another alternative would be to approximate the segments of the Bezier Path curve with several line segments. Then you only need to find the intersection of the lines / lines.

Answer 2

Iterate through a list of points defining the shape. Put (x, y) in the line equation and see if it allows. Pseudocode -

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