C#•4mo ago

Grouping adjacent XYZ points, no idea how to go about this

Let's assume I have an array of point: 0,0,0 0,0,1 0,1,0 1,0,0 2,2,2 5,5,5 5,5,6 Both groups of points should result in 1 XYZ coordinates each, I can't figure out for my life how to do this. (No Screenshots as I have nothing)

26 Replies

SamwiseTheBrave•4mo ago

just to be clear: you want to determine, if two points are adjacent?

Mastalt•4mo ago

not only 2, it can stretch out, so a line form 0,0,0 to 0,6,0 would be a single point

SamwiseTheBrave•4mo ago

I'm afraid I don't understand, what do you mean. How a line can be a single point?

Mastalt•4mo ago

That's the result I'm trying to get, so any "cluster" of point which are linked to one another result in a single coordinate (can be wherever in the group(middle, bottom, etc.)) you can think of it as legos, all legos which are connected to one another represent a structure, but 2 set of legos are 2 different structure

SamwiseTheBrave•4mo ago

so: you want to group points that are connected in some way, and then calculate a common XYZ coordinate for them? The second thing can be done by calculating an average of all positions of points.

Mastalt•4mo ago

yes that is true, but i stil dont know how to group points that way

SamwiseTheBrave•4mo ago

are they on some grid, like 1x1x1 grid?

Mastalt•4mo ago

yes, all are whole coordinate (no floating points)

SamwiseTheBrave•4mo ago

Wait a sec, I'm gonna do a quick sketch in 2D

SamwiseTheBrave•4mo ago

A simple example in 2D, is it what you mean by "adjacent"?

SamwiseTheBrave•4mo ago

(group of adjacent points marked red) points here are adjacent on the X, on the Y and diagonally. meaning that two points are adjacent when distance between them is equal to 1 because grid is 1x1 ofc we can't measure this distance with good old Pythagorean formula because diagonal of a square isn't equal in length to the side instead, you have to substract two points positions and get the abs of the result then, if result X, Y and Z are smaller or equal to 1, points are adjacent

SamwiseTheBrave•4mo ago

Mastalt•4mo ago

hmm I see, I'll try something like that, but then, if lets say 0 1 1 1 0 2 1 2 2 0 They would be adjacent, but more than 1 apart (assuming we start from 0 2) so i would have to do it recursivly?

SamwiseTheBrave•4mo ago

0, 2 isn't adjacent to 2, 0 ~~but yeah~~ 1, 2 isn't either

Mastalt•4mo ago

but it is adjacent to 1,1 which is adjacent to 2,0

SamwiseTheBrave•4mo ago

ah, yes good point I understand now what you mean

Mastalt•4mo ago

yeah i had trouble finding the right explanantion lol

SamwiseTheBrave•4mo ago

let me think about it for a minute yes, I think some recursion is needed I haven't tested it, but I would do it like this: 1. take a point 2. calculate it's neighbours 3. repeat this for each neighbour

Mastalt•4mo ago

I have over 2m points 😰 Thats why i wanted to hopefully do a 1 liner with linQ, but if it cant be helped...

SamwiseTheBrave•4mo ago

Do you need to perform this operation once? Or like every frame? In second case it can indeed be a bit problematic

Mastalt•4mo ago

I need to do it once and inprt to database, then i can just access from there But im on a time crunch lol

SamwiseTheBrave•4mo ago

I wrote a simple method, looks like it works, I just need to test it a little more. I will post it here if it works.

Mastalt•4mo ago

Thx a lot, you're a life saver

SamwiseTheBrave•4mo ago

        Point3D[] GetCluster(Point3D originPoint, Point3D[] allPoints, List<Point3D> alreadyFound)
        {
            Point3D[] adjacent = allPoints.Where(p3d => !alreadyFound.Contains(p3d) &&
            Math.Abs(originPoint.X - p3d.X) <= 1 &&
            Math.Abs(originPoint.Y - p3d.Y) <= 1 &&
            Math.Abs(originPoint.Z - p3d.Z) <= 1
            ).ToArray();

            if (adjacent.Length == 0)
                return alreadyFound.ToArray();

            List<Point3D[]> subClusters = new List<Point3D[]>();

            alreadyFound.AddRange(adjacent);

            foreach (Point3D p3D in adjacent)
            {
                subClusters.Add(GetCluster(p3D, allPoints, alreadyFound));
            }

            List<Point3D> output = new List<Point3D>();

            for (int i = 0; i < subClusters.Count; i++)
            {
                for (int j = 0; j < subClusters[i].Length; j++)
                {
                    output.Add(subClusters[i][j]);
                }
            }

            return output.ToArray();
        }

        Point3D[] GetCluster(Point3D originPoint, Point3D[] allPoints, List<Point3D> alreadyFound)
        {
            Point3D[] adjacent = allPoints.Where(p3d => !alreadyFound.Contains(p3d) &&
            Math.Abs(originPoint.X - p3d.X) <= 1 &&
            Math.Abs(originPoint.Y - p3d.Y) <= 1 &&
            Math.Abs(originPoint.Z - p3d.Z) <= 1
            ).ToArray();

            if (adjacent.Length == 0)
                return alreadyFound.ToArray();

            List<Point3D[]> subClusters = new List<Point3D[]>();

            alreadyFound.AddRange(adjacent);

            foreach (Point3D p3D in adjacent)
            {
                subClusters.Add(GetCluster(p3D, allPoints, alreadyFound));
            }

            List<Point3D> output = new List<Point3D>();

            for (int i = 0; i < subClusters.Count; i++)
            {
                for (int j = 0; j < subClusters[i].Length; j++)
                {
                    output.Add(subClusters[i][j]);
                }
            }

            return output.ToArray();
        }

so it looks like this method works I tested it on a set of points which was basically two cubes and it returned the proper result. However, test it yourself, if you can. Point3D is just a simple struct with three properties, X, Y and Z Nothing fancy. @Mastalt

Mastalt•4mo ago

this is exactly what I needed, thank you very much 🙏

SamwiseTheBrave•4mo ago

Glad I could help, I hope it works 😉 @Mastalt also, this method is unoptimized and therefore quite slow for 2M points it can take up to 20 minutes or even longer, considering that time complexity of this algorithm isn't linear I don't have time to do this at the moment, but you could try (instead of using this Where()) sorting points by distance to the current point and then taking first 8 points from sorted collection and checking if they're adjacent to the current point. Edit: just tested it, it's even slower OK, nevermind I'm just silly This method is very fast, my code was just running extremly slow because of my naive random point generation loop

Gaming

Programming

Grouping adjacent XYZ points, no idea how to go about this