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?
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.
@visose unfortunately i’m not very familiar with tree structures
@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.
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.
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);
}
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.
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)
@RadovanG you are always pushing line further Great solution I wonder how it can be that we use systems on same i7 and i always get longer times
when i pushed to comparer different condition without tolerance i am 400ms slower than you
Simply: return ( ( left.From == right.From && left.To == right.To ) || ( left.From == right.To && left.To == right.From ) );
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.
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.
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
Btw. as the word has been said … Any delaunay (2d & 3d) high performance ideas ?