2

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.

Kate Gregory
  • 18,808
  • 8
  • 56
  • 85
user2932974
  • 23
  • 3
  • 5
    Really we'd like to see your attempt at solving this and what went wrong with it – Richard Tingle Oct 29 '13 at 16:37
  • Possible place to start; http://mathworld.wolfram.com/Circle-LineIntersection.html Once you've got the circle line intersection you can check if the point is on the arc – Richard Tingle Oct 29 '13 at 16:38
  • @Richard Tingle: I'm still in the algorithm proofing phase, I haven't started coding yet. – user2932974 Oct 29 '13 at 16:47
  • That was a route I was considering for handling arcs - treat them as circles and use circle intersections and filter out based on if the arc contains that section of the circle. I was hoping there were more arc-centric equations for doing this though, and I have not had any success researching arc intersection algorithms, other than "counting" ones. – user2932974 Oct 29 '13 at 16:50
  • This is possibly more of a maths question than a programming question. Here is annother possible starting point; http://math.stackexchange.com/questions/228841/how-do-i-calculate-the-intersections-of-a-straight-line-and-a-circle – Richard Tingle Oct 29 '13 at 16:55
  • For nearly all your computational geometry needs, including sample code and explanations of various pitfalls to avoid, refer to the Geometric Tools website and/or book: http://www.geometrictools.com/ It's one of several resources worth checking whenever a new problem crops up. – Rethunk Nov 03 '13 at 02:34
  • To avoid testing all combinations you'll probably want to use a sweep line algorithm. There are fast algorithms for line-line, but line-arc and arc-arc may be problematic and might be best to handle separately. – Nuclearman Nov 04 '13 at 16:10
  • Although the segments make a closed shape, with interior geometries, I think the only choice is to just see if an intersection occurs for all combinations. My alternative is to check each segment pairing to see if their end point ranges overlap on both the X and Y axis, however I think the computation time for that isn't much of an improvement over just calculating the intercept point. Or maybe I am underestimating how much computation is required in these algorithms... – user2932974 Nov 07 '13 at 01:35

1 Answers1

1

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

Community
  • 1
  • 1
nelly
  • 417
  • 3
  • 9
  • 1
    In fact the challenge is not to find an "arc-centric" algorithm, but to avoid the greedy search of all combinations. A quick idea would be to break the space is equal subspaces, quickly find the "boxes" where each of the arcs/lines is contained and only brute-force check shapes contained in each – nelly Oct 29 '13 at 16:59
  • I was going to find the bounding box of each segment, and ensure there is an intersection of the bounding box before anything else, but I'm not certain if that is too efficient. – user2932974 Oct 29 '13 at 17:38
  • On the bright side - I have a limit of 100 segments, so at worst, I should probably still be under a second on a fast processor. – user2932974 Oct 29 '13 at 17:38