Topic: How to remove the lines of which's StartPoint.X are same in a List<Line>?

[waterharbin]

Hello,everyone.I have a List<Line> which have been sorted by the StartPoint.X.The code is below:

Code: [Select]

public int sortByStartPointX(Line a, Line b)
        {
            if (Math.Abs(a.StartPoint.X - b.StartPoint.X) <= 1)
                return a.StartPoint.Y.CompareTo(b.StartPoint.Y);
            return a.StartPoint.X.CompareTo(b.StartPoint.X);
        }
LineList.Sort(sortByStartPointX);
So,the lines'order should like the image.And now,my problem is that for each StartPoint.X, I just want a single line to be left in the LineList.Take the picture for example, I just want the 1,n+1,n+m+1 lines to be left in the LineList.All I can do is below.

Code: [Select]

List<Line> cesoredLineLst = new List<Line>();
private void  censorLines(List<Line> sourceLineList,List<Line> destinationLineList)
        {
            destinationLineList.Clear();    //Make sure it is empty at the begining

            while (sourceLineList.Count() > 0)  //The loop can noly stop when the sourceLineList is empty
            {
                //Get the loop line,which is the fist element of the List
                Line loopLine = sourceLineList.First();

                //remove the line from the List
                sourceLineList.Remove(loopLine);

                //to determine whethe the StartPoint.X existed in the destinationLineList or not
                bool existRepeatedX = destinationLineList.Exists(li =>
                    {
                        if (loopLine.StartPoint.X = li.StartPoint.X)
                            return true;
                        return false;
                    });

                //if not,add the line to the destinationLineList
                if (!existRepeatedX)
                    destinationLineList.Add(loopLine);
            }           
        }
cesorLines(LineList,cesoredLineLst);
I know my algorithm is not good.I need to define a extra List<Line>,and every line in the LineList need to be iterated.When the number is huge,this algorithm gets worse!! So,is there any way to improve? The extra List<Line> can be spared?

[Jeff H]

Are you asking for a list with of lines with the lowest Y value for each X value?
 
 
 

[Kerry]

waterharbin,
I can't lookat a solution at the moment.
Just wanted to say that yours seems to be one of the better presentations for a problem that I have seen for a while.

Regards

[waterharbin]

Are you asking for a list with of lines with the lowest Y value for each X value?

Hello,Jeff.The Y value is not important, any Y is OK.Only the X,the Xs need to be unique in the Line<Line>.

[waterharbin]

Hello,Kerry.I hope we can get it done together and you can teach me again, :-)And others will not  be troubled by problems like this.

[gile]

Hi,

If I do not misunderstand the task, this can easily be done using Linq.

Code: [Select]

        private List<Line> censorLines(List<Line> sourceLineList)
        {
            return sourceLineList
                .GroupBy(l => (int)l.StartPoint.X)
                .Select(g => g.OrderBy(l => l.StartPoint.Y).First())
                .ToList();
        }

[gile]

Or this one. A little more verbose but iterates only one time each IGrouping.

Code: [Select]

        private List<Line> censorLines(List<Line> sourceLineList)
        {
            return sourceLineList
                .GroupBy(l => (int)l.StartPoint.X)
                .Select(g => g.Aggregate((l1, l2) =>
                    { if (l1.StartPoint.Y < l2.StartPoint.Y) return l1; else return l2; }))
                .ToList();
        }

[gile]

Sorry, reading more attentively your code, I think I misundertood the task.

If you want to keep only one line with the same start point X coordinate whatever its Y coordinate ("The Y value is not important, any Y is OK"), you can use the IEnumerable.Distinct() extension method with your own iEqualityComparer implementation.

Code: [Select]

        private List<Line> CensorLines(List<Line> sourceLinelist)
        {
            return sourceLinelist.Distinct(new LineComparer()).ToList();
        }

        class LineComparer : IEqualityComparer<Line>
        {
            public bool Equals(Line l1, Line l2)
            {
                return l1.StartPoint.X == l2.StartPoint.X;
            }

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

[gile]

Or, more simple and concise using F#:

Code: [Select]

let censorLines (lines : Line seq) =
    lines
    |> Seq.distinctBy(fun l -> l.StartPoint.X)
    |> Seq.toList

[waterharbin]

Thank you,gile. And sorry for my poor English.