Best way to get Convex Hull/Boundary of millions of points

Question

I've been trying to do some point analysis on some xyz data, I'm at the point where I've decided it is best to produce a boundary of my xyz files and put this with the metadata for each survey.

Now the part im stuck on is I've got over 15,000 surveys to compute the boundary of, tried convex hull and concave hull with varying results. I can be fairly confident of the regular interval in my points for each survey, so I was thinking of a buffer merge op of point interval + 25%...

Works great for smaller amounts of data. however it doesn't seem the most efficient way on the larger xyz data (still waiting on one to complete processing 15 minutes in ... 500,000 points.).

My thought process was Point -> buffer 0.75 -> Polygon -> Merge to existing polygons -> Multi Polygon -> buffer -0.75 -> Extents of Survey Multi Polygon.

I've been using NetTopologySuite c# for processing, perhaps some others have a routine they would like to share?

Update: logic using NetTopologySuite I think mpl = mpl.Union(p) as Geometry; is the bottleneck ...

Geometry mpl = null;
While(Loop all pnts logic)
{
NetTopologySuite.Geometries.Point pnt = new NetTopologySuite.Geometries.Point(
        ((float)eastL / 100),
        ((float)northL / 100),
        ((float)depth / 100)
      );
      float pntSpace = spacing + (spacing * 0.25);
      //produce a polygon for buffer.
      Polygon p = pnt.Buffer(pntSpace , 2, GeoAPI.Operations.Buffer.EndCapStyle.Square) as Polygon;
      if (mpl == null)
        mpl = p;
      else
        mpl = mpl.Union(p) as Geometry;
}

Answer 1

Here is a solution which is running quite fast (around 15 seconds for a 5 million random points which i created for Texas State). I normalized the multipoint input and it is giving satisfactory output. I am using Topology Framework .NET. It is similar to NetTopologySuite. Maybe you can do the same with NetTopologySuite as well.

My solution (console application) is below. You may need to alter it for batch-running from folders.

using System;
using System.Collections.Generic;
using System.IO;
using Topology.IO;
using Topology.Geometries;

namespace ConvexHullGenerator
{
    class Program
    {
        static void Main(string[] args)
        {
            ShapefileDataReader reader = new ShapefileDataReader(@"C:\Users\Home\Desktop\convex\randompt.shp", GeometryFactory.Default);
            List<ICoordinate> coordinates = new List<ICoordinate>();

            while (reader.Read())
            {
                coordinates.Add(reader.Geometry.Coordinate);
            }

            GeometryFactory fact = new GeometryFactory();
            WKTReader wktRdr = new WKTReader(fact);
            ICoordinate[] coordinatesArr = coordinates.ToArray();

            reader = null;
            coordinates = null;

            IMultiPoint multiPoint = fact.CreateMultiPoint(coordinatesArr);
            multiPoint.Normalize();

            IGeometry hullGeom = multiPoint.ConvexHull();
            StreamWriter sw = new StreamWriter(@"C:\Users\Home\Desktop\convex\hullWKT.txt");
            sw.WriteLine(hullGeom.AsText());
            sw.Close();

            Console.WriteLine("Processing Completed!");
            Console.ReadLine();
        }
    }
}

Hope it helps :)