Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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;
        mpl = mpl.Union(p) as Geometry;
share|improve this question
what is the issue with NetTopologySuite convex hull? slow or not getting the correct boundary? – vinayan Jun 4 '12 at 3:45
ok..i got the is very slow..some computational geometry specialist might be required to answer this :-) – vinayan Jun 4 '12 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 '12 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? – Anthony -GISCOE- Jun 4 '12 at 15:09
Some of the answers to this question may lead you in the right direction: Concave Hull: Definition, Algorithms and Practical Solutions – blah238 Jun 5 '12 at 4:45
up vote 5 down vote accepted

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())

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

            reader = null;
            coordinates = null;

            IMultiPoint multiPoint = fact.CreateMultiPoint(coordinatesArr);

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

            Console.WriteLine("Processing Completed!");

Hope it helps :)

share|improve this answer
Thanks I will give it a shot, I've experienced strange results when using convex hull, can you explain the multiPoint.Normalize() method and its purpose? – Jamo Jun 6 '12 at 1:09
@Jamo sincerely..i don't know what it does..interesting thing is that when i loaded these 5 million points into the JTS Test-builder application as an xml test case, it generated the convex-hull in two seconds!! – vinayan Jun 6 '12 at 1:56

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.