有意思的网格采样算法详解

网格采样算法是一种在计算机图形学和计算机视觉中常用的技术，用于将连续的空间或曲面表示转换为离散的网格表示。这种算法通常用于三维几何形状的建模、渲染和处理。

求解题型：
有一个画布大小为2000X2000，现在有n个点（n>100w），随机落在画布上，把画布平均分成100X100的格子，每个格子大小为20X20,要求计算每个点落在哪个格子上？

定义如下:
定义网格并初始化：List grids;
定义点并初始化：List points;

输出：
遍历输出每个点在哪个网格上，要求效率最高

下面讲2种解法：
第一种遍历法，效率极低，时间复杂度为O(n * m)
第二种是常用的网格采样算法，时间复杂度为O(1)

先用第二种方法求解，实现如下，把points的坐标，x和y都除以20，即可获得所在的格子的坐标
示例代码：

using System;
using System.Collections.Generic;

namespace GridPartition
{
    public class Point
    {
        public int X { get; }
        public int Y { get; }

        public Point(int x, int y)
        {
            X = x;
            Y = y;
        }
    }

    public class GridPartition
    {
        private Dictionary<Tuple<int, int>, List<Point>> gridMap;

        public GridPartition()
        {
            gridMap = new Dictionary<Tuple<int, int>, List<Point>>();
        }

        // 添加一个点
        public void AddPoint(Point point)
        {
            int gridX = point.X / 20;
            int gridY = point.Y / 20;

            Tuple<int, int> gridKey = Tuple.Create(gridX, gridY);

            if (!gridMap.ContainsKey(gridKey))
            {
                gridMap[gridKey] = new List<Point>();
            }

            gridMap[gridKey].Add(point);
        }

        // 输出每个点所在的格子
        public void PrintPointsInGrids()
        {
            foreach (var kvp in gridMap)
            {
                Tuple<int, int> gridKey = kvp.Key;
                List<Point> pointsInGrid = kvp.Value;

                Console.WriteLine($"Grid ({gridKey.Item1}, {gridKey.Item2}) contains {pointsInGrid.Count} point(s):");

                foreach (Point point in pointsInGrid)
                {
                    Console.WriteLine($"    Point ({point.X}, {point.Y})");
                }
            }
        }

        static void Main(string[] args)
        {
            GridPartition gridPartition = new GridPartition();

            // 假设有n个点
            // 在这里添加所有的点
            // 例如：
            gridPartition.AddPoint(new Point(0, 0));
            gridPartition.AddPoint(new Point(5, 10));
            gridPartition.AddPoint(new Point(25, 30));
            gridPartition.AddPoint(new Point(45, 50));
            gridPartition.AddPoint(new Point(1999, 1999));
            // ...

            gridPartition.PrintPointsInGrids();
        }
    }
}