Detecting coincident subset of two coincident line segments?

Sounds like you have your solution, which is great. I have some suggestions for improving it.

Sounds like you have your solution, which is great. I have some suggestions for improving it. The method has a major usability problem, in that it is very confusing to understand (1) what the parameters going in mean, and (2) what the results coming out mean.

Both are little puzzles that you have to figure out if you want to use the method. I would be more inclined to use the type system to make it much more clear what this method does. I'd start by defining a type -- perhaps a struct, particularly if it was going to be immutable -- called LineSegment.

A LineSegment consists of two PointF structs representing the end point. Second, I would define an abstract base type "Locus" and derived types EmptyLocus, PointLocus, LineSegmentLocus and perhaps UnionLocus if you need to represent the locus that is the union of two or more loci. An empty locus is just a singleton, a point locus is just a single point, and so on.

Now your method signature becomes much more clear: static Locus Intersect(LineSegment l1, LineSegment l2) This method takes two line segments and computes the locus of points that is their intersection -- either empty, a single point, or a line segment. Note that you can then generalize this method. Computing the intersection of a line segment with a line segment is tricky, but computing the intersection of a line segment with a point, or a point with a point, or anything with the empty locus is easy.

And it's not hard to extend intersection to arbitrary unions of loci. Therefore, you could actually write: static Locus Intersect(Locus l1, Locus l2) And hey, now it becomes clear that Intersect could be an extension method on locus: static Locus Intersect(this Locus l1, Locus l2) Add an implicit conversion from PointF to PointLocus and LineSegment to LineSegmentLocus, and you can say things like var point = new PointF(whatever); var lineseg = new LineSegment(somepoint, someotherpoint); var intersection = lineseg. Intersect(point); if (intersection is EmptyLocus) ... Using the type system well can massively improve the readability of a program.

1 Thanks for the recommendations and extensions. – Jared Updike Feb 13 '10 at 21:13 This is a great method Eric, I was previously using enums combined with other objects to provide a result. This is elegant and far superior.

Thank you. – Nick Wiggill Jul 25 '10 at 20:55.

Port of this JavaScript code with some changes: // kevlindev.com/gui/math/intersection/Inte... // found here: // stackoverflow.com/questions/563198/how-d... public class Intersector { static double MyEpsilon = 0.00001; private static float OverlapIntervals(float ub1, float ub2) { float l = Math. Min(ub1, ub2); float r = Math. Max(ub1, ub2); float A = Math.

Max(0, l); float B = Math. Min(1, r); if (A > B) // no intersection return new float { }; else if (A == B) return new float { A }; else // if (A Math. Abs(denomy)) { ub1 = (b1.

X - a1. X) / denomx; ub2 = (b2. X - a1.

X) / denomx; } else { ub1 = (b1. Y - a1. Y) / denomy; ub2 = (b2.

Y - a1. Y) / denomy; } List ret = new List(); float interval = OverlapIntervals(ub1, ub2); foreach (float f in interval) { float x = a2. X * f + a1.

X * (1.0f - f); float y = a2. Y * f + a1. Y * (1.0f - f); PointF p = new PointF(x, y); ret.

Add(p); } return ret.ToArray(); } private static bool PointOnLine(PointF p, PointF a1, PointF a2) { float dummyU = 0.0f; double d = DistFromSeg(p, a1, a2, MyEpsilon, ref dummyU); return d Y - q0. Y; double dx10 = q0. X - p.

X; double dy10 = q0. Y - p. Y; double segLength = Math.

Sqrt(dx21 * dx21 + dy21 * dy21); if (segLength Really really general public static PointF Intersection(PointF a1, PointF a2, PointF b1, PointF b2) { if (a1. Equals(a2) && b1. Equals(b2)) { // both "segments" are points, return either point if (a1.

Equals(b1)) return new PointF { a1 }; else // both "segments" are different points, return empty set return new PointF { }; } else if (b1. Equals(b2)) // be is a point, a is a segment { if (PointOnLine(b1, a1, a2)) return new PointF { b1 }; else return new PointF { }; } else if (a1. Equals(a2)) // a is a point, be is a segment { if (PointOnLine(a1, b1, b2)) return new PointF { a1 }; else return new PointF { }; } // at this point we know both a and be are actual segments float ua_t = (b2.

X - b1. X) * (a1. Y - b1.

Y) - (b2. Y - b1. Y) * (a1.

X - b1. X); float ub_t = (a2. X - a1.

X) * (a1. Y - b1. Y) - (a2.

Y - a1. Y) * (a1. X - b1.

X); float u_b = (b2. Y - b1. Y) * (a2.

X - a1. X) - (b2. X - b1.

X) * (a2. Y - a1. Y); // Infinite lines intersect somewhere if (!(-MyEpsilon U_b!

= 0.0 { float ua = ua_t / u_b; float ub = ub_t / u_b; if (0.0f X - a1. X), a1. Y + ua * (a2.

Y - a1. Y)) }; } else { // No Intersection return new PointF { }; } } else // lines (not just segments) are parallel or the same line { // Coincident // find the common overlapping section of the lines // first find the distance (squared) from one point (a1) to each point if ((-MyEpsilon Return OneD_Intersection(b1, b2, a1, a2); else // safe return OneD_Intersection(a1, a2, b1, b2); } else { // Parallel return new PointF { }; } } } } Here is the test code: public class IntersectTest { public static void PrintPoints(PointF pf) { if (pf == null || pf. Length Length == 1) { System.Console.

WriteLine(pf0); } else if (pf. Length == 2) { System.Console. WriteLine(pf0 + " -- " + pf1); } } public static void TestIntersect(PointF a1, PointF a2, PointF b1, PointF b2) { System.Console.

WriteLine("----------------------------------------------------------"); System.Console. WriteLine("Does " + a1 + " -- " + a2); System.Console. WriteLine("intersect " + b1 + " -- " + b2 + " and if so, where?

"); System.Console. WriteLine(""); PointF result = Intersect. Intersection(a1, a2, b1, b2); PrintPoints(result); } public static void Main() { System.Console.

WriteLine("----------------------------------------------------------"); System.Console. WriteLine("line segments intersect"); TestIntersect(new PointF(0, 0), new PointF(100, 100), new PointF(100, 0), new PointF(0, 100)); TestIntersect(new PointF(5, 17), new PointF(100, 100), new PointF(100, 29), new PointF(8, 100)); System.Console. WriteLine("----------------------------------------------------------"); System.Console.

WriteLine(""); System.Console. WriteLine("----------------------------------------------------------"); System.Console. WriteLine("just touching points and lines cross"); TestIntersect(new PointF(0, 0), new PointF(25, 25), new PointF(25, 25), new PointF(100, 75)); System.Console.

WriteLine("----------------------------------------------------------"); System.Console. WriteLine(""); System.Console. WriteLine("----------------------------------------------------------"); System.Console.

WriteLine("parallel"); TestIntersect(new PointF(0, 0), new PointF(0, 100), new PointF(100, 0), new PointF(100, 100)); System.Console. WriteLine("----------------------------------------------------------"); System.Console. WriteLine(""); System.Console.

WriteLine("----"); System.Console. WriteLine("lines cross but segments don't intersect"); TestIntersect(new PointF(50, 50), new PointF(100, 100), new PointF(0, 25), new PointF(25, 0)); System.Console. WriteLine("----------------------------------------------------------"); System.Console.

WriteLine(""); System.Console. WriteLine("----------------------------------------------------------"); System.Console. WriteLine("coincident but do not overlap!

"); TestIntersect(new PointF(0, 0), new PointF(25, 25), new PointF(75, 75), new PointF(100, 100)); System.Console. WriteLine("----------------------------------------------------------"); System.Console. WriteLine(""); System.Console.

WriteLine("----------------------------------------------------------"); System.Console. WriteLine("touching points and coincident!"); TestIntersect(new PointF(0, 0), new PointF(25, 25), new PointF(25, 25), new PointF(100, 100)); System.Console. WriteLine("----------------------------------------------------------"); System.Console.

WriteLine(""); System.Console. WriteLine("----------------------------------------------------------"); System.Console. WriteLine("overlap/coincident"); TestIntersect(new PointF(0, 0), new PointF(75, 75), new PointF(25, 25), new PointF(100, 100)); TestIntersect(new PointF(0, 0), new PointF(100, 100), new PointF(0, 0), new PointF(100, 100)); System.Console.

WriteLine("----------------------------------------------------------"); System.Console. WriteLine(""); while (!System.Console. KeyAvailable) { } } } and here is the output: ---------------------------------------------------------- line segments intersect ---------------------------------------------------------- Does {X=0, Y=0} -- {X=100, Y=100} intersect {X=100, Y=0} -- {X=0, Y=100} and if so, where?

{X=50, Y=50} ---------------------------------------------------------- Does {X=5, Y=17} -- {X=100, Y=100} intersect {X=100, Y=29} -- {X=8, Y=100} and if so, where? {X=56.85001, Y=62.30054} ---------------------------------------------------------- ---------------------------------------------------------- just touching points and lines cross ---------------------------------------------------------- Does {X=0, Y=0} -- {X=25, Y=25} intersect {X=25, Y=25} -- {X=100, Y=75} and if so, where? {X=25, Y=25} ---------------------------------------------------------- ---------------------------------------------------------- parallel ---------------------------------------------------------- Does {X=0, Y=0} -- {X=0, Y=100} intersect {X=100, Y=0} -- {X=100, Y=100} and if so, where?

Doesn't intersect ---------------------------------------------------------- ---- lines cross but segments don't intersect ---------------------------------------------------------- Does {X=50, Y=50} -- {X=100, Y=100} intersect {X=0, Y=25} -- {X=25, Y=0} and if so, where? Doesn't intersect ---------------------------------------------------------- ---------------------------------------------------------- coincident but do not overlap! ---------------------------------------------------------- Does {X=0, Y=0} -- {X=25, Y=25} intersect {X=75, Y=75} -- {X=100, Y=100} and if so, where?

Doesn't intersect ---------------------------------------------------------- ---------------------------------------------------------- touching points and coincident! ---------------------------------------------------------- Does {X=0, Y=0} -- {X=25, Y=25} intersect {X=25, Y=25} -- {X=100, Y=100} and if so, where? {X=25, Y=25} ---------------------------------------------------------- ---------------------------------------------------------- overlap/coincident ---------------------------------------------------------- Does {X=0, Y=0} -- {X=75, Y=75} intersect {X=25, Y=25} -- {X=100, Y=100} and if so, where?

{X=25, Y=25} -- {X=75, Y=75} ---------------------------------------------------------- Does {X=0, Y=0} -- {X=100, Y=100} intersect {X=0, Y=0} -- {X=100, Y=100} and if so, where? {X=0, Y=0} -- {X=100, Y=100}.

I downvoted only because I feel that providing a complete code sample here goes against the spirit of the site. The OP does not seem to want to learn, they just want their assignment done by someone else. – Ed S.

Feb 13 '10 at 0:00 errr... I didn't notice that you posted the question as well =P. I have removed the downvote. – Ed S.

Feb 13 '10 at 0:03 ...or not, I am being told that my 10 minute old post is too old to change. I have upvoted another of your answers to make up for it. Sorry.

:) – Ed S. Feb 13 '10 at 0:04 Thanks for "taking it back". You will notice that I also marked the question as Community Wiki to avoid people thinking I was rep farming, etc.That is an interesting question though... is posting a working code example against the spirit of the site?

Perhaps I should post it somewhere else (blog, etc. ) and link to it? The point is that a lot of the answers to other similar questions have fatal flaws in them, which is really... against the spirit of the site too. Thanks for the attempted explanation.

Perhaps I should have just posted this on a blog somewhere, when I finished.Sorry... – Jared Updike Feb 13 '10 at 0:39 Also, since it's community Wiki, neither of us have lost any rep! – Jared Updike Feb 13 '10 at 0:40.

Jared, Great question and great answer. The problem can be simplified by representing the position of a point along a line as a function of a single parameter as explained on Joseph O' Rourke's CGA FAQ here. Let r be a parameter to indicate P's location along the line containing AB, with the following meaning: r=0 P = A r=1 P = B r1 P is on the forward extension of AB 0Note that we avoid taking square roots because only the square of the length is required.

One plus for the link reference. It was useful to me – Gnomo Oct 20 '10 at 10:30.

This is really very simple. If you have two lines you can find two equations in the form of y = mx + b. For example: y = 2x + 5 y = x - 3 So, the two lines intersect when y1 = y2 at the same x coordinate, so... 2x + 5 = x - 3 x + 5 = -3 x = -8 When x=-8 y1=y2 and you have found the point of intersection.

This should be very trivial to translate into code. If there is no intersection point than the slope m of each line will be equal, in which case you do not even need to perform the calculation.

This is also subtly wrong: when the points are above and below each other, the slope is infinite and all hell breaks lose. – Jared Updike Feb 13 '10 at 0:38 When the slopes of each line are equal, they can still intersect at one point or at a line segment, or even not overlap at all. – Jared Updike Feb 13 '10 at 0:48.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.