Top 5 Recent Articles
ARTICLES CATEGORIES
- Algorithms (22)
- All (399)
- Biography (1)
- Blog (44)
- Business Requirements (1)
- Commentary (1)
- Conversion (2)
- Customers (2)
- Data Models (1)
- Education (2)
- GeoRaptor (13)
- GPS (1)
- Image Processing (2)
- Import Export (8)
- Licensing (2)
- LiDAR (1)
- Linear Referencing (4)
- Manifold GIS (3)
- Mapping (1)
- MySQL Spatial (7)
- Networking and Routing (including Optimization) (5)
- Open Source (18)
- Oracle Spatial and Locator (194)
- Partitioning (1)
- PostGIS (36)
- Projections (1)
- Published Articles (1)
- qGIS (1)
- Recommendations (1)
- Services (1)
- Software Change Log (1)
- Source Code (37)
- Space Curves (9)
- Spatial Database Functions (109)
- Spatial DB comparison (1)
- Spatial XML Processing (11)
- SQL Server Spatial (92)
- Standards (3)
- Stored Procedure (17)
- Tessellation or Gridding (10)
- Tools (2)
- Topological Relationships (1)
- Training (2)
- Triangulation (2)
Noding and building a polygon from single, overlapping linestrings
The Spatial Companion 4 Oracle (SC4O) package (built using Java Topology Suite components) contains a method called ST_PolygonBuilder that can then form polygons from linestrings.
However, ST_PolygonBuilder will not form polygons where it detects an unformed intersection: in this situation ST_PolygonBuilder has to be used with another SC4O method called ST_NodeLinestrings.
ST_NodeLinestrings forms all intersections between all linestrings in a set.
The following example shows how to use these methods to build a single polygon from un-noded intersecting linestrings.
Overlapping Linestrings
Here is a set of un-noded linestrings.
SELECT SDO_GEOMETRY('LINESTRING(5 14, 13 10)',28355) AS line FROM dual UNION ALL
SELECT SDO_GEOMETRY('LINESTRING(13 2, 5 -1)',28355) FROM dual UNION ALL
SELECT SDO_GEOMETRY('LINESTRING(-1 10, 7 14)',28355) FROM dual UNION ALL
SELECT SDO_GEOMETRY('LINESTRING(1 12, -2 5)',28355) FROM dual UNION ALL
SELECT SDO_GEOMETRY('LINESTRING(-2 7, 1 0)',28355) FROM dual UNION ALL
SELECT SDO_GEOMETRY('LINESTRING(-1 2, 7 -1)',28355) FROM dual UNION ALL
SELECT SDO_GEOMETRY('LINESTRING(11 12, 14 5)',28355) FROM dual UNION ALL
SELECT SDO_GEOMETRY('LINESTRING(11 0, 14 7)',28355) FROM dual;
These lines are shown as follows.
Noded Linestrings
We can compute the intersection points and create a resultant linestring from them as follows.
SELECT sc4o.ST_NodeLinestrings(CURSOR(SELECT SDO_GEOMETRY('LINESTRING(5 14, 13 10)',28355) AS line FROM dual UNION ALL
SELECT SDO_GEOMETRY('LINESTRING(13 2, 5 -1)',28355) FROM dual UNION ALL
SELECT SDO_GEOMETRY('LINESTRING(-1 10, 7 14)',28355) FROM dual UNION ALL
SELECT SDO_GEOMETRY('LINESTRING(1 12, -2 5)',28355) FROM dual UNION ALL
SELECT SDO_GEOMETRY('LINESTRING(-2 7, 1 0)',28355) FROM dual UNION ALL
SELECT SDO_GEOMETRY('LINESTRING(-1 2, 7 -1)',28355) FROM dual UNION ALL
SELECT SDO_GEOMETRY('LINESTRING(11 12, 14 5)',28355) FROM dual UNION ALL
SELECT SDO_GEOMETRY('LINESTRING(11 0, 14 7)',28355) FROM dual),1) AS nLines
FROM dual;
--
NLINES
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
SDO_GEOMETRY(2006,28355,NULL,
SDO_ELEM_INFO_ARRAY(1,2,1,5,2,1,9,2,1,13,2,1,17,2,1,21,2,1,25,2,1,29,2,1,33,2,1,37,2,1,41,2,1,45,2,1,49,2,1,53,2,1,57,2,1,61,2,1,65,2,1,69,2,1,73,2,1,77,2,1,81,2,1,85,2,1,89,2,1,93,2,1),
SDO_ORDINATE_ARRAY(5,14,6,13.5,6,13.5,11.5,10.7,11.5,10.7,13,10,13,2,11.6,1.5,11.6,1.5,6,-0.6,6,-0.6,5,-1,-1,10,0.5,10.7,0.5,10.7,6,13.5,6,13.5,7,14,1,12,0.5,10.7,0.5,10.7,-1.6,6,-1.6,6,-2,5,-2,7,-1.6,6,-1.6,6,0.4,1.5,0.4,1.5,1,0,-1,2,0.4,1.5,0.4,1.5,6,-0.6,6,-0.6,7,-1,11,12,11.5,10.7,11.5,10.7,13.6,6,13.6,6,14,5,11,0,11.6,1.5,11.6,1.5,13.6,6,13.6,6,14,7))
The linestring looks like this:
Build Polygon
We are now able to build our polygon.
SELECT sc4o.ST_PolygonBuilder(
sc4o.ST_NodeLinestrings(CURSOR(SELECT SDO_GEOMETRY('LINESTRING(5 14, 13 10)',28355) AS line FROM dual UNION ALL
SELECT SDO_GEOMETRY('LINESTRING(13 2, 5 -1)',28355) FROM dual UNION ALL
SELECT SDO_GEOMETRY('LINESTRING(-1 10, 7 14)',28355) FROM dual UNION ALL
SELECT SDO_GEOMETRY('LINESTRING(1 12, -2 5)',28355) FROM dual UNION ALL
SELECT SDO_GEOMETRY('LINESTRING(-2 7, 1 0)',28355) FROM dual UNION ALL
SELECT SDO_GEOMETRY('LINESTRING(-1 2, 7 -1)',28355) FROM dual UNION ALL
SELECT SDO_GEOMETRY('LINESTRING(11 12, 14 5)',28355) FROM dual UNION ALL
SELECT SDO_GEOMETRY('LINESTRING(11 0, 14 7)',28355) FROM dual),1),1) AS nPoly
FROM dual;
--
NPOLY
-------------------------------------------------------------------------------------------------------
SDO_GEOMETRY(2003,28355,NULL,
SDO_ELEM_INFO_ARRAY(1,1003,1),
SDO_ORDINATE_ARRAY(6,13.5,0.5,10.7,-1.6,6,0.4,1.5,6,-0.6,11.6,1.5,13.6,6,11.5,10.7,6,13.5))
This looks like the following.
UPDATE
I was asked by a colleague how to process the results of ST_NodeLinestrings more intelligently. You will have noticed above that ST_NodeLineStrings returns a single linestring from all the input strings. Now this is fine and efficient from its perspective, but what if you wanted to filter some of the linestrings in that multilinestring before calling ST_PolygonBuilder. There are lots of reasons why you might want to do this. Perhaps you are only interested in building polygons from those noded linestrings that fell inside some sort of filter polygon (fence).
How can we do this?
1. Exploding or Vectorising the Noded Linestring
The first step is to extract a set of segments from the linestring.
This website has produced blog articles showing how to “explode” a single multi-part geometry into its individual parts; it has also shown how to “segmentize” or “vectorize” a linestring or polygon object into a set of 2 vertex, linestrings.
In this situation we will use the “vectorize” approach.
In the free GEOM package on this website, there exists a function called GetVector (ST_Vectorize or ST_Segmentize in the code that ships with my book).
SELECT codesys.T_Vector(t.Id,t.element_id,t.subelement_id,t.startCoord,t.endCoord).AsSdoGeometry(28355) AS vector
FROM TABLE(geom.GetVector(
sc4o.ST_NodeLinestrings(
CURSOR(SELECT SDO_GEOMETRY('LINESTRING(5 14, 13 10)',28355) AS line FROM dual UNION ALL
SELECT SDO_GEOMETRY('LINESTRING(13 2, 5 -1)',28355) FROM dual UNION ALL
SELECT SDO_GEOMETRY('LINESTRING(-1 10, 7 14)',28355) FROM dual UNION ALL
SELECT SDO_GEOMETRY('LINESTRING(1 12, -2 5)',28355) FROM dual UNION ALL
SELECT SDO_GEOMETRY('LINESTRING(-2 7, 1 0)',28355) FROM dual UNION ALL
SELECT SDO_GEOMETRY('LINESTRING(-1 2, 7 -1)',28355) FROM dual UNION ALL
SELECT SDO_GEOMETRY('LINESTRING(11 12, 14 5)',28355) FROM dual UNION ALL
SELECT SDO_GEOMETRY('LINESTRING(11 0, 14 7)',28355) FROM dual),1))) t;
-- Results
--
VECTOR
------
SDO_GEOMETRY(2002,28355,NULL,SDO_ELEM_INFO_ARRAY(1,2,1),SDO_ORDINATE_ARRAY(5.0,14.0, 6.0,13.5))
SDO_GEOMETRY(2002,28355,NULL,SDO_ELEM_INFO_ARRAY(1,2,1),SDO_ORDINATE_ARRAY(6.0,13.5, 11.5,10.7))
SDO_GEOMETRY(2002,28355,NULL,SDO_ELEM_INFO_ARRAY(1,2,1),SDO_ORDINATE_ARRAY(11.5,10.7, 13.0,10.0))
SDO_GEOMETRY(2002,28355,NULL,SDO_ELEM_INFO_ARRAY(1,2,1),SDO_ORDINATE_ARRAY(13.0,2.0, 11.6,1.5))
SDO_GEOMETRY(2002,28355,NULL,SDO_ELEM_INFO_ARRAY(1,2,1),SDO_ORDINATE_ARRAY(11.6,1.5, 6.0,-0.6))
SDO_GEOMETRY(2002,28355,NULL,SDO_ELEM_INFO_ARRAY(1,2,1),SDO_ORDINATE_ARRAY(6.0,-0.6, 5.0,-1.0))
SDO_GEOMETRY(2002,28355,NULL,SDO_ELEM_INFO_ARRAY(1,2,1),SDO_ORDINATE_ARRAY(-1.0,10.0, 0.5,10.7))
SDO_GEOMETRY(2002,28355,NULL,SDO_ELEM_INFO_ARRAY(1,2,1),SDO_ORDINATE_ARRAY(0.5,10.7, 6.0,13.5))
SDO_GEOMETRY(2002,28355,NULL,SDO_ELEM_INFO_ARRAY(1,2,1),SDO_ORDINATE_ARRAY(6.0,13.5, 7.0,14.0))
SDO_GEOMETRY(2002,28355,NULL,SDO_ELEM_INFO_ARRAY(1,2,1),SDO_ORDINATE_ARRAY(1.0,12.0, 0.5,10.7))
SDO_GEOMETRY(2002,28355,NULL,SDO_ELEM_INFO_ARRAY(1,2,1),SDO_ORDINATE_ARRAY(0.5,10.7, -1.6,6.0))
SDO_GEOMETRY(2002,28355,NULL,SDO_ELEM_INFO_ARRAY(1,2,1),SDO_ORDINATE_ARRAY(-1.6,6.0, -2.0,5.0))
SDO_GEOMETRY(2002,28355,NULL,SDO_ELEM_INFO_ARRAY(1,2,1),SDO_ORDINATE_ARRAY(-2.0,7.0, -1.6,6.0))
SDO_GEOMETRY(2002,28355,NULL,SDO_ELEM_INFO_ARRAY(1,2,1),SDO_ORDINATE_ARRAY(-1.6,6.0, 0.4,1.5))
SDO_GEOMETRY(2002,28355,NULL,SDO_ELEM_INFO_ARRAY(1,2,1),SDO_ORDINATE_ARRAY(0.4,1.5, 1.0,0.0))
SDO_GEOMETRY(2002,28355,NULL,SDO_ELEM_INFO_ARRAY(1,2,1),SDO_ORDINATE_ARRAY(-1.0,2.0, 0.4,1.5))
SDO_GEOMETRY(2002,28355,NULL,SDO_ELEM_INFO_ARRAY(1,2,1),SDO_ORDINATE_ARRAY(0.4,1.5, 6.0,-0.6))
SDO_GEOMETRY(2002,28355,NULL,SDO_ELEM_INFO_ARRAY(1,2,1),SDO_ORDINATE_ARRAY(6.0,-0.6, 7.0,-1.0))
SDO_GEOMETRY(2002,28355,NULL,SDO_ELEM_INFO_ARRAY(1,2,1),SDO_ORDINATE_ARRAY(11.0,12.0, 11.5,10.7))
SDO_GEOMETRY(2002,28355,NULL,SDO_ELEM_INFO_ARRAY(1,2,1),SDO_ORDINATE_ARRAY(11.5,10.7, 13.6,6.0))
SDO_GEOMETRY(2002,28355,NULL,SDO_ELEM_INFO_ARRAY(1,2,1),SDO_ORDINATE_ARRAY(13.6,6.0, 14.0,5.0))
SDO_GEOMETRY(2002,28355,NULL,SDO_ELEM_INFO_ARRAY(1,2,1),SDO_ORDINATE_ARRAY(11.0,0.0, 11.6,1.5))
SDO_GEOMETRY(2002,28355,NULL,SDO_ELEM_INFO_ARRAY(1,2,1),SDO_ORDINATE_ARRAY(11.6,1.5, 13.6,6.0))
SDO_GEOMETRY(2002,28355,NULL,SDO_ELEM_INFO_ARRAY(1,2,1),SDO_ORDINATE_ARRAY(13.6,6.0, 14.0,7.0))
This looks like the following.
2. Create a Fence Polygon
I have created a fence polygon (using GeoRaptor) that can be used to clip off those 2 vertex segments that exist outside the vectors that define the polygon.
This is as follows:
SELECT SDO_GEOMETRY(2003,28355,NULL, SDO_ELEM_INFO_ARRAY(1,1003,1), SDO_ORDINATE_ARRAY(-1.6,4.9, -2.2,6.0, -0.2,11.0, 6.1,14.1, 11.6,11.3, 13.9,6.0, 11.9,1.2, 6.3,-1.0, 1.3,0.6, -0.2,1.1, -1.3,4.1, -1.6,4.9)) AS geom FROM dual;
This looks like the following.
3. Filter and Polygonize
Finally, we can implement the filter and then send the filtered vectors into ST_PolygonBuilder as follows.
WITH FILTER AS (
SELECT SDO_GEOMETRY(2003,28355,NULL,
SDO_ELEM_INFO_ARRAY(1,1003,1),
SDO_ORDINATE_ARRAY(-1.6,4.9, -2.2,6.0, -0.2,11.0, 6.1,14.1, 11.6,11.3, 13.9,6.0, 11.9,1.2, 6.3,-1.0, 1.3,0.6, -0.2,1.1, -1.3,4.1, -1.6,4.9)) AS geom
FROM dual
)
SELECT sc4o.ST_PolygonBuilder(
(CURSOR(SELECT vector
FROM (SELECT codesys.T_Vector(t.Id,t.element_id,t.subelement_id,t.startCoord,t.endCoord).AsSdoGeometry(28355) AS vector
FROM TABLE(geom.GetVector(
sc4o.ST_NodeLinestrings(CURSOR(SELECT SDO_GEOMETRY('LINESTRING(5 14, 13 10)',28355) AS line FROM dual UNION ALL
SELECT SDO_GEOMETRY('LINESTRING(13 2, 5 -1)',28355) FROM dual UNION ALL
SELECT SDO_GEOMETRY('LINESTRING(-1 10, 7 14)',28355) FROM dual UNION ALL
SELECT SDO_GEOMETRY('LINESTRING(1 12, -2 5)',28355) FROM dual UNION ALL
SELECT SDO_GEOMETRY('LINESTRING(-2 7, 1 0)',28355) FROM dual UNION ALL
SELECT SDO_GEOMETRY('LINESTRING(-1 2, 7 -1)',28355) FROM dual UNION ALL
SELECT SDO_GEOMETRY('LINESTRING(11 12, 14 5)',28355) FROM dual UNION ALL
SELECT SDO_GEOMETRY('LINESTRING(11 0, 14 7)',28355) FROM dual),1))) t
) f,
FILTER e
WHERE sdo_geom.relate(f.vector,
'DETERMINE',
e.geom,
0.005) = 'INSIDE')),1) AS poly
FROM Dual;
-- Results
--
SDO_GEOMETRY(2003,28355,NULL,SDO_ELEM_INFO_ARRAY(1,1003,1),SDO_ORDINATE_ARRAY(6.0,-0.6, 11.6,1.5, 13.6,6.0, 11.5,10.7, 6.0,13.5, 0.5,10.7, -1.6,6.0, 0.4,1.5, 6.0,-0.6))
This results in the following.
4. Conclusion
There are situations where the linework may be incomplete. See this article to see what can be done.
The following image of a cadastral subdivision was actually constructed from a set of input linestrings that fully described the resultant polygons but which had the following spatial problems that needed to be resolved before polygons could be resulted:
- Overshooting lines;
- Undershooting lines (gap of various distances);
- Superfluous lines that did not form part of any polygon.
The above techniques, coupled with use of ST_Extend and ST_Snap functions (elsewhere described) were used to filtering, vectorization, noding and polygon building to create the final output.
I hope this is of use to someone out there.