Given line segments x1
, y1
, x2
, y2
, and circular arcs (defined with x1
, y1
, x2
, y2
, I
, j
; where I
is distance in the X direction from x1
to the center of the circle, j
is distance in the Y direction from y1
to the center of the circle; arcs with (x1,y1)
= (x2,y2)
are circles.), how do I find the coordinates of all points of intersection between a collection of these geometries?
Note: arcs can also be given as x1
, y1
, x2
, y2
, R
, with R
being radius, however I already have a mechanism for converting one into the other.
This is a project in Java, and I have not found any libraries or algorithms to determine this.
Determining the intersections between two line segments is simple, but the other cases are much more complex.
Your problem boils down to finding the intersection between (1) line-line, (2) line-arc, (3) arc-arc
(1) you can find plenty of solution on the internet. Here's one: How do you detect where two line segments intersect?
(2) suppose for the beginning that you have lines and circles (instead of just line segments and arcs). If the line and circle intersect, then you can compute the points this way: http://mathworld.wolfram.com/Circle-LineIntersection.html
In case these one or two points exist you have to check that they actually are contained in both the line segment AND the arc. If so, you have your points!
(3) here again you suppose you have two circle and find the points this way: http://mathworld.wolfram.com/Circle-CircleIntersection.html
and finally check again if the points belong in both arcs.
If you have these three methods you can try the greedy way and try all N^2 combinations of line segments and arcs