Bagaimanakah saya boleh mengenal pasti dan mempoligoni lubang cembung dalam awan titik 2D menggunakan C#?

Kod ini menunjukkan pendekatan untuk mencari lubang cembung dalam set titik 2d. Pendekatan ini melibatkan mencipta peta bit awan titik, mengira ketumpatan data untuk setiap sel dalam peta bit, mencipta senarai kawasan yang tidak digunakan (peta[][] = 0 atau peta[][] <= treshold), membahagikan senarai kawasan yang tidak digunakan kepada kumpulan komponen yang disambungkan, dan poligonkan setiap kumpulan komponen yang disambungkan untuk mendapatkan poligon cembung yang mewakili lubang.

Berikut ialah pelaksanaan C# bagi algoritma disediakan:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Drawing;

namespace HoleFinder
{
    class Program
    {
        // Define a cell structure for the bitmap
        public struct Cell
        {
            public double x0, x1, y0, y1; // Bounding box of points inside the cell
            public int count;            // Number of points inside the cell
        }

        // Define a line structure for representing hole boundaries
        public struct Line
        {
            public double x0, y0, x1, y1; // Line edge points
            public int id;             // Id of the hole to which the line belongs for segmentation/polygonization
            public int i0, i1, j0, j1;    // Index in map[][]
        }

        // Compute the bounding box of the point cloud
        public static (double x0, double x1, double y0, double y1) ComputeBoundingBox(List points)
        {
            double x0 = points[0].X;
            double x1 = points[0].X;
            double y0 = points[0].Y;
            double y1 = points[0].Y;

            foreach (var point in points)
            {
                if (point.X < x0) x0 = point.X;
                if (point.X > x1) x1 = point.X;
                if (point.Y < y0) y0 = point.Y;
                if (point.Y > y1) y1 = point.Y;
            }

            return (x0, x1, y0, y1);
        }

        // Create a bitmap of the point cloud
        public static int[,] CreateBitmap(List points, (double x0, double x1, double y0, double y1) boundingBox, int N)
        {
            // Create a 2D array to represent the bitmap
            int[,] bitmap = new int[N, N];

            // Compute the scale factors for converting point coordinates to bitmap indices
            double mx = N / (boundingBox.x1 - boundingBox.x0);
            double my = N / (boundingBox.y1 - boundingBox.y0);

            // Iterate over the points and increment the corresponding cells in the bitmap
            foreach (var point in points)
            {
                int i = (int)Math.Round((point.X - boundingBox.x0) * mx);
                int j = (int)Math.Round((point.Y - boundingBox.y0) * my);

                if (i >= 0 && i < N && j >= 0 && j < N)
                    bitmap[i, j]++;
            }

            return bitmap;
        }

        // Compute the data density for each cell in the bitmap
        public static void ComputeDataDensity(int[,] bitmap, Cell[] map)
        {
            for (int i = 0; i < map.Length; i++)
            {
                map[i].count = 0;
            }

            for (int i = 0; i < bitmap.GetLength(0); i++)
            {
                for (int j = 0; j < bitmap.GetLength(1); j++)
                {
                    map[i * bitmap.GetLength(1) + j].count += bitmap[i, j];
                }
            }
        }

        // Create a list of unused areas (map[][] = 0 or map[][] <= treshold)
        public static List<(int i0, int i1, int j0, int j1)> FindUnusedAreasHorizontalVertical(Cell[] map, int N, int treshold = 0)
        {
            List<(int i0, int i1, int j0, int j1)> unusedAreas = new List<(int, int, int, int)>();

            // Scan horizontally
            for (int j = 0; j < N; j++)
            {
                int i0 = -1;
                int i1 = -1;
                for (int i = 0; i < N; i++)
                {
                    if (map[i * N + j].count == 0 || map[i * N + j].count <= treshold)
                    {
                        if (i0 < 0) i0 = i;
                    }
                    else
                    {
                        if (i0 >= 0)
                        {
                            unusedAreas.Add((i0, i1, j, j));
                            i0 = -1;
                            i1 = -1;
                        }
                    }
                }

                if (i0 >= 0) unusedAreas.Add((i0, i1, j, j));
            }

            // Scan vertically
            for (int i = 0; i < N; i++)
            {
                int j0 = -1;
                int j1 = -1;
                for (int j = 0; j < N; j++)
                {
                    if (map[i * N + j].count == 0 || map[i * N + j].count <= treshold)
                    {
                        if (j0 < 0) j0 = j;
                    }
                    else
                    {
                        if (j0 >= 0)
                        {
                            unusedAreas.Add((i, i, j0, j1));
                            j0 = -1;
                            j1 = -1;
                        }
                    }
                }

                if (j0 >= 0) unusedAreas.Add((i, i, j0, j1));
            }

            return unusedAreas;
        }

        // Segment the list of unused areas into groups of connected components
        public static List> SegmentUnusedAreas(List<(int i0, int i1, int j0, int j1)> unusedAreas)
        {
            // Initialize each unused area as a separate group
            List> segments = new List>();
            foreach (var unusedArea in unusedAreas)
            {
                segments.Add(new List<(int i0, int i1, int j0, int j1)> { unusedArea });
            }

            // Iterate until no more segments can be joined
            bool joined = true;
            while (joined)
            {
                joined = false;

                // Check if any two segments intersect or are adjacent
                for (int i = 0; i < segments.Count; i++)
                {
                    for (int j = i + 1; j < segments.Count; j++)
                    {
                        // Check for intersection
                        bool intersects = false;
                        foreach (var unusedArea1 in segments[i])
                        {
                            foreach (var unusedArea2 in segments[j])
                            {
                                if (unusedArea1.i0 <= unusedArea2.i1 && unusedArea1.i1 >= unusedArea2.i0
                                    && unusedArea1.j0 <= unusedArea2.j1 && unusedArea1.j1 >= unusedArea2.j0)
                                {
                                    intersects = true;
                                    break;
                                }
                            }

                            if (intersects) break;
                        }

                        // Check for adjacency
                        bool adjacent = false;
                        if (!intersects)
                        {
                            foreach (var unusedArea1 in segments[i])
                            {
                                foreach (var unusedArea2 in segments[j])
                                {
                                    if (unusedArea1.i0 == unusedArea2.i0 && unusedArea1.i1 == unusedArea2.i1
                                        && ((unusedArea1.j1 == unusedArea2.j0 && Math.Abs(unusedArea1.j0 - unusedArea2.j1) == 1)
                                            || (unusedArea1.j0 == unusedArea2.j1 && Math.Abs(unusedArea1.j1 - unusedArea2.j0) == 1)))
                                    {
                                        adjacent = true;
                                        break;
                                    }

                                    if (unusedArea1.j0 == unusedArea2.j0 && unusedArea1.j1 == unusedArea2.j1
Atas ialah kandungan terperinci Bagaimanakah saya boleh mengenal pasti dan mempoligoni lubang cembung dalam awan titik 2D menggunakan C#?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!