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

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;
}
``````
• what is the issue with NetTopologySuite convex hull? slow or not getting the correct boundary? Jun 4, 2012 at 3:45
• ok..i got the point..it is very slow..some computational geometry specialist might be required to answer this :-) Jun 4, 2012 at 5:11
• Yeah just a little slow :(, I'm able to use 0.5 x 0.5 squares instead, it seems to of sped the process up a little, but any other examples or experience would be great.
– Jamo
Jun 4, 2012 at 5:46
• What is the actual output that you want? If it's just an extent, can't you just take the max/min of the xyz points? Jun 4, 2012 at 15:09
• Some of the answers to this question may lead you in the right direction: Concave Hull: Definition, Algorithms and Practical Solutions Jun 5, 2012 at 4:45

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)
{
List<ICoordinate> coordinates = new List<ICoordinate>();

{
}

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

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!");