4

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? – vinayan Jun 4 '12 at 3:45
  • 1
    ok..i got the point..it 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
  • 2
    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
5

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

  • 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 clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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