comparing two lines - vb component

Replies to This Discussion

Permalink Reply by Sridevi Koonath on November 27, 2012 at 12:53am

Not sure if they are the best possible options:

• If line1 = Line2 returns a false, then do a line1.Flip and compare them again; or
• Check if line1.BoundingBox.Equals(Line2.BoundingBox)

Permalink Reply by Raul Matagringo on November 27, 2012 at 2:01am

Hi,

i would say:

  private void RunScript(List<Line> x, List<Line> y, ref object A)
  {

    foreach (Line my_line_1 in x)
    {
      foreach (Line my_line_2 in y)
      {
        if (my_line_1.From == my_line_2.From || my_line_1.From == my_line_2.To || my_line_1.To == my_line_2.From || my_line_1.To == my_line_2.To)
        {

        }
      }
    }

  }

I dont think that this solution would be slow...

Permalink Reply by David Rutten on November 27, 2012 at 2:54am

I think your || && logic is a bit off but you're right that unless you build a spatial tree you won't be able to make it much faster than this. And building a spatial tree is both difficult and slow so it only really makes sense if you need to repeatedly perform these sorts of comparisons on the same list of lines.

If you really are dealing with the exact same lines, then you only have to compare From and To points to each other:

if (L0.From == L1.From && L0.To == L1.To)

  //lines are the same.

If however the lines are only equal within a certain accuracy then you'll need to compare both sides and include a tolerance check:

if (L0.From.DistanceTo(L1.From) < tolerance)

{

  // lines share start-points, they must now match end-points as well.

  if (L1.To.DistanceTo(L1.To) < tolerance)

    // lines are identical within tolerance.

}

else if (L0.From.DistanceTo(L1.To) < tolerance)

{

  // lines share start-point and end-point, they must match at the other end as well.

  if (L0.To.DistanceTo(L1.From) < tolerance)

    // lines are identical within tolerance.

}

--

David Rutten

david@mcneel.com

Poprad, Slovakia

Permalink Reply by Guillaume Niel on November 27, 2012 at 2:31pm

Thank you all, but I already used this method consisting in comparing .From and .To, and it is slow.In fact, I have 2 nested loops, and the total amount of comparisons is 10 000x5 000 = 50 000 000, for a 50x50 mesh (I'll have to deal with 10 times bigger meshes).

That is why I asked if there was a more efficient script to do this.

In my case, I will repeatedly perform these sorts of comparisons on the same list of lines, so I am interested in testing the spatial tree solution. Is there any exemple/post I could start from ?

Permalink Reply by David Rutten on November 28, 2012 at 12:50am

Where do these lines come from? Are they mesh edges?

--

David Rutten

david@mcneel.com

Poprad, Slovakia

Permalink Reply by Guillaume Niel on November 28, 2012 at 2:41pm

My lines are edges coming from a quad mesh, wich is the starting point of my global GH script.

In my first vb component, I use lines as an input, and they are built with the MEdges component, from my starting mesh. The geometry of the lines is then modified, through the formfinding routine.

In my second vb component, I need to build an array with 4 columns. Each row represent one face of the mesh (row 0 for face 0, row1 for face 1, ...) and each column represent the number of the edge element. If ABCD is the quad face, column 0 is  the number of the edge AB, column 1 is BC, column 2 is CD and column 3 is DA.

So to build this array, I extract the edges of each face with FaceB component then Explode component, and I build the array by comparing each line coming from this to each line coming from MEdges component, with a 2 level nested loop. Here is where I am looking for an efficient way to compare 2 lines...

Is there an easier and faster way to build this array ?

Permalink Reply by David Rutten on November 28, 2012 at 3:37pm

I'd definitely start with trying to maintain the data from the mesh rather than recreating the connectivity afterwards. The mesh knows which faces and edges are adjacent so ideally if you can tap into this information you won't have to write something yourself.

Since you compare each line to every other line, it does in fact pay to build a spatial tree I think, it turns the inner loop from O(N) into O(log N) so instead of O(N²) you'd get an algorithm that runs in O(N log N). I'll see if I can write something small in C# that uses the Grasshopper octree structure adapted for Line end-points.

--

David Rutten

david@mcneel.com

Poprad, Slovakia

Permalink Reply by David Rutten on November 28, 2012 at 4:34pm

Minor update, seems there's a stackoverflow exception somewhere in the tree-builder. I'm trying to track it down but until then I'll be of little help.

--

David Rutten

david@mcneel.com

Poprad, Slovakia

Permalink Reply by David Rutten on November 29, 2012 at 1:02pm

I fixed an infinite recursion bug so until the next version goes out you're in risk of crashing Rhino while running the attached file. It shows how to use the Grasshopper Tree3D class to create an octree for a point-set of custom types (in this case I created a new type called LinePoint which is both the xyz coordinate as well as the line index).

I suspect the crash happens when the largest number of coincident points is equal to or larger than the subdivision threshold (I used 30 in the attached script).

--

David Rutten

david@mcneel.com

Poprad, Slovakia

Attachments:

• LineSpatialTree.gh, 3 KB

Permalink Reply by Guillaume Niel on November 29, 2012 at 2:23pm

Thanks a lot David,

I'll look at this, but I have to convert the script into vb.net, I can't use C#.

I don't understand why using spatial trees leads to N logN iterations instead of N². Can I find some documentation somewhere for spatial tree theory ? 

Permalink Reply by David Rutten on November 29, 2012 at 4:55pm

You can use online translators to convert C# to VB and vice versa.

You're iterating over a list of lines, for each line you do something which takes the same amount of time. Such an algorithm is O(N) (twice the amount of lines, it'll take twice as long).

If you nest two loops you're iterating over each line, and then you iterate again over each line. So when you now have twice as many lines, it takes four times as long O(N*N) or O(N²)

With an octree you can reduce the second iteration from O(N) to O(log N). The reason octrees are fast is because they allow you to quickly reject large amounts of lines in your set. Lines are no longer stored in a list, but rather in recursive spatial buckets. If we determine that a certain bucket is too far away to possibly yield any valid results, we can instantly skip all the lines in that buckets and any sub-buckets. If you're lucky, you can reject ~85% of the local data in every iteration, which means even large collections of lines are reduced to only a few potential candidates very quickly.

Thinking about this I'm actually not sure now whether lookup in my Tree3d class is O(log N) or O(sqrt N), but the basic principle holds. The reason the resulting algorithm is O(N * log N) is because the outer loop is still O(N) but the inner loop is now replaced with an O(log N) searcher, so you end up with O(N) * O(log N) = O(N log N)

At least that's how I think it works, computational theory has never been my strong suit.

--

David Rutten

david@mcneel.com

Poprad, Slovakia

Permalink Reply by Raul Matagringo on November 28, 2012 at 4:06am

could you explain more? Are you searching for duplicates? Why do you have duplicates? You can use "SelDup" in rhino for eliminatig duplicates. I search often if startpoit = endpoint. For this i have my own class for members in C#. To speed up the operation you can use Dictionary and/or List.

• ‹ Previous
• 1
• 2
• Next ›
• Page