Comparing Line Ends


(Przemysław Doliwa) #1

I have this piece of code where i’m checking if line is the same ( i mean line lies one on other so start and end and end and start coords are the same - Line.Equals don’t work here for some reason )

  for ( int i = Lines.Count - 2; i >= 0; i-- )
        {
          for ( int j = Lines.Count - 1; j >= i + 1; j-- )
          {
            if ( LineEndsEquals(Lines[i], Lines[j]) )
            {
              Lines.RemoveAt(j);
            }
          }
        }

But this can take up to 11 seconds on medium line set ~30k. Maybe someone have idea how to check this quicker?


(Vicente Soler) #2

You could first get the mid points of all the lines, find duplicate points, then check if the end points of the lines that correspond to the duplicates match.
You can speed up the duplicate point search by many different ways. The easies in Rhino (but not necessarily most optimal) is to use the RTree class included.


(Przemysław Doliwa) #3

@visose unfortunately i’m not very familiar with tree structures :frowning:

@dale would you mind checking Line equality comparer? In my case lineA.Equals(lineB) or simply == don’t work don’t know why. Simplest possible way would be to use just Distinct() on line list but it don’t work - on points without problem.


(Dale Fugier) #4

Hi @D-W,

Without doing any investigation, I’m guess this is your problem.

http://developer.rhino3d.com/guides/cpp/do-not-test-for-equality/

Maybe this will help?

public static bool PointsAreEqualWithinTolerance(Point3d a, Point3d b, double tolerance)
{
  var rc = false;
  if (a.IsValid && b.IsValid)
  {
    if (tolerance < 0.0)
      tolerance = RhinoMath.ZeroTolerance;
    if (tolerance > 0.01)
      tolerance = 0.01;
    rc = a.DistanceTo(b) < tolerance;
  }
  return rc;
}

– Dale


(Przemysław Doliwa) #5

@dale hmm i don’t get how it relates to built-it Line.Equals() method - http://developer.rhino3d.com/5/api/RhinoCommonWin/html/M_Rhino_Geometry_Line_Equals.htm and http://developer.rhino3d.com/5/api/RhinoCommonWin/html/M_Rhino_Geometry_Line_op_Equality.htm

my method where i check ln1.From == ln2.From && … works but when in double reverse loop it is just superb slow so distinct here for sure would be quicker but it returns just original list.

and like i said earlier distinct for points works without problem.


(Dale Fugier) #6

Hi @D-W,

Line.Equals is lame because it does not take any tolerance into account. Because of floating point rounding errors, this is not a function you should use, in my opinion. Instead, use Line.EpsilonEquals or make up your own comparison function.

You might see if this method for culling duplicates is any faster - it might not be…

public static void CullDuplicateLines(List<Line> lines, double tolerance)
{
  tolerance = RhinoMath.Clamp(tolerance, RhinoMath.ZeroTolerance, 0.01);
  var temp = new List<Line>(lines.Count);
  for (var i = 0; i < lines.Count; i++)
  {
    if (lines[i].IsValid)
    {
      temp.Add(lines[i]);
      for (var j = i + 1; j < lines.Count; j++)
      {
        if (!lines[j].IsValid)
          continue;
        if (lines[i].EpsilonEquals(lines[j], tolerance))
          lines[j] = Line.Unset;
      }
    }
  }
  lines.Clear();
  lines.AddRange(temp);
}

– Dale


(Przemysław Doliwa) #7

@dale your method just don’t work :wink: no matter if tolerance is set even like that - when i use method i put just 1

tolerance = RhinoMath.Clamp(tolerance, RhinoMath.ZeroTolerance, 0.5);


(Vicente Soler) #8

You can use .Distinct() implementing your own IEqualityComparer:

  IEnumerable<Line> CullDupicateLines(IEnumerable<Line> lines, double tol)
  {
    var comparer = new LineComparer(tol);
    return lines.Distinct(comparer);
  }

  class LineComparer : IEqualityComparer<Line>
  {
    private double _tol;

    public LineComparer(double tol)
    {
      _tol = tol * tol;
    }

    public bool Equals(Line a, Line b)
    {
      if((a.PointAt(0.5) - b.PointAt(0.5)).SquareLength >= _tol)
        return false;

      if((a.From - b.From).SquareLength < _tol && (a.To - b.To).SquareLength < _tol)
        return true;

      if((a.From - b.To).SquareLength < _tol && (a.To - b.From).SquareLength < _tol)
        return true;

      return false;
    }

    public int GetHashCode(Line l)
    {
      return l.GetHashCode();
    }
  }

The extra check of the midpoint will probably speed it up in most cases (but not always).
Edit: With this comparer, two identical lines but with opposite directions will be considered equal, the EpsilonEquals method will flag them as different.


(Przemysław Doliwa) #9

That worked right out of the box :slight_smile: Thank you very much @visose!

It almost doesn’t add any aditional processing time on 30k lines!

And it is exacly what i need;)


(Radovan Grmusa) #10

Hi

If you need fast code and do not need to implement tolerance then:
-you group your items/Lines based on their hash code (the same line will have the same hash code)
-but because it can happen that different lines have the same hash code, you have to subgroup each group of lines by the same start point
-such subgroups of lines you group into subgroups based on their end points
-and now at the end if particular subgroup has more then item these items are the same
Total 123.456 lines (where almost half are duplicates) are processed in less then 1 sec.
testLinesDuplicates2.gh (1.7 MB)


(Przemysław Doliwa) #11

@RadovanG you are always pushing line further :slight_smile: Great solution :slight_smile: I wonder how it can be that we use systems on same i7 and i always get longer times :thinking:

when i pushed to comparer different condition without tolerance i am 400ms slower than you :slight_smile:
Simply: return ( ( left.From == right.From && left.To == right.To ) || ( left.From == right.To && left.To == right.From ) );

image

@visose get here ~2 / 2.2 sec

@RadovanG but i don’t get one thing why our sets of lines differs ? it seems you’re missing some lines :thinking:


(Vicente Soler) #12

The code I posted above, for half a million lines (~300k unique) takes 152 ms. Most of the time measured in the profiler is the huge overhead of casting the list of lines into the scripting component.


(Przemysław Doliwa) #13

@visose i found so far this performance differs from set to set but your version is good clean and simple - having KISS rule in mind :slight_smile:


(Vicente Soler) #14


To get around the overhead of casting the list of lines, I’m inputting a single mesh object. The vertices of the mesh store the lines as a list of points (start, end, start, end…).

Very important to profile your code, to know where it’s actually slow. 123456 lines as above takes 22 ms.


(Radovan Grmusa) #15

The difference in resulting set can be caused if tolerance is applied, if case of no tolerance applied less lines will be detected as duplicates.


(Radovan Grmusa) #16

After baking lines and using native Rhino command I got the same resulting sets of duplicate lines as with my script.


(Radovan Grmusa) #17

I do not see your code in the post.


(Vicente Soler) #18

It’s in the reply in this thread marked as solution.


(Przemysław Doliwa) #19

Hmm weird i’m using this to cull own delaunay and i get similar numbers as in Delaunay Edges comoponent sometimes native gh component have more lines not sure why cause i’m not missing any :thinking:

Btw. as the word has been said … Any delaunay (2d & 3d) high performance ideas ? :smiley:


(Vicente Soler) #20

Use this library:
https://designengrlab.github.io/MIConvexHull/
It’s in C# and very simple to use.