Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <pre><code> // port of this JavaScript code with some changes: // http://www.kevlindev.com/gui/math/intersection/Intersection.js // found here: // http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect/563240#563240 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 &gt; B) // no intersection return new float[] { }; else if (A == B) return new float[] { A }; else // if (A &lt; B) return new float[] { A, B }; } // IMPORTANT: a1 and a2 cannot be the same, e.g. a1--a2 is a true segment, not a point // b1/b2 may be the same (b1--b2 is a point) private static PointF[] OneD_Intersection(PointF a1, PointF a2, PointF b1, PointF b2) { //float ua1 = 0.0f; // by definition //float ua2 = 1.0f; // by definition float ub1, ub2; float denomx = a2.X - a1.X; float denomy = a2.Y - a1.Y; if (Math.Abs(denomx) &gt; 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&lt;PointF&gt; ret = new List&lt;PointF&gt;(); 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 &lt; MyEpsilon; } private static double DistFromSeg(PointF p, PointF q0, PointF q1, double radius, ref float u) { // formula here: //http://mathworld.wolfram.com/Point-LineDistance2-Dimensional.html // where x0,y0 = p // x1,y1 = q0 // x2,y2 = q1 double dx21 = q1.X - q0.X; double dy21 = q1.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 &lt; MyEpsilon) throw new Exception("Expected line segment, not point."); double num = Math.Abs(dx21 * dy10 - dx10 * dy21); double d = num / segLength; return d; } // this is the general case. Really really general public static PointF[] Intersection(PointF a1, PointF a2, PointF b1, PointF b2) { if (a1.Equals(a2) &amp;&amp; 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)) // b 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, b is a segment { if (PointOnLine(a1, b1, b2)) return new PointF[] { a1 }; else return new PointF[] { }; } // at this point we know both a and b 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 &lt; u_b &amp;&amp; u_b &lt; MyEpsilon)) // e.g. u_b != 0.0 { float ua = ua_t / u_b; float ub = ub_t / u_b; if (0.0f &lt;= ua &amp;&amp; ua &lt;= 1.0f &amp;&amp; 0.0f &lt;= ub &amp;&amp; ub &lt;= 1.0f) { // Intersection return new PointF[] { new PointF(a1.X + ua * (a2.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 &lt; ua_t &amp;&amp; ua_t &lt; MyEpsilon) || (-MyEpsilon &lt; ub_t &amp;&amp; ub_t &lt; MyEpsilon)) { if (a1.Equals(a2)) // danger! return OneD_Intersection(b1, b2, a1, a2); else // safe return OneD_Intersection(a1, a2, b1, b2); } else { // Parallel return new PointF[] { }; } } } } </code></pre> <p>Here is the test code:</p> <pre><code> public class IntersectTest { public static void PrintPoints(PointF[] pf) { if (pf == null || pf.Length &lt; 1) System.Console.WriteLine("Doesn't intersect"); else if (pf.Length == 1) { System.Console.WriteLine(pf[0]); } else if (pf.Length == 2) { System.Console.WriteLine(pf[0] + " -- " + pf[1]); } } 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) { } } } </code></pre> <p>and here is the output:</p> <pre> ---------------------------------------------------------- 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} ---------------------------------------------------------- </pre>
    singulars
    1. This table or related slice is empty.
    1. PODetecting coincident subset of two coincident line segments
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USJared Updike
    1. USJared Updike
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTDownMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COI 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.
      singulars
      1. PO
      1. USEd S.
    2. COerrr... I didn't notice that you posted the question as well =P. I have removed the downvote.
      singulars
      1. PO
      1. USEd S.
    3. CO...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. :)
      singulars
      1. PO
      1. USEd S.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload