I am trying to cluster(group) every circle that's uninterrupted overlapping (connected) to each other how could I do that? (preferably in a pretty efficient way).
(I have messed around trying to write some recursive functions but haven't gotten anything to work.)
I have created a VS project to visualize the problem.
Generates Random circles.
How the clustering currently works:
(its only looks at what circle is overlapping that specific circle not all that is connected)
How it should look if its working
(separate clusters for all connecting circles)
CODE: (C#)
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
// Cluster overlapping circles
// Patrik Fröhler
// www.patan77.com
// 2017-08-14
namespace circleGroup
{
struct circle // the circle "object"
{
public float[] pos;
public int radius;
public Color color;
public int id;
public float x
{
get { return pos[0]; }
set { pos[0] = value; }
}
public float y
{
get { return pos[1]; }
set { pos[1] = value; }
}
}
public partial class Form1 : Form
{
DB _DB = new DB(); // "Global Database"
public Form1()
{
InitializeComponent();
}
private static circle createCircle(float _x = 0, float _y = 0, int _radius = 1, Color? _color = null, int _id = -1) // creates a circle
{
circle tmpCircle = new circle() { pos = new float[2], x = _x, y = _y, radius = _radius, id = _id };
tmpCircle.color = _color ?? Color.Black;
return (tmpCircle);
}
private circle[] genRngCircles(int _n) // generates an array of random circles
{
Random rng = new Random();
circle tmpC;
circle[] tmpCarr = new circle[_n];
for (int i = 0; i < _n; i++)
{
tmpC = createCircle();
tmpC.radius = rng.Next(10, 75);
tmpC.x = rng.Next(tmpC.radius, (512 - tmpC.radius));
tmpC.y = rng.Next(tmpC.radius, (512 - tmpC.radius));
tmpC.color = Color.FromArgb(127, rng.Next(0, 255), rng.Next(0, 255), rng.Next(0, 255));
tmpC.id = i;
tmpCarr[i] = tmpC;
}
return tmpCarr;
}
private void drawCircle(circle _circle, Graphics _g) // draws one circle
{
SolidBrush sb = new SolidBrush(_circle.color);
_g.FillEllipse(sb, (_circle.x - _circle.radius), (_circle.y - _circle.radius), (_circle.radius * 2), (_circle.radius * 2));
sb.Dispose();
}
private void drawString(float[] _pos, string _text, Graphics _g) // draws text
{
StringFormat sf = new StringFormat();
sf.LineAlignment = StringAlignment.Center;
sf.Alignment = StringAlignment.Center;
Font font = new Font("Arial", 12);
SolidBrush sb = new SolidBrush(Color.Black);
float x = _pos[0];
float y = _pos[1];
_g.DrawString(_text, font, sb, x, y, sf);
font.Dispose();
sb.Dispose();
}
private void drawCircleArr(circle[] _circleArr, Graphics _g)// draws an array of circles
{
_g.Clear(panel1.BackColor);
for (int i = 0; i < _circleArr.Length; i++)
{
drawCircle(_circleArr[i], _g);
drawString(_circleArr[i].pos, _circleArr[i].id.ToString(), _g);
}
}
static double mDistance<T>(T[] _p0, T[] _p1) // gets euclidean distance between two points of arbitrary numbers of dimensions
{
double[] p0 = new double[] { Convert.ToDouble(_p0[0]), Convert.ToDouble(_p0[1]) };
double[] p1 = new double[] { Convert.ToDouble(_p1[0]), Convert.ToDouble(_p1[1]) };
double tmp = 0;
double tmpTotal = 0;
for (int i = 0; i < _p0.Length; i++)
{
tmp = (p0[i] - p1[i]);
tmpTotal += (tmp * tmp);
}
double output = Math.Sqrt(tmpTotal);
return (output);
}
private bool overlap(circle _c0, circle _c1) // checks if two circles overlap
{
double dis = mDistance(_c0.pos, _c1.pos);
if (dis <= (_c0.radius + _c1.radius))
{
return (true);
}
return (false);
}
private Color avgColor(List<circle> _colorArr) // averages mutiple colors togehter
{
float ia = 0;
float ir = 0;
float ig = 0;
float ib = 0;
for (int i = 0; i < _colorArr.Count; i++)
{
ia += _colorArr[i].color.A;
ir += _colorArr[i].color.R;
ig += _colorArr[i].color.G;
ib += _colorArr[i].color.B;
}
byte a = Convert.ToByte(Math.Round(ia / _colorArr.Count));
byte r = Convert.ToByte(Math.Round(ir / _colorArr.Count));
byte g = Convert.ToByte(Math.Round(ig / _colorArr.Count));
byte b = Convert.ToByte(Math.Round(ib / _colorArr.Count));
return (Color.FromArgb(a, r, g, b));
}
private void treeView(List<circle>[] _circleLArr) // Create Treeview
{
treeView1.Nodes.Clear();
for (int i = 0; i < _circleLArr.Length; i++)
{
treeView1.Nodes.Add(i.ToString());
for (int j = 0; j < _circleLArr[i].Count; j++)
{
treeView1.Nodes[i].Nodes.Add(_circleLArr[i][j].id.ToString());
}
}
treeView1.ExpandAll();
}
private void drawCircleClusters(List<circle>[] _circleLArr, Graphics _g) // draws the circle clusters
{
_g.Clear(panel1.BackColor);
circle tmpC;
Color tmpColor;
for (int i = 0; i < _circleLArr.Length; i++)
{
tmpColor = avgColor(_circleLArr[i]);
for (int j = 0; j < _circleLArr[i].Count; j++)
{
tmpC = _circleLArr[i][j];
tmpC.color = tmpColor;
drawCircle(tmpC, _g);
drawString(_circleLArr[i][j].pos, _circleLArr[i][j].id.ToString(), _g);
}
}
}
//----------------------------------------------------
private List<circle>[] simpleOverlap(circle[] _circleArr) // test what circles overlaps
{
List<circle>[] tmpLArr = new List<circle>[_circleArr.Length];
for (int i = 0; i < (_circleArr.Length); i++)
{
tmpLArr[i] = new List<circle>();
for (int j = 0; j < (_circleArr.Length); j++)
{
if (overlap(_circleArr[i], _circleArr[j]))
{
tmpLArr[i].Add(_circleArr[j]);
}
}
}
return (tmpLArr);
}
/*
private circle[] recurOverlap(circle[] _circleArr) // recursive overlap test(not done/working)
{
List<circle> overlapArr = new List<circle>();
List<circle> dontOverlapArr = new List<circle>();
bool loop = true;
int n = 0;
while (loop)
{
if (overlap(_circleArr[0], _circleArr[n]))
{
overlapArr.Add(_circleArr[n]);
dontOverlapArr.Insert(0, _circleArr[n]);
circle[] dontArr = dontOverlapArr.ToArray();
recurOverlap(dontArr);
}
else
{
dontOverlapArr.Add(_circleArr[n]);
}
n++;
if (n >= _circleArr.Length)
{
loop = false;
}
}
if(_circleArr.Length <= 1)
{
return _circleArr;
}
else{
return overlapArr.ToArray();
}
}
private List<circle>[] clusterBrecur(circle[] _circleArr)
{
List<circle>[] tmpLArr = new List<circle>[_circleArr.Length];
for (int i = 0; i < (_circleArr.Length); i++)
{
tmpLArr[i] = new List<circle>();
recurOverlap(_circleArr);
}
return (tmpLArr);
}*/
private void run() // Run function
{
treeView1.Nodes.Clear(); // clear tree view
_DB.g = panel1.CreateGraphics();// Create Panel Graphics to draw on
_DB.circleArr = genRngCircles(10); // Creates an array with random circles
drawCircleArr(_DB.circleArr, _DB.g); // Draws the random circles
clusterAbtn.Enabled = true; // enables the cluster button
}
private void clusterA() // clusterA function
{
_DB.circleClusters = simpleOverlap(_DB.circleArr); // runs cluster algorithm test A
treeView(_DB.circleClusters); // Creates the treeview
drawCircleClusters(_DB.circleClusters, _DB.g); // draws the circle clusters
}
private void clusterB()
{
}
private void clusterA_rClick()
{
drawCircleArr(_DB.circleArr, _DB.g); // Draws the random circles
}
private void runBtn_Click(object sender, EventArgs e) // run button click
{
run();
}
private void clusterAbtn_MouseUp(object sender, MouseEventArgs e)
{
switch (e.Button)
{
case MouseButtons.Left:
clusterA();
break;
case MouseButtons.Right:
clusterA_rClick();
break;
}
}
private void clusterBbtn_Click(object sender, EventArgs e) // clusterB button click
{
clusterB();
}
}
class DB // "Database"
{
public Graphics g;
public circle[] circleArr;
public List<circle>[] circleClusters;
}
}
The current "overlap function"
private List<circle>[] simpleOverlap(circle[] _circleArr) // test what circles overlaps
{
List<circle>[] tmpLArr = new List<circle>[_circleArr.Length];
for (int i = 0; i < (_circleArr.Length); i++)
{
tmpLArr[i] = new List<circle>();
for (int j = 0; j < (_circleArr.Length); j++)
{
if (overlap(_circleArr[i], _circleArr[j]))
{
tmpLArr[i].Add(_circleArr[j]);
}
}
}
return (tmpLArr);
}