Say, I have a point cloud of 30,000 points in 3D. I want to count the neighbors for each point at a cut-off distance.
the following code always shows the neighbor count as 1 no matter what the coordinate values are:
using System;
using System.Collections.Generic;
public class Point3D
{
public double X { get; set; } // X-coordinate of the point
public double Y { get; set; } // Y-coordinate of the point
public double Z { get; set; } // Z-coordinate of the point
public Point3D(double x, double y, double z)
{
X = x;
Y = y;
Z = z;
}
public double GetDistance(Point3D point)
{
double dx = X - point.X; // Calculate the difference in X-coordinates
double dy = Y - point.Y; // Calculate the difference in Y-coordinates
double dz = Z - point.Z; // Calculate the difference in Z-coordinates
return Math.Sqrt(dx * dx + dy * dy + dz * dz); // Calculate and return the Euclidean distance between two 3D points
}
public override int GetHashCode()
{
int hash = 17; // Initialize the hash value with an arbitrary prime number
// Update the hash value using the X, Y, and Z coordinates
hash = hash * 31 + X.GetHashCode();
hash = hash * 31 + Y.GetHashCode();
hash = hash * 31 + Z.GetHashCode();
return hash; // Return the calculated hash value
}
}
public static class NeighborCounter
{
private static Dictionary<int, HashSet<Point3D>> hashBuckets = new Dictionary<int, HashSet<Point3D>>();
private static void AddPoint(Point3D point, int hash)
{
if (!hashBuckets.TryGetValue(hash, out HashSet<Point3D> bucket))
{
bucket = new HashSet<Point3D>(); // Create a new HashSet for the hash if it doesn't exist
hashBuckets[hash] = bucket; // Add the bucket to the hashBuckets dictionary
}
bucket.Add(point); // Add the point to the corresponding bucket
}
private static HashSet<Point3D> GetNeighbors(Point3D point, int hash)
{
if (hashBuckets.TryGetValue(hash, out HashSet<Point3D> neighbors))
{
return neighbors; // Return the neighbors for the given hash
}
return null; // Return null if there are no neighbors for the given hash
}
/*
numHashes determines the range of neighboring hash values to consider when searching for neighboring points. It affects the scope of the search by specifying how many neighboring hash values, in both directions, should be considered.
It helps identify potential candidate points within a certain range of hash values.
*/
public static Dictionary<Point3D, int> Search(Point3D[] points, int numHashes, double cutOffDistance)
{
/*
By processing each point and adding it to the appropriate hash bucket, this loop organizes the points into separate buckets based on their hash values.
*/
foreach (Point3D point in points)
{
int hash = point.GetHashCode(); // Calculate the hash value for the point
AddPoint(point, hash); // Add the point to the corresponding hash bucket
}
Dictionary<Point3D, int> pointNeighbors = new Dictionary<Point3D, int>();
foreach (Point3D point in points)
{
int neighborCount = 0; // Initialize the neighbor count for the current point
int hash = point.GetHashCode(); // Calculate the hash value for the point
for (int i = hash - numHashes; i <= hash + numHashes; i++)
{
var neighbors = GetNeighbors(point, i); // Retrieve the neighbors for the given hash
if (neighbors != null)
{
foreach (Point3D neighbor in neighbors)
{
double distance = point.GetDistance(neighbor); // Calculate the distance between the current point and its neighbor
if (distance <= cutOffDistance) // Check if the distance is within the cutoff distance
{
neighborCount++; // Increment the neighbor count
}
}
}
}
pointNeighbors[point] = neighborCount; // Store the neighbor count for the current point
}
return pointNeighbors; // Return the dictionary containing the points and their neighbor counts
}
}
public class Program
{
public static void Main(string[] args)
{
Point3D[] points = new Point3D[]
{
new Point3D(0, 0, 0),
new Point3D(0, 0, 1),
new Point3D(1, 0, 0),
new Point3D(0, 1, 0),
new Point3D(1, 1, 0),
new Point3D(2, 2, 0)
};
double cutOffDistance = 1.5; // The maximum distance between two points for them to be considered neighbors
int numHashes = 100; // The number of neighboring hashes to consider
Dictionary<Point3D, int> pointNeighbors = NeighborCounter.Search(points, numHashes, cutOffDistance);
foreach (var kvp in pointNeighbors)
{
Console.WriteLine($"Point ({kvp.Key.X}, {kvp.Key.Y}, {kvp.Key.Z}) has {kvp.Value} neighbors within the cutoff distance.");
}
Console.ReadKey();
}
}
What is the bug in the code?
Here is another version using Morton's hashing:
using System;
using System.Collections.Generic;
public class Point3D
{
public double X { get; set; } // X-coordinate of the point
public double Y { get; set; } // Y-coordinate of the point
public double Z { get; set; } // Z-coordinate of the point
public Point3D(double x, double y, double z)
{
X = x;
Y = y;
Z = z;
}
public double GetDistance(Point3D point)
{
double dx = X - point.X; // Calculate the difference in X-coordinates
double dy = Y - point.Y; // Calculate the difference in Y-coordinates
double dz = Z - point.Z; // Calculate the difference in Z-coordinates
return Math.Sqrt(dx * dx + dy * dy + dz * dz); // Calculate and return the Euclidean distance between two 3D points
}
public ulong GetMortonHash()
{
ulong xBits = Part1By1((ulong)X);
ulong yBits = Part1By1((ulong)Y);
ulong zBits = Part1By1((ulong)Z);
return xBits * 4 + yBits * 2 + zBits;
}
private ulong Part1By1(ulong value)
{
value &= 0x00000000FFFFFFFF; // Discard upper 32 bits (if any)
value = (value ^ (value << 16)) & 0x0000FFFF0000FFFF;
value = (value ^ (value << 8)) & 0x00FF00FF00FF00FF;
value = (value ^ (value << 4)) & 0x0F0F0F0F0F0F0F0F;
value = (value ^ (value << 2)) & 0x3333333333333333;
value = (value ^ (value << 1)) & 0x5555555555555555;
return value;
}
}
public static class NeighborCounter
{
private static Dictionary<ulong, HashSet<Point3D>> hashBuckets
= new Dictionary<ulong, HashSet<Point3D>>();
private static void AddPoint(Point3D point, ulong hash)
{
if (!hashBuckets.TryGetValue(hash, out HashSet<Point3D> bucket))
{
bucket = new HashSet<Point3D>(); // Create a new HashSet for the hash if it doesn't exist
hashBuckets[hash] = bucket; // Add the bucket to the hashBuckets dictionary
}
bucket.Add(point); // Add the point to the corresponding bucket
}
private static HashSet<Point3D> GetNeighbors(Point3D point, ulong hash)
{
if (hashBuckets.TryGetValue(hash, out HashSet<Point3D> neighbors))
{
return neighbors; // Return the neighbors for the given hash
}
return null; // Return null if there are no neighbors for the given hash
}
/*
numHashes determines the range of neighboring hash values to consider when searching for neighboring points. It affects the scope of the search by specifying how many neighboring hash values, in both directions, should be considered.
It helps identify potential candidate points within a certain range of hash values.
*/
public static Dictionary<Point3D, int> Search(Point3D[] points, ulong numHashes, double cutOffDistance)
{
/*
By processing each point and adding it to the appropriate hash bucket, this loop organizes the points into separate buckets based on their hash values.
*/
foreach (Point3D point in points)
{
ulong hash = point.GetMortonHash(); // Calculate the hash value for the point
AddPoint(point, hash); // Add the point to the corresponding hash bucket
}
Dictionary<Point3D, int> pointNeighbors = new Dictionary<Point3D, int>();
foreach (Point3D point in points)
{
int neighborCount = 0; // Initialize the neighbor count for the current point
ulong hash = point.GetMortonHash(); // Calculate the hash value for the point
for (ulong i = hash - numHashes; i <= hash + numHashes; i++)
{
var neighbors = GetNeighbors(point, (ulong)i); // Retrieve the neighbors for the given hash
if (neighbors != null)
{
foreach (Point3D neighbor in neighbors)
{
double distance = point.GetDistance(neighbor); // Calculate the distance between the current point and its neighbor
if (distance <= cutOffDistance) // Check if the distance is within the cutoff distance
{
neighborCount++; // Increment the neighbor count
}
}
}
}
pointNeighbors[point] = neighborCount; // Store the neighbor count for the current point
}
return pointNeighbors; // Return the dictionary containing the points and their neighbor counts
}
}
public class Program
{
public static void Main(string[] args)
{
Point3D[] points = new Point3D[]
{
new Point3D(0, 0, 0),
new Point3D(0, 0, 1),
new Point3D(1, 0, 0),
new Point3D(0, 1, 0),
new Point3D(1, 1, 0),
new Point3D(2, 2, 0)
};
double cutOffDistance = 1.5; // The maximum distance between two points for them to be considered neighbors
ulong numHashes = 100; // The number of neighboring hashes to consider
Dictionary<Point3D, int> pointNeighbors = NeighborCounter.Search(points, numHashes, cutOffDistance);
foreach (var kvp in pointNeighbors)
{
Console.WriteLine($"Point ({kvp.Key.X}, {kvp.Key.Y}, {kvp.Key.Z}) has {kvp.Value} neighbors within the cutoff distance.");
}
Console.ReadKey();
}
}
This also doesn't behave as intended.