토양 샘플 위치를 나타내는 2D 점 세트에서 구멍을 어떻게 식별하고 묘사할 수 있습니까?

2D 점 세트에서 구멍 찾기

이 작업은 직교 그리드 시스템 내의 2D 점 세트에서 구멍을 찾는 것입니다. 점은 토양 샘플 위치를 나타내고 구멍에는 거대한 암석, 늪지대 또는 호수/연못이 포함될 수 있습니다. 목표는 이러한 영역을 대략적으로 정의하는 오목 다각형을 찾아 알고리즘의 민감도를 조정하여 다각형의 거칠기 또는 매끄러움을 제어하는 ​​것입니다.

해결 방법

단계:

1. 밀도 만들기 map: 각 점의 크기를 조정하고 그리드에 투영하여 점 세트를 비트맵 또는 2D 배열로 변환합니다. 각 셀의 밀도(점 수)를 계산합니다.
2. 구멍 식별: 밀도가 0이거나 지정된 임계값보다 낮은 셀을 찾습니다.
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);

위 내용은 토양 샘플 위치를 나타내는 2D 점 세트에서 구멍을 어떻게 식별하고 묘사할 수 있습니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!