How can I identify and polygonize convex holes within a 2D point cloud using C#?

This code demonstrates an approach to finding convex holes in a set of 2d points. The approach involves creating a bitmap of the point cloud, computing the data density for each cell in the bitmap, creating a list of unused areas (map[][] = 0 or map[][] <= treshold), segmenting the list of unused areas into groups of connected components, and polygonizing each group of connected components to obtain the convex polygons representing the holes.

Here's the C# implementation of the algorithm provided:

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
The above is the detailed content of How can I identify and polygonize convex holes within a 2D point cloud using C#?. For more information, please follow other related articles on the PHP Chinese website!