日期:2014-05-18  浏览次数:21018 次

[研究]不规则坐标(可看作二维数组)分组算法。欢迎所有有兴趣研究算法的人。
坐标X或Y(也可把坐标X、Y看作数组)根据给定的一堆坐标(随机),进行分组的算法。 
坐标数据: 
坐标:X=163,Y=83 
坐标:X=164,Y=83 
坐标:X=197,Y=83 
坐标:X=198,Y=83 
坐标:X=163,Y=84 
坐标:X=164,Y=84 
坐标:X=197,Y=84 
坐标:X=198,Y=84 
坐标:X=163,Y=85 
坐标:X=164,Y=85 
坐标:X=199,Y=85 
坐标:X=199,Y=85 
…… 

要把以上坐标分组成如下: 
Point[] Group1 = {{163,83},{164,83},{163,84},{164,84},{163,85},{164,85}} 
Point[] Group2 = {{197,83},{198,83},{197,84},{198,84},{197,85},{198,85}} 
…… 

分组规则:只要X或Y其中一个能从数据中找到连续的就分为一组。

如下图每个几何图形分为一组。


------解决方案--------------------
利用递归思路对其邻近的点进行比对,当x,y方向都没有邻近点的时候则视为递归终点.
这样说好像比较范,就先当抛出个砖头.
------解决方案--------------------
把所有点作为图的顶点,然后遍历每个顶点寻找与之相邻的顶点并且添加一个边。

然后这个图的每一个连通分量就是楼主要求得一个分组了
------解决方案--------------------
看看效果先,我已经绘制出来:
C# code
public partial class Form1 : Form 
{
  public Form1()
  {
    InitializeComponent();
  }

  private void Form1_Paint(object sender, PaintEventArgs e)
  {
    int gridSize = 20;
    for (int i = 0; i * gridSize < ClientSize.Width; i++)
    {
      e.Graphics.DrawString(i.ToString("00"), Font, Brushes.Black,
        i * gridSize - 5, 0);
      e.Graphics.DrawLine(Pens.Gray, i * gridSize, gridSize,
        i * gridSize, ClientSize.Height);
    }
    for (int i = 0; i * gridSize < ClientSize.Height; i++)
    {
      e.Graphics.DrawString(i.ToString("00"), Font, Brushes.Black, 0,
        i * gridSize - 5);
      e.Graphics.DrawLine(Pens.Gray, gridSize, i * gridSize,
        ClientSize.Width, i * gridSize);
    }

    for (int i = 0; i < points.Length; i++)
      e.Graphics.DrawEllipse(Pens.Red,
        (points[i].X + 1) * gridSize - 3, (points[i].Y + 1) * gridSize - 3,
        6, 6);

    for (int i = 0; i < groups.Count; i++)
    {
      int minX = int.MaxValue, minY = int.MaxValue,
        maxX = int.MinValue, maxY = int.MinValue;
      for (int j = 0; j < groups[i].Count; j++)
      {
        Point p = groups[i][j];
        minX = p.X < minX ? p.X : minX;
        minY = p.Y < minY ? p.Y : minY;
        maxX = p.X > maxX ? p.X : maxX;
        maxY = p.Y > maxY ? p.Y : maxY;
      }
      Rectangle r = Rectangle.FromLTRB(
        (minX + 1) * gridSize - 5, (minY + 1) * gridSize - 5,
        (maxX + 1) * gridSize + 5, (maxY + 1) * gridSize + 5);
      e.Graphics.DrawRectangle(Pens.Blue, r);
      e.Graphics.DrawString(i.ToString(), Font, Brushes.Black, r);
    }
  }

  private const int pointCount = 100;
  private Point[] points = new Point[pointCount];
  private bool[] scans; // 是否计算过
  private List <List <Point>> groups = new List <List <Point>>();