c# - 群集重叠圆圈？

Question

我正在尝试对每个不间断重叠(连接)的圆圈进行聚类(分组)，我该怎么做？ (最好以一种非常有效的方式)。

(我一直在尝试编写一些递归函数，但没有任何效果。)

我创建了一个 VS 项目来可视化问题。

Download here:

生成随机圆。

集群目前如何运作:(它只查看哪个圆圈与特定圆圈重叠，而不是所有连接的圆圈)

它应该如何运作(所有连接圈的独立集群)

代码:(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;
    }
}

当前的“重叠函数”

    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);
    }

Answer 1

我对您的代码进行了以下更改。看起来像工作

    private List<circle>[] simpleOverlap(circle[] _circleArr) // test what circles overlaps 
    {
        List<List<circle>> list = new List<List<circle>>();

        //List<circle>[] tmpLArr = new List<circle>[_circleArr.Length];
        //for (int i = 0; i < (_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;
        for (int i = 0; i < list.Count; i += (flag ? 1 : 0))
        {
            flag = true;
            List<circle> cluster = list[i];
            for (int j = i + 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;
    }

我必须再添加 1 个方法 bool Intersects(List<circle> cluster1, List<circle> cluster2) .看看是否有帮助。