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
Line Simplification
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.
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
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 :)
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
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.
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
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
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
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.
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)
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
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());
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.
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
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
I have attached the renamed file. Hope it helps. And, yes, all of these methods are implemented as statics.
mpnSQLGeometryFactory.txt (12.1 KB)
Ted,
Just posting to close this thread so we don’t see it in our forum tracker. We are planning to replace most of NTS with the SQL CLR Types. Thanks for the information! We might also put a bunch of static methods for doing geometric operations on the Feature as well.
David
Sorry about posting back. I know you need to post last to close the forum items. But I just had to tell you how excited I was to think about having static factory methods on the feature. Given that you have your own objects, it really makes a lot of sense to place them there.
Ted,
I’m glad I could get you excited. I will let you know how we propose to do it and get your feedback. You could also do it through extension methods as well and just tack them on. The only reason we didn’t do this before is that typically if you make methods static most people new to programming won’t find them and then they think your objects cannot do anything. :-(
David