我们如何识别和描绘代表土壤样本位置的二维点集中的孔？

在 2D 点集中查找孔

任务是在笛卡尔网格系统内的一组 2D 点中查找孔。这些点代表土壤样本位置，洞可能包括巨大的岩石、沼泽地或湖泊/池塘。目标是找到大致定义这些区域的凹多边形，调整算法的灵敏度来控制多边形的粗糙度或平滑度。

解决方案

步骤：

1. 创建密度map: 通过缩放每个点并将其投影到网格上，将点集转换为位图或二维数组。计算每个单元的密度（点数）。
2. 识别孔：查找密度为零或低于给定阈值的单元。
3. 分割孔区域： 创建覆盖这些孔的水平和垂直线，并根据与形成孔的接近程度对它们进行分组
4. 将孔段多边形化：将线段转换为凹多边形。对点进行排序以确保正确的连接并删除重复项。

示例实现 (C#):

using System;
using System.Collections.Generic;

public class Holes
{
    // Density map (2D array)
    private int[][] map;

    // List of hole segments (lines)
    private List<Line> segments;

    // Polygonized holes (concave polygons)
    private List<Polygon> holes;

    // Polygonization tolerance (higher value = smoother polygons)
    private double tolerance;

    // Initializes the hole detection algorithm.
    public Holes(int[][] points, int mapSize, double tolerance)
    {
        if (points == null || mapSize <= 0 || tolerance <= 0)
        {
            throw new ArgumentException("Invalid arguments");
        }
        
        // Initialize the variables
        this.map = new int[mapSize][mapSize];
        this.tolerance = tolerance;
        this.segments = new List<Line>();
        this.holes = new List<Polygon>();
        
        // Create density map
        CreateDensityMap(points, mapSize);
    }

    // Identifies holes in the density map.
    public void FindHoles()
    {
        if (map == null || map.Length == 0)
        {
            throw new InvalidOperationException("Density map not initialized.");
        }
        
        // Find hole cells
        List<Cell> holeCells = FindCells(0);
        
        // Group hole cells into segments
        List<List<Line>> lineGroups = GroupLines(holeCells);
        
        // Polygonize segments
        PolygonizeSegments(lineGroups);
    }

    // Helper functions for hole detection.

    private void CreateDensityMap(int[][] points, int mapSize)
    {
        // Scale and project points onto a grid
        for (int i = 0; i < points.Length; i++)
        {
            double scaledX = points[i][0] / points[0][0] * mapSize;
            double scaledY = points[i][1] / points[0][1] * mapSize;
            int x = (int)scaledX;
            int y = (int)scaledY;
            
            // Increment count in density map
            map[x][y]++;
        }
    }

    private List<Cell> FindCells(int threshold)
    {
        List<Cell> holeCells = new List<Cell>();
        
        for (int i = 0; i < map.Length; i++)
        {
            for (int j = 0; j < map[i].Length; j++)
            {
                if (map[i][j] == 0 || map[i][j] <= threshold)
                {
                    holeCells.Add(new Cell(i, j));
                }
            }
        }
        
        return holeCells;
    }

    private List<List<Line>> GroupLines(List<Cell> holeCells)
    {
        // Group lines by proximity
        List<List<Line>> lineGroups = new List<List<Line>>();
        foreach (Cell holeCell in holeCells)
        {
            List<Line> group = null;
            
            // Find existing group or create a new one
            for (int i = 0; i < lineGroups.Count; i++)
            {
                if (lineGroups[i].Find(line => line.Proximity(holeCell) <= tolerance) != null)
                {
                    group = lineGroups[i];
                    break;
                }
            }
            
            if (group == null)
            {
                group = new List<Line>();
                lineGroups.Add(group);
            }
            
            // Add horizontal/vertical lines
            group.Add(new Line(holeCell.x, holeCell.y, true));
            group.Add(new Line(holeCell.x, holeCell.y, false));
        }
        
        return lineGroups;
    }

    private void PolygonizeSegments(List<List<Line>> lineGroups)
    {
        foreach (List<Line> lineGroup in lineGroups)
        {
            Polygon polygon = PolygonizeSegment(lineGroup);
            if (polygon != null)
            {
                holes.Add(polygon);
            }
        }
    }

    private Polygon PolygonizeSegment(List<Line> lineSegment)
    {
        // Sort lines by angle (convex hull algorithm)
        lineSegment.Sort((a, b) => a.Angle.CompareTo(b.Angle));
        
        // Remove duplicate lines
        List<Line> uniqueLines = new List<Line>();
        foreach (Line line in lineSegment)
        {
            if (uniqueLines.Count == 0 || uniqueLines[uniqueLines.Count - 1].Angle != line.Angle)
            {
                uniqueLines.Add(line);
            }
        }
        
        // Polygonize lines
        List<Point> points = new List<Point>();
        for (int i = 0; i < uniqueLines.Count; i++)
        {
            Point point = null;
            Line currentLine = uniqueLines[i];
            
            if (uniqueLines[(i + 1) % uniqueLines.Count].Angle - currentLine.Angle > Math.PI)
            {
                point = currentLine.GetIntersection(uniqueLines[(i + 1) % uniqueLines.Count], true);
            }
            else
            {
                point = currentLine.GetIntersection(uniqueLines[(i + 1) % uniqueLines.Count], false);
            }
            
            if (point != null)
            {
                points.Add(point);
            }
        }
        
        return new Polygon(points);
    }

    // Helper classes for line/polygon representation.

    private class Line
    {
        public int x1, y1, x2, y2;
        public double angle;
        public bool isHorizontal;

        public Line(int x, int y, bool isHorizontal)
        {
            if (isHorizontal)
            {
                x1 = 0; y1 = y;
                x2 = map.GetLength(0) - 1; y2 = y;
            }
            else
            {
                x1 = x; y1 = 0;
                x2 = x; y2 = map[0].GetLength(0) - 1;
            }
            
            this.angle = Math.Atan2(y2 - y1, x2 - x1);
            this.isHorizontal = isHorizontal;
        }

        public double Angle { get { return angle; } }

        public double Proximity(Cell cell)
        {
            double distX, distY;
            if (isHorizontal)
            {
                distX = cell.x - x1;
                distY = cell.y - y1;
            }
            else
            {
                distX = cell.x - x2;
                distY = cell.y - y2;
            }
            
            return Math.Sqrt(distX * distX + distY * distY);
        }

        public Point GetIntersection(Line other, bool isConvex)
        {
            double denominator, numerator, tx, ty;
            
            if (isHorizontal)
            {
                denominator = (other.y2 - other.y1) - (y2 - y1);
                numerator = ((other.x2 - other.x1) * (y1 - other.y1)) - ((x2 - x1) * (other.y2 - other.y1));
                tx = numerator / denominator;
                ty = other.y1 + ((tx - other.x1) * (other.y2 - other.y1)) / (other.x2 - other.x1);
            }
            else
            {
                denominator = (other.x2 - other.x1) - (x2 - x1);

以上是我们如何识别和描绘代表土壤样本位置的二维点集中的孔？的详细内容。更多信息请关注PHP中文网其他相关文章！