Comment pouvons-nous identifier et délimiter les trous dans un ensemble de points 2D représentant les emplacements des échantillons de sol ?

Recherche de trous dans des ensembles de points 2D

La tâche consiste à trouver les trous dans un ensemble de points 2D dans un système de grille cartésienne. Les points représentent les emplacements des échantillons de sol et les trous peuvent inclure des roches géantes, des endroits marécageux ou des lacs/étangs. L'objectif est de trouver le polygone concave qui définit grossièrement ces zones, en ajustant la sensibilité de l'algorithme pour contrôler la rugosité ou la douceur du polygone.

Approche de la solution

Étapes :

1. Créer une densité map : Convertissez l'ensemble de points en un bitmap ou un tableau 2D en mettant à l'échelle et en projetant chaque point sur une grille. Calculez la densité (nombre de points) pour chaque cellule.
2. Identifiez les trous :Trouvez les cellules de densité nulle ou inférieure à un seuil donné.
3. Segmentez les zones de trous : Créez des lignes horizontales et verticales recouvrant ces trous, en les regroupant par proximité pour former un trou segments.
4. Polygoniser les segments de trous : Convertissez les segments en polygones concaves. Triez les points pour garantir une connectivité appropriée et supprimez les doublons.

Exemple de mise en œuvre (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);

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!