ThinkGeo.com    |     Documentation    |     Premium Support

Line Simplification

#1

I ran into this problem quite by accident.  I am using line simplification to remove vertices from line elements to speed up the display of SQL Server Spatial data.  I found I have a number of lines where the first and last vertices are the same.  Depending on the shape of the line, the results of the simplify routine are a three vertex line with the same first and last vertex.  This line will pass the IsValid test whether I use simple or advanced validation, but this is not a valid line in SQL Server, meaning it fails STIsValid(). 


My initial solution was to return the original line from my simplification routine, but I encounter at least one line with 75 vertices that simplified to three.  This is exactly the type of line I want to simplify.  My current work around for this problem is to remove the last vertex so I have a two point line that doesn't double back on itself.  This may lead to its own set of problems however, such as line/route tracing.


Is this a problem with line simplification, or an expected result that I have to handle?


Can you suggest a better work around?


Shouldn't your Feature.IsValid() routine catch this problem?


Charles



#2

Charles, I think MapSuite is still using NTS under the hood.  And in my experience with NTS over the last three years, you cannot trust its IsValid tests.  First, they can easily give you a wrong answer, and second, on geometry that is truly invalid, the validity test can take several seconds to a few minutes. 
  
 We had written our own geometry factory wrapper with functions for union, intersection, etc, that proxied to the native NTS object methods, but from which we could catch errors, etc.   A few months ago, we started using the SQL Server spatial types as standalone objects (we do not use SQL Server, though).  Now, within our factory methods, we find that we can instantiate sql server types from feature WKB’s, perform the operations (with high integrity), and convert back faster than the native NTS implementation.    We use buffering intensively in our application.  We had a 13% buffer failure rate with the native NTS methods.    Now, we have less than a 1% failure rate for effectively the same geometries, and the 99% that succeed occur in less than 40% of the time.  
  
 I know this is not an answer to your question, but I thought it might be helpful to share our experiences with NTS vs SQL Server Spatial Types.    And, for what it is worth, I have been a big supporter of NTS and the GeoAPI interfaces.  The fact that ThinkGeo used them is actually one of the reasons I switched to ThinkGeo.

#3

Ted, Thanks for your sharing on NTS experience, I appreciate it very much.


Charles, Thanks for your post and question. Here what I want to address is how the validation integrated in Map Suite works, hope it helps.
 
There is a property called IsValid in feature object, it has nothing to do with the Validate API in the Shape object which will be mentioned after this. This property only checks the WellKnownBinary integrated in the feature is null or not.
 
The shape contains an API called Validate, and each sub class (concrete shapes) will implement its own ValidateCore according its own case. Up to now, we leave out the implementations for future usage or customized validation when passing the Advanced ShapeValidateMode, so please forget this if you do not want to create your own Validation logic.And in Simple ShapeValidateMode, we just do very simple validation on the shape, for example we will pass the validation if we found the vertices count in the lineshape >= 2 or more, and >=4 for the RingShape etc.
 
Any more questions just feel free to let me know.
 
Thanks.
 
Yale

#4

Charles, 
  
   I am not sure that a three point that double back on itself is not a valid line string.  If the ends connect and there is area and it does not self intersect then it is a ring.  Technically I think a line that double back on itself is intersecting and therefor a line string.  I think it gets down to how each vendor implements it. 
  
 The lines you process are they circles at first that you converted into a line?  Did they start with the same start and end position? 
  
 David

#5

David, according to the OGIS Simple Feature Specification, spikes in a polygon ring are not allowed, and the object in question has a spike… one line segment returning upon itself.    If you are using NTS under the hood for this simplification function, I can assure you that the function is NOT robust, and it can return invalid geometries from valid parameters. 
  
 When we started switching to the SQL Server Spatial Types for our operations, the first thing we had to do was add code to correct a lot of NTS geometries that we had saved, assuming them to be valid.   The SQL Server Spatial Types are quite rigid in their rules for valid geometries. 
  
 Charles… sounds like my NTS dissertation was a wild goose chase for your IsValid issue.   Sorry for the confusion.

#6

Ted, 
  
   I think you are missing my point.  The point is he is working with lines.  It is valid to have a line that doubles back on itself.  It is also valid to have a line that has the same start and end vertex. 
  
 David

#7

Yep.   You are correct.  I don't see anything in the OGIS spec that precludes that.   I was focused on rings, rather than linestrings.


I'll shut up now :)



#8

Ted, 
  
   In summation…    
  
 1. NTS is not all the great for hardcore geometry handling.  It’s outdated but good for general use. 
 2. The whole geometry realm is a complex place and many time counter intuitive / confusing.  Things like lines, rings etc seem so simple but it is hardly the case. 
  
 I am interested in how you used SQL though.  You said you can reference the assemblies directly?  What assemblies do you use?  I would love to write a code community project on how people can use that as an alternative.  Are the assemblies also included in the free version of SQL Server? 
  
 David

#9

I’m headed into my Wednesday… the day I write off to weekly conference calls :(.   When the day is over, I’ll get more info to you.   But, in summary, the SQL Server Spatial Types can be googled.   They are a free download, and can be used w/o any instance of SQL Server at all.   At least that’s my take on it.  I would be interested in your take. 
  
 You actually download this component (copied from their downloads page): 
  
 Microsoft SQL Server System CLR Types  
 The SQL Server System CLR Types package contains the components implementing the new geometry, geography, and hierarchyid types in SQL Server 2008. This component can be installed separately from the server to allow client applications to use these types outside of the server. 


#10

I appreciate all of the replies.  To answer David first reply, the majority of the lines were very narrow triangles, although at least one had 73 vertices prior to simplification.  The line that doubles back on itself may be valid outside SQL Server Spatial.  I can’t think of a real world example, but I know that these features fail the Location.STIsValid() test in SQL Server.  
  
 I’m not sure that I understand what Ted is doing, but I’m interested as well. 
  
 Charles

#11

Charles, 
  
   I am going to try and put something together for tomorrow or Friday to outline what Ted is talking about.  I am very interested in that as well.  
  
   As for a real world case it is very common that a line might track somethings movement and that movement might go back to the original position.  For example a car being tracked driving around town will most likely double back on its way home.  The reason that it is not a polygon is that the route is possibly self intersecting.  Of course we all know as well that tracking a car produces a line and not a polygon.  We tend to think that if a line starts and stops in the same place it is a ring or polygon but it isn’t true. 
  
 David

#12

David, 
  
 The problem doesn’t appear to be a line starting and ending at the same location.  STIsValid() only fails if it is applied to a three point line.  I’d be curious to know if SQL Spatial does that intentionally and why, but seeing it is Microsoft, I don’t think I could get an answer. 
  
 Charles

#13

Can you show us the WKT (AsText) for the shape in question?   I’m looking at examples of STIsValid where it is demonstrated with a three-point line being valid.

#14

I've attached the SQLGeometryFactory class that we built so that we can easily use the geometry operations of these types with the native NTS objects.   Were I starting over, I would likely base our entire application on these types, but in all of our classes, we've coded the geometry objects using the GeoAPI interfaces, and I guess only the NTS objects have chosen to implement those interfaces :(


In the attached file, you will find at least one function that has dependencies upon a litle WKT parser library we wrote.   We always used it when we needed to parse WKT w/o a full GIS engine.   And, when the SQL Server Types give you an invalid format error, we can parse the data ourselves and have a chance at programmatically fixing stuff that might be bad (like rings not being closed, or having one bad interior ring in a polygon).   If you comment out that code in the CreateFromWKT function, I think the rest of it might "just work".


You will note that we have factory functions for "IntersectPolygons".   Fortunately, we had a rule that our developers were never allowed to use the embedded operation methods directly on the IGeometry object.... (ie, a developer that writes poly2 = poly0.Intersect(poly1) gets their hand slapped).  By using a factory method, we can do things like test for either geometry being null and other convenience things.  And we can catch any geometry errors and log them, if not recover from them.   That's how we got a database of over 50,000 "invalid geometry" objects that we could use for testing against NTS improvements or other alternatives.   By having this rule in place, it became very easy for us to just make those factory methods call these new SQL factory methods.   We change our core library, and no other code had to change.   Well, in these SQL methods, you may notice that we don't have any Union methods.   That's because the NTS union operations work pretty well, so we had no need to proxy the calls from our original Union factory method to an equivalent SQL factory method.


Also, Charles, for your simplification routine, you might want to look at the Reduce method on these SQL Geometry objects.   If that's what you start with, then maybe you can get better and faster behavior directly from those objects.    We use this Reduce function a lot (thinning data from 5hz GPS receivers).   And the NTS implementation seemed marginal.


msdn.microsoft.com/en-us/library/bb933814.aspx


Anyway... hope this helps.



mpnSQLGeometryFactory.cs (12.1 KB)

#15

Ted, 
  
 The original feature is: 
  
 LINESTRING (11720580.200000001 3703978.52, 11720588.07 3703971.11, 11720568.02 3703991.62, 11720580.200000001 3703978.52) 
  
 This is valid using the STIsValid() method 
  
 If you delete either of the intermediate vertices, STIsValid() will fail. 
 LINESTRING (11720580.200000001 3703978.52, 11720568.02 3703991.62, 11720580.200000001 3703978.52) 
 LINESTRING (11720580.200000001 3703978.52, 11720588.07 3703971.11, 11720580.200000001 3703978.52) 
  
 My test query within SQL Spatial is: 
  
 DECLARE @Location geometry 
 SET @Location = geometry::STLineFromText(’[Put the line string to test here]’, 0) 
 SELECT @Location.STIsValid() 
  
 Charles

#16

I decided to experiment a little.  I wanted to see what the SS types would do if it tried to make the line valid.   And I wondered what it would do with an internal spike in a line.  I executed this code:


 This CreateFromWKT function parses the WKT into a SQL Geometry, tests for it being valid, and executes the MakeValid if it is not.   The first call was valid, as expected.  The other three calls were invalid, as you have indicated.   It made the second and third entry valid by returning a two-point line, and it make the fourth entry be valid by returning a multi linestring, removing the overlapping segment.



LINESTRING(11720580.200000001 3703978.52,11720588.07 3703971.11,11720568.02 3703991.62,11720580.200000001 3703978.52)


LINESTRING(11720568.020000458 3703991.6199989319,11720580.200000763 3703978.5200004578)


LINESTRING(11720580.200000763 3703978.5200004578,11720588.069999695 3703971.1100006104)


MULTILINESTRING((11720581.199996948 3703972.5199966431,11720588.069999695 3703971.1100006104,11720580.199996948 3703978.5199966431),(11720568.019996643 3703991.6200027466,11720588.069999695 3703971.1100006104))



            // Parse the original line
            IGeometry g0 = mpnSqlGeometryFactory.CreateFromWKT("LINESTRING (11720580.200000001 3703978.52, 11720588.07 3703971.11, 11720568.02 3703991.62, 11720580.200000001 3703978.52)");
            System.Diagnostics.Debug.WriteLine(g0.AsText());

            // Remove the second point
            IGeometry g1 = mpnSqlGeometryFactory.CreateFromWKT("LINESTRING (11720580.200000001 3703978.52, 11720568.02 3703991.62, 11720580.200000001 3703978.52)");
            System.Diagnostics.Debug.WriteLine(g1.AsText());
  
            // Remove the third point
            IGeometry g2 = mpnSqlGeometryFactory.CreateFromWKT("LINESTRING (11720580.200000001 3703978.52, 11720588.07 3703971.11, 11720580.200000001 3703978.52)");
            System.Diagnostics.Debug.WriteLine(g2.AsText());

            // Insert the second point as a fourth point, and modify the last point to avoid overlapping that segment
            IGeometry g4 = mpnSqlGeometryFactory.CreateFromWKT("LINESTRING (11720580.200000001 3703978.52, 11720588.07 3703971.11, 11720568.02 3703991.62, 11720588.07 3703971.11, 11720581.200000001 3703972.52)");
            System.Diagnostics.Debug.WriteLine(g4.AsText());



#17

I decided to test with numbers that were easier for a human to work with, and I wanted to know if a partial spike was also handled.


 


 



        public void LineStringIsValid()
        {
            // Parse the original line
            IGeometry g0 = mpnSqlGeometryFactory.CreateFromWKT("LINESTRING (0 0, 0 2, 2 2, 0 0)");
            System.Diagnostics.Debug.WriteLine(g0.AsText());

            // Remove the second point
            IGeometry g1 = mpnSqlGeometryFactory.CreateFromWKT("LINESTRING (0 0, 2 2, 0 0)");
            System.Diagnostics.Debug.WriteLine(g1.AsText());
  
            // Remove the third point
            IGeometry g2 = mpnSqlGeometryFactory.CreateFromWKT("LINESTRING (0 0, 0 2, 0 0)");
            System.Diagnostics.Debug.WriteLine(g2.AsText());

            // Insert the second point as a fourth point, and modify the last point to avoid overlapping that segment
            IGeometry g4 = mpnSqlGeometryFactory.CreateFromWKT("LINESTRING (0 0, 0 2, 2 2, 0 2, 0 3)");
            System.Diagnostics.Debug.WriteLine(g4.AsText());

            // Move the returning point of the spike to be 1/2 way to the origin of the spike,
            // and see if a partial overlap is recognized
            IGeometry g5 = mpnSqlGeometryFactory.CreateFromWKT("LINESTRING (0 0, 0 2, 2 2, 1 2, 0 3)");
            System.Diagnostics.Debug.WriteLine(g5.AsText());

        }

The results:




        
  • LINESTRING(0 0,0 2,2 2,0 0)

    •     
  • LINESTRING(2 2,0 0)

    •     
  • LINESTRING(0 2,0 0)

    •     
  • MULTILINESTRING((0 3,0 2,2 2),(0 2,0 0))

    •     
  • MULTILINESTRING((0 3,1 2,2 2),(1 2,0 2,0 0))



So, it appears that SQL Server does not like any kind of line segment coincidence.  But... its MakeValid function will still let you incorporate the results from the other processors into a SQL server database.  However, I'm not sure that turning a single line with a spike into a multi-line won't wreak havoc with algorithms that are only expecting single lines.



#18

Ted, 
  
   Thanks for the info.  I agree that turning a single string line into multi string line needs to be monitored.  I think it is reasonable though.  We are looking to make the change in the core code here as well.  We are testing now with the raw objects and if everything goes well we will have them in after a week or so and you can try them out of you like in our daily developer builds.  I am thinking moire and more about using MEF to allow us to replace these kinds of features and give devleopers more choice to change out our internal logic.  Thanks to you Ted, I have seen the MEF light and we use it in a bunch of stuff here like out new WMS server and new Map Suite Explorer.  It really rocks.  Also we will keep NTS around as it has some function line in memory R-Tree and some other goodies that are worth the dependency. 
  
 David

#19

Ted,  
  
 Could you re-attach the mpnSQLGeometryFactory.cs file you posted as it wont server it correctly.  Just rename the extension to .txt so the web server doesn’t get upset. 
  
   I would like to use more factory stuff or even more static methods but the general developer has a hard time learning them. :-(  
  
 David

#20

I have attached the renamed file.   Hope it helps.   And, yes, all of these methods are implemented as statics.



mpnSQLGeometryFactory.txt (12.1 KB)