c# - Cluster overlapping circles? -
i trying cluster(group) every circle that's uninterrupted overlapping (connected) each other how that? (preferably in pretty efficient way).
(i have messed around trying write recursive functions haven't gotten work.)
i have created vs project visualize problem.
generates random circles. 
how clustering works: (its looks @ circle overlapping specific circle not connected) 
how should if working (separate clusters 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 // circle "object" { public float[] pos; public int radius; public color color; public int id; public float x { { return pos[0]; } set { pos[0] = value; } } public float y { { 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 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 array of random circles { random rng = new random(); circle tmpc; circle[] tmpcarr = new circle[_n]; (int = 0; < _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 1 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 array of circles { _g.clear(panel1.backcolor); (int = 0; < _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 2 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; (int = 0; < _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 2 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; (int = 0; < _colorarr.count; i++) { ia += _colorarr[i].color.a; ir += _colorarr[i].color.r; ig += _colorarr[i].color.g; ib += _colorarr[i].color.b; } byte = 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(); (int = 0; < _circlelarr.length; i++) { treeview1.nodes.add(i.tostring()); (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 circle clusters { _g.clear(panel1.backcolor); circle tmpc; color tmpcolor; (int = 0; < _circlelarr.length; i++) { tmpcolor = avgcolor(_circlelarr[i]); (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 circles overlaps { list<circle>[] tmplarr = new list<circle>[_circlearr.length]; (int = 0; < (_circlearr.length); i++) { tmplarr[i] = new list<circle>(); (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]; (int = 0; < (_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 draw on _db.circlearr = genrngcircles(10); // creates array random circles drawcirclearr(_db.circlearr, _db.g); // draws random circles clusterabtn.enabled = true; // enables cluster button } private void clustera() // clustera function { _db.circleclusters = simpleoverlap(_db.circlearr); // runs cluster algorithm test treeview(_db.circleclusters); // creates treeview drawcircleclusters(_db.circleclusters, _db.g); // draws circle clusters } private void clusterb() { } private void clustera_rclick() { drawcirclearr(_db.circlearr, _db.g); // draws 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 circles overlaps { list<circle>[] tmplarr = new list<circle>[_circlearr.length]; (int = 0; < (_circlearr.length); i++) { tmplarr[i] = new list<circle>(); (int j = 0; j < (_circlearr.length); j++) { if (overlap(_circlearr[i], _circlearr[j])) { tmplarr[i].add(_circlearr[j]); } } } return (tmplarr); }
i made following change code. looks working
private list<circle>[] simpleoverlap(circle[] _circlearr) // test circles overlaps { list<list<circle>> list = new list<list<circle>>(); //list<circle>[] tmplarr = new list<circle>[_circlearr.length]; //for (int = 0; < (_circlearr.length); i++) foreach (circle circle in _circlearr) { list<circle> cluster = null; //tmplarr[i] = new list<circle>(); //for (int j = 0; j < (_circlearr.length); j++) //{ // if (overlap(_circlearr[i], _circlearr[j])) // { // tmplarr[i].add(_circlearr[j]); // } //} foreach(list<circle> cluster2 in list) { foreach (circle circle2 in cluster2) { if (overlap(circle, circle2)) { cluster = cluster2; goto label_001; } } } label_001: if (cluster == null) { cluster = new list<circle>(); list.add(cluster); } cluster.add(circle); } bool flag = true; (int = 0; < list.count; += (flag ? 1 : 0)) { flag = true; list<circle> cluster = list[i]; (int j = + 1; j < list.count; j++) { list<circle> cluster2 = list[j]; if (intersects(cluster, cluster2)) { cluster.addrange(cluster2); list.remove(cluster2); j--; flag = false; } } } return list.toarray(); //return (tmplarr); } bool intersects(list<circle> cluster1, list<circle> cluster2) { foreach (circle circle1 in cluster1) { foreach (circle circle2 in cluster2) { if (overlap(circle1, circle2)) { return true; } } } return false; } i had add 1 more method bool intersects(list<circle> cluster1, list<circle> cluster2). see if helps.
Comments
Post a Comment