organising lists using hashsets or better approach?

Hello Vulpes,
Many thanks for all your help in this matter. I have been thinking about the subdivision problem and I can only see non straightforward workarounds. I will have to look deeper into the subdivision issue later on but for now I have decided to move on. I am currently working on the contouring code. The contouring code was working for the expected cases represented by Groups 11,12,21,22 but we had problems when it came to the groups 31,32.
After a lot of thinking I came up with an algorithm that might work properly for such groups. I would like to add this algorithm to the current code but I am bit lost about how to proceed.

I have attached a file explaining the algorithm and a practical example to clarify its implementation. Can you please have a look at it?
 
My final code should be as follows:

////////////////////////////////////////////////
3 possible inputs: 
i) Group11 and Group12 or 
ii) Group21 and Group22 or 
iii) Group31 and Group32 

For i) and ii) we can use the current code.
For iii) we have to use the new algorithm.

Outputs:
Contour indices (go to txt file)
Contour points (go to txt file and to xls file)
/////////////////////////////////////////////////

The contouring code I am referring to is the following:

using System;

using System.Collections.Generic;

using System.Linq;

using System.IO;

using System.Text.RegularExpressions;

#region Structs

struct Pair

{

    public int X { get; set; }

    public int Y { get; set; }

    public Pair(int x, int y)

        : this()

    {

        X = x;

        Y = y;

    }

    public bool Equals(Pair p)

    {

        if ((p.X == this.X && p.Y == this.Y) || (p.X == this.Y && p.Y == this.X))

            return true;

        return false;

    }

    public override string ToString()

    {

        return String.Format("{0}, {1}, -1,", this.X, this.Y);

    }

}

#endregion

class Program

{

    static void Main()

    {

       //In the example attached we use directly the list pairs rather than group12 //because it would be very complicated to generate an example that contains all the //possible cases directly from here.

        #region Lists

        int[] a0 = { 1,3,3,-1, };

        int[] a1 = { 3,2,0,-1, };

        int[] a2 = { 1,0,2,-1, };

        int[] a3 = { 0,1,2, -1, };

        int[] a4 = { 4,2,0, -1, };

        int[] a5 = { 5,4,3, -1, };

        int[] a6 = { 4,3,2, -1, };

        int[] a7 = { 5,4,5, -1, };

        var group12 = new List<int[]> {  a0,    a1,    a2,    a3,    a4,    a5,    a6,    a7

        };

        var pairs = new List<Pair>();

        var edge13 = new List<int[]>();

        var pairsUsed = new List<int>();

        #endregion

         /* We need to exclude all isolated triangles from group12

           when generating the list of possible pairs.

           A triangle will be isolated if its vertices are not shared by

           any other triangle in group12. So we start by counting how many times

           each vertex occurs

         */

        #region count vertex

        var vertexCount = new Dictionary<int, int>();

        foreach (int[] a in group12)

        {

            foreach (int b in a)

            {

                if (vertexCount.ContainsKey(b))

                {

                    vertexCount[b]++;

                }

                else

                {

                    vertexCount.Add(b, 1);

                }

            }

        }

        #endregion

        #region get all possible pairs from group12 but exclude isolated triangles

        foreach (int[] a in group12)

        {

            if (vertexCount[a[0]] == 1 &&

                vertexCount[a[1]] == 1 &&

                vertexCount[a[2]] == 1) continue;

            pairs.Add(new Pair(a[0], a[1]));

            pairs.Add(new Pair(a[1], a[2]));

            pairs.Add(new Pair(a[2], a[0]));

        }

        #endregion

        #region remove duplicates leaving just unique pairs

        for (int i = 0; i < pairs.Count - 1; i++)

        {

            bool isDuplicated = false;

            for (int j = pairs.Count - 1; j > i; j--)

            {

                if (pairs[i].Equals(pairs[j]))

                {

                    pairs.RemoveAt(j);

                    isDuplicated = true;

                }

            }

            if (isDuplicated)

            {

                pairs.RemoveAt(i);

                i--;

            }

        }

        #endregion

        #region sort pairs by X and then by y

        pairs = (from p in pairs orderby p.X, p.Y select p).ToList();

        while (pairs.Count > 0)

        {

            pairsUsed.Clear();

            pairsUsed.Add(0);

            int next = pairs[0].Y;

            bool found;

            do

            {

                found = false;

                for (int j = 1; j < pairs.Count; j++)

                {

                    if (pairs[j].X == next && !pairsUsed.Contains(j)) //****

                    {

                        pairsUsed.Add(j);

                        next = pairs[j].Y;

                        found = true;

                        break;

                    }

                }

            }

            while (found && pairs[0].X != next);

            int[] a = new int[pairsUsed.Count + 2];

            for (int k = 0; k < pairsUsed.Count; k++)

            {

                a[k] = pairs[pairsUsed[k]].X;

            }

            a[a.Length - 2] = next;

            a[a.Length - 1] = -1;

            edge13.Add(a);

            pairsUsed.Sort();

            for (int l = pairsUsed.Count - 1; l >= 0; l--)

            {

                pairs.RemoveAt(pairsUsed[l]);

            }

        }

        #endregion

        #region printout edge13 list to file

        foreach (int[] a in edge13)

        {

            Console.WriteLine(String.Join(", ", a));

            Console.WriteLine();

        }

        #endregion

        Console.ReadKey();

    }

} 

Your help is greatly appreciated! Many thanks!!!

Hello Vulpes,

Many thanks for this. I have drawn the results obtained and I found out that the connectivity between the points was not correct using the previous code.  I have made some modifications in the code and now the connectivity is OK and List3 show positive values for the previous example. To test it I have decided to change the orientation of one of the two triangles in List2 to see if the lists are properly split into groups and it worked OK as well. Being happy with the result I have created a more complex example…  But unfortunately this example scuppered my initial joy. In this example all the triangles before the subdivision have the same orientation but after the subdivision they have mixed orientations.  At this point I see that the only robust solution we might have is the option of trying all the combinations to get the good orientation as you suggested.

Can you please help me implementing this option?

Below is the code with the modifications I have done (it includes the lists for the simple example with two triangles and different orientations –which works ok-) and also the lists for the "complex" example (which does not work).

Thank you very much for all your help, it is greatly appreciated.

using System;

using System.Collections.Generic;

struct Point

{

    public readonly double X;

    public readonly double Y;

    public readonly double Z;

    public Point(double x, double y, double z)

    {

        X = x;

        Y = y;

        Z = z;

    }

    public override string ToString()

    {

        return String.Format("{0} {1} {2},", X, Y, Z);

    }

    private static double Determinant(Point a, Point b, Point c)

    {

        return ((b.Y - a.Y) * (c.Z - a.Z) + (b.Z - a.Z) * (c.X - a.X) + (b.X - a.X) * (c.Y - a.Y) - (b.Z - a.Z) * (c.Y - a.Y) - (b.X - a.X) * (c.Z - a.Z) - (b.Y - a.Y) * (c.X - a.X));

    }

    public static bool CounterClockWise(Point a, Point b, Point c)

    {

        return Determinant(a, b, c) > 0.0;

    }

    public static bool ClockWise(Point a, Point b, Point c)

    {

        return Determinant(a, b, c) < 0.0;

    }

    public static bool Collinear(Point a, Point b, Point c)

    {

        return Determinant(a, b, c) == 0.0;

    }

    public static Point FromString(string p)

    {

        string[] items = p.Replace(",", "").Split(' ');

        double[] coords = new double[3];

        for (int i = 0; i < 3; i++) coords[i] = double.Parse(items[i]);

        return new Point(coords[0], coords[1], coords[2]);

    }

    public static double GetArea(Point a, Point b, Point c)

    {

        return Math.Abs(Determinant(a, b, c)) / 2.0;

    }

    //GET determinant value

    public static double GetDet(Point a, Point b, Point c)

    {

        return Determinant(a, b, c);

    }

    //

    public static Point Middle(Point a, Point b)

    {

        return new Point((a.X + b.X) / 2.0, (a.Y + b.Y) / 2.0, (a.Z + b.Z) / 2.0);

    }

    public static int GetCode(Point a, Point b, Point c)

    {

        if (CounterClockWise(a, b, c)) return 1;

        if (ClockWise(a, b, c)) return -1;

        return 0;

    }

}

class Program

{

    static void Main()

    {

        var list1 = new List<string>

      {

         "0 50 0,",

         "50 50 0,",

         "50 0 0,",

         "0 0 0,"

      };

        var list2 = new List<string>

      {

         "3, 0, 2,-1",

         "0, 2, 1,-1",

      };

        var list3 = new List<int> { 1, 1 };

        CleanLists(list1, list2, list3, null, false); // remove duplicates before sub-division

        // work out areas for each triangle in List2 and total area

        var areas = new List<double>();

        double totalArea = 0.0;

        foreach (string s in list2)

        {

            string[] items = s.Split(',');

            int[] indices = new int[3];

            for (int i = 0; i < 3; i++) indices[i] = int.Parse(items[i]);

            Point a = Point.FromString(list1[indices[0]]);

            Point b = Point.FromString(list1[indices[1]]);

            Point c = Point.FromString(list1[indices[2]]);

            double area = Point.GetArea(a, b, c);

            areas.Add(area);

            totalArea += area;

        }

        // print out areas

        Console.WriteLine("-- ALL GROUPS (BEFORE SUBDIVISION) --");

        Console.WriteLine("\nAREAS\n");

        for (int i = 0; i < areas.Count; i++) Console.WriteLine("{0,2} : {1}", i, areas[i]);

        Console.WriteLine();

        // work out average area of each triangle

        double origCount = list2.Count;

        double avgArea = totalArea / origCount;

        Console.WriteLine("Average area is {0}\n", avgArea);

        //determinant values

        var dets = new List<double>();

        double totalDet = 0.0;

        foreach (string s in list2)

        {

            string[] items = s.Split(',');

            int[] indices = new int[3];

            for (int i = 0; i < 3; i++) indices[i] = int.Parse(items[i]);

            Point a = Point.FromString(list1[indices[0]]);

            Point b = Point.FromString(list1[indices[1]]);

            Point c = Point.FromString(list1[indices[2]]);

            double det = Point.GetDet(a, b, c);

            dets.Add(det);

            totalDet+= det;

        }

        // print out det value

        Console.WriteLine("-- ALL GROUPS (BEFORE SUBDIVISION) --");

        Console.WriteLine("\nDETERMINANT\n");

        for (int i = 0; i < dets.Count; i++) Console.WriteLine("{0,2} : {1}", i, dets[i]);

        Console.WriteLine();

        // subdivide the triangles whose area is greater than average until it is no longer greater than average

        for (int i = 0; i < list2.Count; i++)

        {

            if (areas[i] > 0.5 * avgArea) //****** (remember to remove 0.5)

            {

                Subdivide(i, areas[i], list1, list2, list3, areas);

                --i;

            }

        }

        CleanLists(list1, list2, list3, areas, true); // remove duplicates after sub-division

        // print out all lists after subdivision

        Console.WriteLine("-- ALL GROUPS (AFTER SUBDIVISION) --");

        Console.WriteLine("\nLIST1\n");

        for (int i = 0; i < list1.Count; i++) Console.WriteLine("{0,2} : {1}", i, list1[i]);

        Console.WriteLine("\nLIST2\n");

        for (int i = 0; i < list2.Count; i++) Console.WriteLine("{0,2} : {1}", i, list2[i]);

        Console.WriteLine("\nLIST3\n");

        for (int i = 0; i < list3.Count; i++) Console.WriteLine("{0,2} : {1}", i, list3[i]);

        Console.WriteLine("\nAREAS\n");

        for (int i = 0; i < areas.Count; i++) Console.WriteLine("{0,2} : {1}", i, areas[i]);

        Console.WriteLine();

        var group11 = new List<string>(); // group 1, list1

        var group12 = new List<string>(); // group 1, list2

        var group21 = new List<string>(); // group 2, list1

        var group22 = new List<string>(); // group 2, list2

        var group31 = new List<string>(); // group 3, list1

        var group32 = new List<string>(); // group 2, list2

        // split up the data into the appropriate groups

        for (int i = 0; i < Math.Min(list2.Count, list3.Count); i++)

        {

            switch (list3[i])

            {

                case 1: // counterclockwise

                    group12.Add(list2[i]);

                    break;

                case -1: // clockwise  

                    group22.Add(list2[i]);

                    break;

                case 0: // collinear 

                    group32.Add(list2[i]);

                    break;

            }

        }

        group11 = ProcessGroup(list1, group12);

        group21 = ProcessGroup(list1, group22);

        group31 = ProcessGroup(list1, group32);

        // print out groups

        PrintGroup(1, group11, group12);

        PrintGroup(2, group21, group22);

        PrintGroup(3, group31, group32);

        Console.ReadKey();

    }

    static List<string> ProcessGroup(List<string> points, List<string> connections)

    {

        // figure out which points are used in the group and store them

        int[,] indices = new int[connections.Count, 3];

        var allIndices = new List<int>();

        for (int i = 0; i < connections.Count; i++)

        {

            string[] items = connections[i].Split(',');

            indices[i, 0] = int.Parse(items[0]);

            indices[i, 1] = int.Parse(items[1]);

            indices[i, 2] = int.Parse(items[2]);

            if (!allIndices.Contains(indices[i, 0])) allIndices.Add(indices[i, 0]);

            if (!allIndices.Contains(indices[i, 1])) allIndices.Add(indices[i, 1]);

            if (!allIndices.Contains(indices[i, 2])) allIndices.Add(indices[i, 2]);

        }

        allIndices.Sort();

        var dict = new Dictionary<int, int>();

        for (int i = 0; i < allIndices.Count; i++) dict.Add(allIndices[i], i);

        for (int i = 0; i < connections.Count; i++)

        {

            for (int j = 0; j < 3; j++) indices[i, j] = dict[indices[i, j]]; // remap actual indices to 0, 1, 2 etc

            connections[i] = String.Format("{0}, {1}, {2},-1", indices[i, 0], indices[i, 1], indices[i, 2]);

        }

        var groupPoints = new List<string>();

        foreach (int index in allIndices) groupPoints.Add(points[index]);

        return groupPoints;

    }

    static void PrintGroup(int num, List<string> points, List<string> connections)

    {

        Console.WriteLine("-- GROUP {0} --", num);

        Console.WriteLine("\nLIST1\n");

        foreach (string point in points) Console.WriteLine(point);

        Console.WriteLine("\nLIST2\n");

        foreach (string connection in connections) Console.WriteLine(connection);

        Console.WriteLine();

    }

    //NEW SUBDIVIDE CLASS (22/10/2014). KEEPS PROPER ORIENTATION

    static void Subdivide(int index, double area, List<string> points, List<string> triangles, List<int> codes, List<double> areas)

    {

        string[] items = triangles[index].Split(',');

        int[] indices = new int[6];

        for (int i = 0; i < 3; i++) indices[i] = int.Parse(items[i]);

        Point v0 = Point.FromString(points[indices[0]]);

        Point v1 = Point.FromString(points[indices[1]]);

        Point v2 = Point.FromString(points[indices[2]]);

        Point v3 = Point.Middle(v0, v1); // v01

        Point v4 = Point.Middle(v1, v2); // v12

        Point v5 = Point.Middle(v2, v0); // v20

        int count = points.Count;

        points.Add(v3.ToString());

        points.Add(v4.ToString());

        points.Add(v5.ToString());

        indices[3] = count;

        indices[4] = count + 1;

        indices[5] = count + 2;

        triangles.Insert(index + 1, String.Format("{0}, {1}, {2},-1", indices[0], indices[5], indices[3]));

        triangles.Insert(index + 2, String.Format("{0}, {1}, {2},-1", indices[3], indices[5], indices[4]));

        triangles.Insert(index + 3, String.Format("{0}, {1}, {2},-1", indices[3], indices[4], indices[1]));

        triangles.Insert(index + 4, String.Format("{0}, {1}, {2},-1", indices[5], indices[2], indices[4]));

        triangles.RemoveAt(index);

        area /= 4.0;

        areas.Insert(index + 1, area);

        areas.Insert(index + 2, area);

        areas.Insert(index + 3, area);

        areas.Insert(index + 4, area);

        areas.RemoveAt(index);

        codes.Insert(index + 1, Point.GetCode(Point.FromString(points[indices[0]]), Point.FromString(points[indices[5]]), Point.FromString(points[indices[3]])));

        codes.Insert(index + 2, Point.GetCode(Point.FromString(points[indices[3]]), Point.FromString(points[indices[5]]), Point.FromString(points[indices[4]])));

        codes.Insert(index + 3, Point.GetCode(Point.FromString(points[indices[3]]), Point.FromString(points[indices[4]]), Point.FromString(points[indices[1]])));

        codes.Insert(index + 4, Point.GetCode(Point.FromString(points[indices[5]]), Point.FromString(points[indices[2]]), Point.FromString(points[indices[4]])));

        codes.RemoveAt(index);

    }

    static bool AreTrianglesEqual(string triangle1, string triangle2)

    {

        string[] items1 = triangle1.Split(',');

        int[] vertices1 = new int[3];

        for (int i = 0; i < 3; i++) vertices1[i] = int.Parse(items1[i]);

        Array.Sort(vertices1);

        string[] items2 = triangle2.Split(',');

        int[] vertices2 = new int[3];

        for (int i = 0; i < 3; i++) vertices2[i] = int.Parse(items2[i]);

        Array.Sort(vertices2);

        if ((vertices1[0] == vertices2[0]) && (vertices1[1] == vertices2[1]) && (vertices1[2] == vertices2[2])) return true;

        return false;

    }

    static void CleanLists(List<string> list1, List<string> list2, List<int> list3, List<double> areas, bool afterSubdivision)

    {

        string ab = afterSubdivision ? "After" : "Before";

        // check for duplicates in list1

        int[] remappings = new int[list1.Count];

        var duplicates = new List<int>();

        for (int i = 0; i < list1.Count; i++) remappings[i] = i;

        for (int i = 0; i < list1.Count - 1; i++)

        {

            if (remappings[i] != i) continue;

            for (int j = i + 1; j < list1.Count; j++)

            {

                if (list1[i] == list1[j])

                {

                    duplicates.Add(j);

                    remappings[j] = i;

                }

            }

        }

        if (duplicates.Count > 0)

        {

            var reorderings = new int[list1.Count];

            for (int i = 0; i < list1.Count; i++) reorderings[i] = i;

            duplicates.Sort();

            foreach (int dup in duplicates)

            {

                reorderings[dup] = -1;

            }

            for (int i = list1.Count - 1; i >= 0; i--)

            {

                if (reorderings[i] == -1 && i < list1.Count - 1)

                {

                    for (int j = i + 1; j < list1.Count; j++)

                    {

                        if (reorderings[j] != -1) reorderings[j]--;

                    }

                }

            }

            for (int i = 0; i < list1.Count; i++)

            {

                remappings[i] = reorderings[remappings[i]];

            }

            // now delete duplicates from list1

            for (int i = duplicates.Count - 1; i >= 0; i--)

            {

                list1.RemoveAt(duplicates[i]);

            }

            // finally remap vertices in list2

            for (int i = 0; i < list2.Count; i++)

            {

                string[] items = list2[i].Split(',');

                int[] indices = new int[3];

                for (int j = 0; j < 3; j++)

                {

                    indices[j] = int.Parse(items[j]);

                    indices[j] = remappings[indices[j]];

                }

                list2[i] = String.Join(", ", indices) + ",-1";

            }

            // check it worked        

            Console.WriteLine(ab + " sub-division, duplicates were found and removed from list1 and list2 remapped as follows\n");

            foreach (string s in list1) Console.WriteLine(s);

            Console.WriteLine();

            foreach (string s in list2) Console.WriteLine(s);

            Console.WriteLine();

        }

        else

        {

            Console.WriteLine(ab + " sub-division, no duplicates found in list1\n");

        }

        // now check for duplicates in list2

        duplicates.Clear();

        for (int i = 0; i < list2.Count - 1; i++)

        {

            if (duplicates.Contains(i)) continue;

            for (int j = i + 1; j < list2.Count; j++)

            {

                if (duplicates.Contains(j)) continue;

                if (AreTrianglesEqual(list2[i], list2[j]))

                {

                    duplicates.Add(j);

                }

            }

        }

        if (duplicates.Count > 0)

        {

            duplicates.Sort();

            // delete duplicates from list2 and the corresponding entry in list3 and (if after sub-division) areas

            for (int i = duplicates.Count - 1; i >= 0; i--)

            {

                list2.RemoveAt(duplicates[i]);

                list3.RemoveAt(duplicates[i]);

                if (afterSubdivision) areas.RemoveAt(duplicates[i]);

            }

            // check it worked

            Console.WriteLine(ab + " sub-division, duplicates were found and removed from list2 and list3 adjusted as follows\n");

            foreach (string s in list2) Console.WriteLine(s);

            Console.WriteLine();

            foreach (int i in list3) Console.WriteLine(i);

            Console.WriteLine();

        }

        else

        {

            Console.WriteLine(ab + " sub-division, no duplicates found in list2\n");

        }

    }

}

THE LISTS FOR THE COMPLEX EXAMPLE:

var list1 = new List

      {

"20 -20 20,",

"20 -20 -20,",

"20 -9.2388 3.82683,",

"20 -7.07107 7.07107,",

"20 -3.82683 9.2388,",

"20 6.12323e-016 10,",

"20 20 20,",

"20 20 -20,",

"20 -1.83697e-015 -10,",

"20 -3.82683 -9.2388,",

"20 -7.07107 -7.07107,",

"20 -9.2388 -3.82683,",

"20 -10 1.22465e-015,",

"20 9.2388 3.82683,",

"20 10 0,",

"20 9.2388 -3.82683,",

"20 7.07107 -7.07107,",

"20 3.82683 -9.2388,",

"20 3.82683 9.2388,",

"20 7.07107 7.07107,",   

      };

        var list2 = new List

      {

"0,1,2,-1",

"0,2,3,-1",

"0,3,4,-1",

"0,4,5,-1",

"0,5,6,-1",

"1,7,8,-1",

"1,8,9,-1",

"1,9,10,-1",

"1,10,11,-1",

"1,11,12,-1",

"1,12,2,-1",

"7,13,14,-1",

"7,14,15,-1",

"7,15,16,-1",

"7,16,17,-1",

"7,17,8,-1",

"6,5,18,-1",

"6,18,19,-1",

"6,19,13,-1",

"6,13,7,-1",        

      };

        var list3 = new List { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };

Hello Vulpes,

I came out with an idea that might work in all cases (see attached). If you see a problem with this method I would have no problem about going with the combinations option you mentioned earlier.

Let me know what you think.

Thank you!