Databases
StackOverflow2013
Postsdbo
POImplementing Hoey Shamos algorithm with C#
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POImplementing Hoey Shamos algorithm with C#
    primarykey
    data
    text
    <p>Okay, I am now getting the correct information from my current algorithm! However, with 700,000 polygons to check, it's just way too slow! The previous issue is fixed (My Line2D intersectsWith method was incorrect)</p> <p>Now it's a matter of identifying my bottleneck! This algorithm is suppose to be O(nlog-n) so it should be much quicker. My intersectsWith method looks like it can't get any faster, however I will post its code, in case I'm wrong</p> <p><strong>EDIT: Added IComparable interface</strong></p> <p>My method for reading line segment intersections. Some code has been omitted for readability.</p> <pre><code> public class Line2D : IComparable { public Line2D(XYPoints p1, XYPoints p2) { } public bool intersectsLine(Line2D comparedLine) { if ((X2 == comparedLine.X1) &amp;&amp; (Y2 == comparedLine.Y1)) return false; if ((X1 == comparedLine.X2) &amp;&amp; (Y1 == comparedLine.Y2)) return false; if (X2 == comparedLine.X1 &amp;&amp; Y2 == comparedLine.Y1) { return false; } if (X1 == comparedLine.X2 &amp;&amp; Y1 == comparedLine.Y2) { return false; } double firstLineSlopeX, firstLineSlopeY, secondLineSlopeX, secondLineSlopeY; firstLineSlopeX = X2 - X1; firstLineSlopeY = Y2 - Y1; secondLineSlopeX = comparedLine.getX2() - comparedLine.getX1(); secondLineSlopeY = comparedLine.getY2() - comparedLine.getY1(); double s, t; s = (-firstLineSlopeY * (X1 - comparedLine.getX1()) + firstLineSlopeX * (getY1() - comparedLine.getY1())) / (-secondLineSlopeX * firstLineSlopeY + firstLineSlopeX * secondLineSlopeY); t = (secondLineSlopeX * (getY1() - comparedLine.getY1()) - secondLineSlopeY * (getX1() - comparedLine.getX1())) / (-secondLineSlopeX * firstLineSlopeY + firstLineSlopeX * secondLineSlopeY); if (s &gt;= 0 &amp;&amp; s &lt;= 1 &amp;&amp; t &gt;= 0 &amp;&amp; t &lt;= 1) { return true; } return false; // No collision } int IComparable.CompareTo(object obj) { //return Y1.GetHashCode(); Line2D o1 = this; Line2D o2 = (Line2D)obj; if (o1.getY1() &lt; o2.getY1()) { return -1; } else if (o1.getY1() &gt; o2.getY2()) { return 1; } else { if (o1.getY2() &lt; o2.getY2()) { return -1; } else if (o1.getY2() &gt; o2.getY2()) { return 1; } else { return 0; } } } } </code></pre> <p>The bulk of my algorithm implementation, I realize a List isn't the fastest for an algorithm, however I need indexing!:</p> <pre><code>//Create a new list, sort by Y values. List&lt;AlgEvent&gt; SortedList = events.OrderBy(o =&gt; o.getY()).ToList(); List&lt;Line2D&gt; sweepline = new List&lt;Line2D&gt;(); for (var g = 0; g &lt; SortedList.Count; g++) { if (SortedList[g].isStart) { Line2D nl = SortedList[g].line; Line2D above; /* Start generating above */ try { //grab index in sweepline int index = sweepline.IndexOf(nl); //add 1 to get above line if (index == -1) { above = null; } else { above = sweepline[index + 1]; } } catch (ArgumentOutOfRangeException) { above = null; } /* End generating above */ if (above != null) { if (above.intersectsLine(nl)) { return true; } } Line2D below; /* Start generating below */ try { //grab index in sweepline int index = sweepline.IndexOf(nl); //add 1 to get above line below = sweepline[index - 1]; } catch (ArgumentOutOfRangeException) { below = null; } /* End generating below */ if (below != null) { if (below.intersectsLine(nl)) { return true; } } sweepline.Add(nl); sweepline = sweepline.OrderBy(o =&gt; o.getY1()).ToList(); } else { Line2D nl = SortedList[g].line; Line2D above; Line2D below; /* Start generating above */ try { //grab index in sweepline int index = sweepline.IndexOf(nl); Console.Out.WriteLine("index:" + index); //add 1 to get above line above = sweepline[index + 1]; } catch (ArgumentOutOfRangeException) { above = null; } /* End generating above */ /* Start generating below */ try { //grab index in sweepline int index = sweepline.IndexOf(nl); //add 1 to get above line below = sweepline[index - 1]; } catch (ArgumentOutOfRangeException) { below = null; } /* End generating below */ sweepline = sweepline.OrderBy(o =&gt; o.getY1()).ToList(); sweepline.Remove(nl); if (above != null &amp;&amp; below != null) { if (above.intersectsLine(below)) { return true; } } } Console.WriteLine(""); } } // end numofparts for-loop return false; </code></pre> <p>============================================</p> <p>UPDATE: September 12th: Implemented the TreeSet from C5, implemented IComparable to my classes, and slowed it down even more? I am still indexing it if that matters?</p> <p><a href="http://www.itu.dk/research/c5/" rel="nofollow">http://www.itu.dk/research/c5/</a></p> <p>Code using TreeSet:</p> <pre><code>TreeSet&lt;Line2D&gt; sweepline = new TreeSet&lt;Line2D&gt;(); for (var g = 0; g &lt; SortedList.Count; g++) { if (SortedList[g].isStart) { Line2D nl = SortedList[g].line; Line2D above; /* Start generating above */ try { //grab index in sweepline int index = sweepline.IndexOf(nl); //add 1 to get above line above = sweepline[index + 1]; } catch (IndexOutOfRangeException) { above = null; } /* End generating above */ if (above != null) { if (above.intersectsLine(nl)) { return false; } } Line2D below; /* Start generating below */ try { //grab index in sweepline int index = sweepline.IndexOf(nl); //add 1 to get above line below = sweepline[index - 1]; } catch (IndexOutOfRangeException) { below = null; } /* End generating below */ if (below != null) { if (below.intersectsLine(nl)) { return false; } } sweepline.Add(nl); //sweepline = sweepline.OrderBy(o =&gt; o.getY1()).ToList(); } else { Line2D nl = SortedList[g].line; Line2D above; Line2D below; /* Start generating above */ try { //grab index in sweepline int index = sweepline.IndexOf(nl); //Console.Out.WriteLine("index:" + index); //add 1 to get above line above = sweepline[index + 1]; } catch (IndexOutOfRangeException) { above = null; } /* End generating above */ /* Start generating below */ try { //grab index in sweepline int index = sweepline.IndexOf(nl); //add 1 to get above line below = sweepline[index - 1]; } catch (IndexOutOfRangeException) { below = null; } /* End generating below */ //sweepline = sweepline.OrderBy(o =&gt; o.getY1()).ToList(); sweepline.Remove(nl); if (above != null &amp;&amp; below != null) { if (above.intersectsLine(below)) { return false; } } } //Console.WriteLine(""); </code></pre> <p>}</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USEvan Parsons
    1. USEvan Parsons
    plurals
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POImplementing Hoey Shamos algorithm with C#
      1. USEvan Parsons
      1. VTBountyStart
    2. VO
      singulars
      1. POImplementing Hoey Shamos algorithm with C#
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POImplementing Hoey Shamos algorithm with C#
      1. This table or related slice is empty.
      1. VTDownMod
    1. COIs there a reason you couldn't implement TreeSet in C#, yourself?
      singulars
      1. POImplementing Hoey Shamos algorithm with C#
      1. USZac Howland
    2. COSo you're basically saying I could extend the OrderedSet class, and add the higher and lower methods?
      singulars
      1. POImplementing Hoey Shamos algorithm with C#
      1. USEvan Parsons
    3. CO@EvanParsons I think Zac is saying implement a TreeSet from scratch. TreeSet and the like use a *balanced tree* data structure (e.g. a Red-Black tree or an AVL tree) but these aren't simple to implement. A skip list is a much simpler data structure that would do the job though.
      singulars
      1. POImplementing Hoey Shamos algorithm with C#
      1. USjohn
 

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