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

在 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 ();
        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>> 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  FindCells(int threshold)
    {
        List<cell> holeCells = new List<cell>();
        
        for (int i = 0; i > GroupLines(List<cell> holeCells)
    {
        // Group lines by proximity
        List<list>> lineGroups = new List<list>>();
        foreach (Cell holeCell in holeCells)
        {
            List<line> group = null;
            
            // Find existing group or create a new one
            for (int i = 0; i  line.Proximity(holeCell) ();
                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>> 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  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);</point></point></line></line></line></line></list></line></list></list></cell></cell></cell></list></cell></polygon></polygon></line>

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