Unity实现DBSCAN
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class TestDBSCAN : MonoBehaviour
{
private List<GameObject> goList = new List<GameObject>();
private List<Vector3> posList = new List<Vector3>();
// Start is called before the first frame update
void Start()
{
//创建随机点
for (int j = 0; j < 5; j++)
{
for (int i = 0; i < 100; i++)
{
GameObject go = GameObject.CreatePrimitive(PrimitiveType.Sphere);
go.transform.localScale = Vector3.one * 0.1f;
go.transform.position = Random.insideUnitSphere * 5;
go.transform.position += Vector3.one * j * 10;
goList.Add(go);
posList.Add(go.transform.position);
}
}
//执行算法
int[] result = DBSCAN.Cluster(posList, 3, 4);
Dictionary<int, List<GameObject>> dic = new Dictionary<int, List<GameObject>>();
//将算法结果分组
for (int i = 0; i < result.Length; i++)
{
int key = result[i];
if (dic.ContainsKey(key))
{
dic[key].Add(goList[i]);
}
else
{
List<GameObject> tempList = new List<GameObject>();
tempList.Add(goList[i]);
dic.Add(key, tempList);
}
}
//对GameObject进行分组
foreach (var item in dic)
{
GameObject goParent = new GameObject();
goParent.name = item.Key.ToString();
foreach (var item2 in item.Value)
{
item2.transform.SetParent(goParent.transform);
}
}
}
}
public class DBSCAN
{
/// <summary>
///
/// </summary>
/// <param name="points">点的集合</param>
/// <param name="minPts">最小个数</param>
/// <param name="eps">最小半径</param>
/// <returns></returns>
public static int[] Cluster(List<Vector3> points, int minPts, int eps)
{
int n = points.Count;
int[] labels = new int[n];
int clusterId = 0;
// 初始化所有点的标签为-1，表示未分类
for (int i = 0; i < n; i++)
{
labels[i] = -1;
}
// 遍历所有点
for (int i = 0; i < n; i++)
{
Vector3 p = points[i];
// 如果点已经分类，则跳过
if (labels[i] != -1)
{
continue;
}
// 找到p的邻居点
List<Vector3> neighbors = GetNeighbors(points, p, eps);
// 如果邻居点数量小于minPts，则将p标记为噪声点
if (neighbors.Count < minPts)
{
labels[i] = 0;
continue;
}
// 新建一个簇
clusterId++;
labels[i] = clusterId;
// 扩展簇
ExpandCluster(points, labels, neighbors, clusterId, eps, minPts);
}
return labels;
}
public static void ExpandCluster(List<Vector3> points, int[] labels, List<Vector3> neighbors, int clusterId, int eps, int minPts)
{
// 遍历邻居点
for (int i = 0; i < neighbors.Count; i++)
{
Vector3 q = neighbors[i];
int index = points.IndexOf(q);
// 如果邻居点未分类，则将其加入簇中
if (labels[index] == -1)
{
labels[index] = clusterId;
// 找到q的邻居点
List<Vector3> qNeighbors = GetNeighbors(points, q, eps);
// 如果邻居点数量大于等于minPts，则将其加入扩展簇的邻居点列表中
if (qNeighbors.Count >= minPts)
{
neighbors.AddRange(qNeighbors);
}
}
// 如果邻居点已经被分类为噪声点，则将其重新分类到当前簇中
else if (labels[index] == 0)
{
labels[index] = clusterId;
}
}
}
private static List<Vector3> GetNeighbors(List<Vector3> list, Vector3 corePoint, float radius)
{
List<Vector3> result = new List<Vector3>();
foreach (var p in list)
{
if (Vector3.Distance(corePoint, p) <= radius)
result.Add(p);
}
return result;
}
}