Matching equal point sets

[Petras_Vestartas]

Hi,

I am doing fairly simple point matching, two know which point id of the second set is equal to the first set.

1. Two sets contains the same amount of points
2. The order of points differs
3. Both point sets points are at exactly same positions.

I am surprised that RTree search is faster than doing Dictionary search where key is the XYZ coordinates of points:

        Dictionary<string, int> cpIDDict = new Dictionary<string, int>(ptsPlines0.Length);
        for (int i = 0; i < ptsPlines0.Length; i++) {
            cpIDDict.Add(Math.Round(ptsPlines0[i].X, 3) + ";" + Math.Round(ptsPlines0[i].Y, 3) + ";" + Math.Round(ptsPlines0[i].Z, 3), i);
        }
        int[] cpID = new int[ptsPlines0.Length];
        for (int i = 0; i < ptsPlines0.Length; i++) {
            cpID[i] = cpIDDict[Math.Round(ptsMesh[i].X, 3) + ";" + Math.Round(ptsMesh[i].Y, 3) + ";" + Math.Round(ptsMesh[i].Z, 3)];
        }

The RTree method I am using is this:

        public static int[] RTreeSearchIDOnlyOne(Point3d[] pointsToSearchFrom, Point3d[] needles, double dist) {

            //If not empty
            if (pointsToSearchFrom.Length == 0 || needles.Length == 0)
                return Enumerable.Repeat(-1, pointsToSearchFrom.Length).ToArray();

            //Search
            IEnumerable<int[]> found = RTree.Point3dClosestPoints(pointsToSearchFrom, needles, dist);


            int[] result = new int[needles.Length];
            int count = 0;
            foreach (var item in found) {
                result[count++] = item.Length > 0 ? item[0] : -1;
            }

            return result;
        }

Do you know other fast search methods to find points id on the same locations?
I think there is a better and faster way to do this, but I do not know one.

SetA

SetB

[DanielPiker]

Could you maybe use an IEqualityComparer here?
If you know you’ve got a one-to-one correspondence, and the positions of the corresponding points are exactly identical, then you should be able to match just by HashCode.

[Petras_Vestartas]

Would it be possible to show how to use IEqualityComparer?

[DanielPiker]

Actually, even simpler could be just to sort using the default point comparer:

private void RunScript(List<Point3d> x, List<Point3d> y, ref object A, ref object B)
  {
    Point3d[] xArray = x.ToArray();
    int[] xIndex = new int[xArray.Length];
    Point3d[] yArray = y.ToArray();
    int[] yIndex = new int[yArray.Length];
    for(int i = 0;i < xArray.Length;i++)xIndex[i] = yIndex[i] = i;
    Array.Sort(xArray, xIndex);
    Array.Sort(yArray, yIndex);
    Array.Sort(yIndex, xIndex);
    A = xIndex;    
  }

[Petras_Vestartas]

@DanielPiker

private void RunScript(List<Point3d> x, List<Point3d> y, ref object A, ref object B)
  {
    Point3d[] xArray = x.ToArray();
    int[] xIndex = new int[xArray.Length];
    Point3d[] yArray = y.ToArray();
    int[] yIndex = new int[yArray.Length];
    for(int i = 0;i < xArray.Length;i++)xIndex[i] = yIndex[i] = i;
    Array.Sort(xArray, xIndex);
    Array.Sort(yArray, yIndex);
    Array.Sort(yIndex, xIndex);
    A = xIndex;    
  }

That is much faster than RTree, thank you.

Would it be intersesting to know how the Point3D method public int CompareTo(Point3d other);
looks like. Is this method is used when Array.Sort function is called?

[DanielPiker]

It uses this:

Point3d.CompareTo Method

0: if this is identical to other

-1: if this.X < other.X

-1: if this.X == other.X and this.Y < other.Y

-1: if this.X == other.X and this.Y == other.Y and this.Z < other.Z

+1: otherwise.

[Petras_Vestartas]

Thank you