topic Re: SDE MSSQL SqlSpatial Geometry Self Intersects problem in Data Management Questions

SDE MSSQL SqlSpatial Geometry Self Intersects problem

ChrisSmith — Thu, 30 Dec 2010 08:13:29 GMT

Hi

I have created a SqlGeometry using the Microsoft.SqlServer.Types SqlGeometryBuilder, the geometry IsValid and IsSimple but when trying to view it in ArcMap it wont draw, when trying to export to a non SqlSpatial SDE table it complains that the polygon is self intersecting. The geometry uses srid 27700 (BNG) and is viewable in SQL management Studio, I have tried various methods that are suggested to correct the geometry including MakeValid(), STUnion(STStartPoint()) on the SqlSpatial side but since it is valid and doesnt self intersect then it doesnt fix the issue.

Any help is appreciated, Geometry details below

Regards

chris

Geometry as Text...(after trying MakeValid()/StUnion(STStartPoint))

POLYGON ((531405.73999977112 104148.89000034332, 531414.71999979019 104179.65999984741, 531407.15999984741 104182.27999973297, 531406.94000005722 104182.35000038147, 531404.44000005722 104177.02000045776, 531401.59000015259 104168.47000026703, 531401.59999990463 104168.5, 531401.48999977112 104168.19999980927, 531395.61999988556 104152.19999980927, 531405.73999977112 104148.89000034332))

Geometry as Gml...

<Polygon xmlns="http://www.opengis.net/gml">
<exterior>
    <LinearRing>
      <posList>531405.73999977112 104148.89000034332 531414.71999979019 104179.65999984741 531407.15999984741 104182.27999973297 531406.94000005722 104182.35000038147 531404.44000005722 104177.02000045776 531401.59000015259 104168.47000026703 531401.59999990463 104168.5 531401.48999977112 104168.19999980927 531395.61999988556 104152.19999980927 531405.73999977112 104148.89000034332</posList>
    </LinearRing>
</exterior>
</Polygon>

Original gml entry from file I am importing...

<gml:Polygon srsName='osgb:BNG'>
<gml:outerBoundaryIs>
<gml:LinearRing>
<gml:coordinates>531406.94,104182.35 531404.44,104177.02 531401.59,104168.47 531401.60,104168.50 531401.49,104168.20 531395.62,104152.20 531405.74,104148.89 531414.72,104179.66 531407.16,104182.28 531406.94,104182.35</gml:coordinates>
</gml:LinearRing>
</gml:outerBoundaryIs>
</gml:Polygon>

Re: SDE MSSQL SqlSpatial Geometry Self Intersects problem

ChrisSmith — Thu, 30 Dec 2010 08:15:24 GMT

I should add that this table is registered with SDE and if I delete this polygon then all my other polygons in the same layer can display without problem in ArcMap.

Re: SDE MSSQL SqlSpatial Geometry Self Intersects problem

VinceAngelo — Thu, 30 Dec 2010 11:00:10 GMT

I made a line out of polygon shell, and generated a shapefile from it, then inspected
the line. That shape does self-intersect, in the vicinity of 531401.6,104168.5.

- V

Re: SDE MSSQL SqlSpatial Geometry Self Intersects problem

ChrisSmith — Thu, 30 Dec 2010 11:14:46 GMT

Hi Vince

Thanks for the post

I posted the same on the SqlSpatial forums and Tanoshimi points out it doesn't self intersect,
so have drawn it on a piece of squared paper and it doesn't appear to self intersect.

I also tried the same process as you have done i.e. created a polyline from the points loaded as an XY Event layer and it doesn't look like it crosses to me.

Appreciate the help and I will have another look at it and see if I find anything different.

The post on the SqlSpatial forum if your interested 🙂

http://social.msdn.microsoft.com/Forums/en-US/sqlspatial/thread/d844071c-68b6-4ce8-bbda-05f19ac4b9e0

Cheers

chris

Re: SDE MSSQL SqlSpatial Geometry Self Intersects problem

VinceAngelo — Sat, 11 Dec 2021 07:22:49 GMT

The ArcSDE topology engine is quite mature. It uses Clementini's topology rules,
which includes the definition of a simple line. All polygon rings must adhere to
simple line restrictions, and this line overlaps itself (linear intersection, not point).

C:\>sdequery -l testshape2,shape -F1 SM_II:line:531404.44,104177.02,531401.59,104168.47 -v
ArcSDE 9.3 Generic Query Tool            Thu Dec 30 08:53:42 2010
------------------------------------------------------------------------
         1
            objectid: 5
               shape: Line shape (1 part, 2 vertices)
                    1   531404.440000, 104177.020000
                    2   531401.590000, 104168.470000
         2
            objectid: 6
               shape: Line shape (1 part, 2 vertices)
                    1   531401.590000, 104168.470000
                    2   531401.600000, 104168.500000
2 rows found in 31.00 ms
 
C:\>sdequery -l testshape2,shape -F1 SM_II:line:531401.59,104168.47,531401.60,104168.50 -v
ArcSDE 9.3 Generic Query Tool            Thu Dec 30 08:53:42 2010
------------------------------------------------------------------------
         1
            objectid: 5
               shape: Line shape (1 part, 2 vertices)
                    1   531404.440000, 104177.020000
                    2   531401.590000, 104168.470000
         2
            objectid: 6
               shape: Line shape (1 part, 2 vertices)
                    1   531401.590000, 104168.470000
                    2   531401.600000, 104168.500000
2 rows found in 47.00 ms

If you do the math, you'll see that segments 5 & 6 have reciprocal slopes;
since they share a vertex, they overlap.

In order for vertex #6 to be included, several points would need to be added,
including a point to make a polygon of the deformed interior polygon ring, a
vertex for the interior ring to touch, and vertices to open and close the interior
ring.

- V

Re: SDE MSSQL SqlSpatial Geometry Self Intersects problem

ChrisSmith — Thu, 30 Dec 2010 13:21:59 GMT

Hi Vince

Thanks for the help, will post your response back to the SqlSpatial forum, see what reply I get there.

cheers

chris

Re: SDE MSSQL SqlSpatial Geometry Self Intersects problem

VinceAngelo — Thu, 30 Dec 2010 14:09:46 GMT

SQL-Server isn't handling the geometry right, but the root of the problem is your
GML source, which also has a topology bug.

I must admit that I also find the representation errors (two places in, twelve out)
disturbing as well -- it looks as though the values have been stored in single precision.

- V

Re: SDE MSSQL SqlSpatial Geometry Self Intersects problem

ChrisSmith — Thu, 30 Dec 2010 19:09:22 GMT

Hi Vince

Is there any way of checking geometries to see if they are considered valid, the loaded dataset will have millions of records. If I remember correctly there was such an app called Checkgeometries that could be used to find invalid geometries in Oracle Spatial.

thanks

chris

Re: SDE MSSQL SqlSpatial Geometry Self Intersects problem

VinceAngelo — Thu, 30 Dec 2010 20:04:00 GMT

'sdelayer -o feature_info -r invalid' should scan a table for invalid shapes.

- V

Re: SDE MSSQL SqlSpatial Geometry Self Intersects problem

ChrisSmith — Fri, 31 Dec 2010 08:00:30 GMT

unfortunately the cmd ends when it hits the first self intersecting feature, it reports the following..

Total rows examined:       99460
Total invalid shapes:          0
Error: Linestring or poly boundary is self-intersecting (-155).
Error: Error in fetching row.

I have examined the features with fids of 99459,99460,99461,99462 but they all are simple polygons definitely not self intersecting so they appear to be fine, so not sure what order the data is examined in.

Interestingly I have located another dodgy geometry, this time the interior ring is self intersecting, gml below if you are interested...

<Polygon xmlns="http://www.opengis.net/gml">
<exterior>
    <LinearRing>
      <posList>529785.17001342773 180867.58999633789 529850.04000854492 180907.64001464844 529827.799987793 180940.95001220703 529767.10000610352 180902.35998535156 529785.17001342773 180867.58999633789</posList>
    </LinearRing>
</exterior>
<interior>
    <LinearRing>
      <posList>529786.55999755859 180893.41000366211 529790.07778930664 180895.52319335938 529786.32998657227 180902.80999755859 529807.55999755859 180915.42001342773 529811.73001098633 180908.5299987793 529786.55999755859 180893.41000366211</posList>
    </LinearRing>
</interior>
</Polygon>

Any other suggestions on how to detect these problem geometries?

thanks

chris

Re: SDE MSSQL SqlSpatial Geometry Self Intersects problem

ChrisSmith — Fri, 31 Dec 2010 09:35:05 GMT

Hi

I have loaded the geometry with the problem interior ring into a shapefile, it is clearly self intersecting when viewed in arcmap.

points from geometry in shapefile....
Part 0
529785.170 180867.590
529767.100 180902.360
529827.800 180940.950
529850.040 180907.640
529786.560 180868.450
529786.560 180868.450

Part 1
529786.560 180893.410
529811.730 180908.530
529807.560 180915.420
529786.330 180902.810
529790.100 180895.480

I then export the feature into sde and the process adds extra points I assume to fix the self intersecting issue.

The exported geometry is viewable in arcmap but if you look at point 1 & 4 they have the same values; is this not considered self intersecting?

points for geometry in sde...
Part 0
529785.170 180867.590
529767.100 180902.360
529827.800 180940.950
529850.040 180907.640
529786.560 180868.450

Part 1
529786.330 180902.810
529790.078 180895.523
529786.560 180893.410
529790.100 180895.480
529790.078 180895.523
529811.730 180908.530
529807.560 180915.420

cheers

chris

Re: SDE MSSQL SqlSpatial Geometry Self Intersects problem

VinceAngelo — Fri, 31 Dec 2010 11:16:26 GMT

The SE_shape_generate_polygon is reasonably adaptive. In this case, if you add the
missing closing vertex to the array, the API will nominate the ring that begins and
ends at 529790.078,180895.523 as a subpart (hole), then complete the primary ring.
Having determined that the subpart is not within its original parent, it is then promoted
to an independent part. Parts and subparts are permitted to touch at a single point
(but not share boundaries or area). The API will also demote rings which *are* within
other parts, making them subparts.

I was the course author for the (now retired) "Accessing SDE with 'C'" 3-day training
class. We spent the second half of the first day on Clemetini topology and relationships.
There was exercise code which permitted generation and comparison of shapes from
command-line arguments. Those exercises are gone, but the core parsing functions
live on, exposed in the se_toolkit DAT module, which is how I was able to assemble
and test your geometry.

- V

Re: SDE MSSQL SqlSpatial Geometry Self Intersects problem

ChrisSmith — Fri, 31 Dec 2010 12:37:03 GMT

Hi Vince

Once again thanks for the help!

I look forward to resurrecting my C-Api skills, been about 5 years but should be fun 😉

Do you still have the course notes that accompanied the exercises in particular the Clementini Topolgy section - or have a pointer to some reading material available on the web?

Happy New Year to you

chris

Re: SDE MSSQL SqlSpatial Geometry Self Intersects problem

VinceAngelo — Fri, 31 Dec 2010 13:10:00 GMT

I can't give away even old training materials (mostly bullet lists on which the instructor
needed to expound, anyway). All the concepts are available in the documentation, or
in User Conference proceeedings (1997 and/or 1998 -- I *did* say this was mature
technology, right?)

- V

BTW: The original "Clementini" paper, which I'll often go back to, is:

E. Clementini, P. Di Felice, and P. van Oosterom, "A Small Set of Formal Topological Relationships Suitable for End-User Interaction," in Advances in Spatial Databases - Third International Symposium, SSD '93. vol. 692, D. Abel and B. C. Ooi, Eds. Berlin: Springer-Verlag, 1993, pp. 277-295.

Re: SDE MSSQL SqlSpatial Geometry Self Intersects problem

EdKatibah — Tue, 04 Jan 2011 21:53:15 GMT

Hi Vince -

In the SQL Server Spatial world, this geometry does not self-intersect. Michael Kallay of the SQL Server Spatial development team has posted an explanation on this issue to the SQL Server Spatial Forum (http://social.msdn.microsoft.com/Forums/en-US/sqlspatial/thread/d844071c-68b6-4ce8-bbda-05f19ac4b9e0/).

Here is what the geometry looks like around Point 7, the suspected self-intersecting point, using SQL Server and the FME Universal Viewer:

I will work with the the SDE engineering team to look at how SQL Server Spatial and ArcGIS can more gracefully handle these kinds of situations.

Thanks,

- Ed Katibah

SQL Server Spatial

Re: SDE MSSQL SqlSpatial Geometry Self Intersects problem

VinceAngelo — Wed, 05 Jan 2011 02:51:55 GMT

The principal problem with using arbitrary precision with real-world coordinate data
is the implicit assertion of accuracy not present at input. The orginal data was
collected at centimeter scale. Varying the locations by a few hundred nanometers
can change topology, but if it does, then it becomes a data quality issue -- *should*
we trust spatial data for which the Heisenberg uncertainty principle applies?

There are a number of ways to process this data to remove the problematic vertices.
The simplest to code would be to perform angle calculation over three coordinate
sets -- vertices that belong in a shape at that scale would not bend the line by more
than 165 degrees (+/-) -- Whether this line bends by 180 degrees or 179.999999
degrees wouldn't matter in this sort of algorithm, just that you remove the vertex
that produces the shortest segment.

A more robust processing step would be to apply a full Douglas-Peucker generalization
to the polygon ring as a line, with a tolerance distance of, say, 1/20th the diagonal
of the bounding box (or just a fixed value, like 0.5 meters), then attempt to cast
the rings back into a polygon.

I have a tool that may be able to do this sort of processing (in a timely fashion with
millions of rows), but I'd have to play with an ASCII dump of the well-known polygon
text to figure out if this was a 20-minute hack or something more involved.

- V

Re: SDE MSSQL SqlSpatial Geometry Self Intersects problem

MichaelKallay — Wed, 05 Jan 2011 16:15:14 GMT

The last post suggests that the MS SQL Server exact computation is akin to splitting hair, and the ESRI computation with a margin of error is better in practice. Although the suggested margins (165 degrees or .5m or 1/20 of the bounding rectangle's diagonal) are much too broad for my liking, it may be a valid choice, but it is not necessarily better. Computations with margins cannot be done in a fully consistent way, and therefore cannot be made fully robust. The problem is articulated at http://people.csail.mit.edu/seth/pubs/taskforce/section3_10.html. The only known way to achieve full robustness is by using exact arithmetic. Since we at MS consider robustness paramount, we chose the (more sophisticated and more difficult) exact arithmetic approach, and we are very proud of its clean and fast implementation. Moreover, in our next relase (already available in a preview version) we have increased the resolution (of the integer space in which we perform our exact computations) from 27 to 48 bits of accuracy.

Michael Kallay, SQL Server spatial team

Re: SDE MSSQL SqlSpatial Geometry Self Intersects problem

VinceAngelo — Wed, 05 Jan 2011 20:47:01 GMT

ArcSDE has been using exact arithmetic for geometry computation since the technology
was aquired in 1995. What is now known as BASIC precision uses 31 bits; HIGH precision
(released with 9.0, and made default since 9.2) uses 64-bit integers (but is 53-bit, due to
double precision mantissa size). The system is very flexible for the different data units found
in international databases; the default values chosen by ArcGIS are optimized by coordinate
system (projection) for preservation of real-world spatial data to millimeter precision (which
is roughly one hundred times the accuracy of most of the spatial datasets I've ever used.) .

The distance parameter in Douglas-Peucker doesn't correspond to precision, but to deflection;
value selection is data dependent (and, to some degree, more art than science).

- V

Re: SDE MSSQL SqlSpatial Geometry Self Intersects problem

ChrisSmith — Mon, 10 Jan 2011 12:24:30 GMT

Hi Vince

Have been away for a week and it appears I have missed quite a bit!

Anyway what I need to be able to do is have a reasonably fast process to scan through 20+ million features to find out which are considered invalid by ESRI software.

Are you able to point me in the right direction? A function I can include in my code, an external library to reference or an executable I can run to select the problem geometries out would be desirable.

cheers

chris

Re: SDE MSSQL SqlSpatial Geometry Self Intersects problem

VinceAngelo — Mon, 10 Jan 2011 13:40:04 GMT

It looks like the 'sdelayer -o feature_info' capability isn't functional for SQL-Server.

What does 'sdelayer -o describe_long' report for the coordinate reference on your layer?
What command did you use to register the layer?

I prototyped a workaround, but it's not going to be pretty. You'll need a copy of se_toolkit
for the 'sdequery' and 'ascinfo' utilities, and you'll need to create a view of the layer that
dumps the well-known text of the geometries as either string (if it will fit in varchar(8000))
or text. Then you can query the registered rowid column and WKT with 'sdequery', and
pipe it through 'ascinfo' to reject the rows that fail SE_shape_generate_from_text, producing
an ASCII file with ID and problematic well-known text. If you want to go this route, it would
probably be easier to take this offline.

Unfortunately, I didn't have time to whip up some data massage classes to automate removal
of spurious jagged lines in geometry.

- V