Finding Intersection Points of Linestrings and Multilinestrings

[mindspit]

I am trying to find the all Intersection Points of
1) a Linestring with a Polygon
and
1) a Linestring with a Multilinestring
I am seeking advice on how to implement those two functions.

I guess that
1)in the 1st case [a Linestring with a Polygon ]
I am not intrested in finding if the linestring is within the polygon,
i am only intrested in finding the crossing point of the line string
with the polygon exterior or interior line.So i guess that i should
check for intersections of the Linestring with
a)the exterior ring of the polygon ( ExteriorRing which is a
LinearRing)
b)the interior line of the polygon ( InteriorRings which is an array
of LineStrings)

2)in the 2nd case [a Linestring with a Multilinestrings]
I will get the MultiLineString.Geometries which are linestrings and
check for intersections with my line.
Are there any special nts algorithms i should know about when i am
searching for the intersection points ?

Thank you,
Minspit

[Markus Schaber]

Hi,

On May 20, 3:37 pm, mindspit <agelospanagiota...@gmail.com> wrote:

> I guess that
> 1)in the 1st case [a Linestring with a Polygon ]
> I am not intrested in finding if the linestring is within the polygon,
> i am only intrested in finding the crossing point of the line string
> with the polygon exterior or interior line.So i guess that i should
> check for intersections of the Linestring with
> a)the exterior ring of the polygon ( ExteriorRing which is a
> LinearRing)
> b)the interior line of the polygon ( InteriorRings which is an array
> of LineStrings)

Polygons have a Boundary, intersect the Boundary with your query
LineString.

[FObermaier]

Hi, at

http://www.google.de/url?sa=t&source=web&ct=res&cd=1&url=http%3A%2F%2Fwww.foss4g2007.org%2Fpresentations%2Fviewattachment.php%3Fattachment_id%3D35&ei=Kq4aSvuTGZKysAabwqGRAg&usg=AFQjCNFr9y4XMJaY689XVQmqz0ukpjLPXw&sig2=b9QrbHFPnQxvSdivH6jkVw

you may download a ppt called jts-secrets, in which you find some
information on noding and polygonalization. Instead to polygonize it
may be suffcient to use some sort of difference to get the
intersection points. There is a sample of that in the
NetTopologySuite.Samples.Console\Technique
\LineStringSelfIntersections.cs, so I suppose it will work with nts as
well.

Hth
FObermaier

[Diego Guidi]

> http://www.google.de/url?sa=t&source=web&ct=res&cd=1&url=http%3A%2F%2...

>
> you may download a ppt called jts-secrets, in which you find some
> information on noding and polygonalization. Instead to polygonize it
> may be suffcient to use some sort of difference to get the
> intersection points.

Thanks for sharing this.

[Ted Macy]

Is the prepared geometry available in NTS?

[Diego Guidi]

> Is the prepared geometry available in NTS?

nope :(
and, I'm sorry, no plans about how to insert this.

[mindspit]

any idea on how to improve these algorithms ?

' ==================== Intersection Points With Polygon
================================================================

Public Shared Function findIntersectionPointsWithPolygon(ByVal aPoint
As Geometries.Point, ByVal aPolygon As Geometries.Polygon) As List(Of
Geometries.Point)
Dim intersectionPoints As New List(Of Geometries.Point)
Dim pm As New PrecisionModel
(GisSharpBlog.NetTopologySuite.Geometries.PrecisionModels.FloatingSingle)
Dim GSfactory As New Geometries.GeometryFactory(pm, 2100)
'Dim GSfactory As New Geometries.GeometryFactory
Dim exteriorConn As Geometries.LinearRing =
aPolygon.ExteriorRing
Debug.Print(aPolygon.Boundary.ToString)


For iExteriorPoint As Integer = 0 To
exteriorConn.Coordinates.Length - 2
Dim Line1coord1 As Geometries.Point =
exteriorConn.GetPointN(iExteriorPoint)
Dim Line1coord2 As Geometries.Point =
exteriorConn.GetPointN(iExteriorPoint + 1)

Dim rli As New
GisSharpBlog.NetTopologySuite.Algorithm.NonRobustLineIntersector()
rli.ComputeIntersection(aPoint.Coordinate,
Line1coord1.Coordinate, Line1coord2.Coordinate)
'Returns the number of intersection points found. This
will be either 0, 1 or 2.
If rli.HasIntersection = True Or rli.IntersectionNum <> 0
Then
Dim intersections As Integer = rli.IntersectionNum
For i As Integer = 0 To intersections - 1
Dim IntCoord As Geometries.Coordinate =
rli.GetIntersection(i)
Dim IntPoint As Geometries.Point =
GSfactory.CreatePoint(IntCoord)
intersectionPoints.Add(IntPoint)
Debug.Print("found intersection point too!")
Next
End If

Next
Dim interiorConns() As Geometries.LineString =
aPolygon.InteriorRings
For iInter As Integer = 0 To interiorConns.Count - 1
Dim interiorConn As Geometries.LinearRing = interiorConns
(iInter)
For interiorPoint As Integer = 0 To
interiorConn.Coordinates.Length - 2
Dim Line1coord1 As Geometries.Point =
exteriorConn.GetPointN(interiorPoint)
Dim Line1coord2 As Geometries.Point =
exteriorConn.GetPointN(interiorPoint + 1)

Dim rli As New
GisSharpBlog.NetTopologySuite.Algorithm.NonRobustLineIntersector()
rli.ComputeIntersection(aPoint.Coordinate,
Line1coord1.Coordinate, Line1coord2.Coordinate)
'Returns the number of intersection points found. This
will be either 0, 1 or 2.
If rli.HasIntersection = True Or rli.IntersectionNum
<> 0 Then
Dim intersections As Integer = rli.IntersectionNum
For i As Integer = 0 To intersections - 1
Dim IntCoord As Geometries.Coordinate =
rli.GetIntersection(i)
Dim IntPoint As Geometries.Point =
GSfactory.CreatePoint(IntCoord)
intersectionPoints.Add(IntPoint)
Debug.Print("found intersection point too!")
Next
End If
Next
Next

Return intersectionPoints
End Function

=================================== Intersection Line With LinearRing
========================================================
Public Shared Function findIntersectionLineWithLR(ByVal chopline As
Geometries.LineString, ByVal LR As Geometries.LinearRing) As List(Of
Geometries.Point)
Dim intersectionPoints As New List(Of Geometries.Point)
Dim minDist As Double = Double.MaxValue

Dim pm As New PrecisionModel
(GisSharpBlog.NetTopologySuite.Geometries.PrecisionModels.FloatingSingle)
Dim GSfactory As New Geometries.GeometryFactory(pm, 2100)
'Dim GSfactory As New Geometries.GeometryFactory

'A LineIntersector is an algorithm that can both test whether
two line segments intersect and compute the intersection point if they
do. The intersection point may be computed in a precise or non-
precise manner. Computing it precisely involves rounding it to an
integer. (This assumes that the input coordinates have been made
precise by scaling them to an integer grid.)
For iExteriorPoint As Integer = 0 To LR.NumPoints - 2
Dim Line1coord1 As Geometries.Point = LR.GetPointN
(iExteriorPoint)
Dim Line1coord2 As Geometries.Point = LR.GetPointN
(iExteriorPoint + 1)
For iLinePoint As Integer = 0 To chopline.NumPoints - 2
Dim Line2coord1 As ICoordinate = chopline.GetPointN
(iLinePoint).Coordinate
Dim Line2coord2 As ICoordinate = chopline.GetPointN
(iLinePoint + 1).Coordinate
'Dim seg As Geometries.LineSegment = New
Geometries.LineSegment(Line2coord1, Line2coord2)
DoEvents()
Dim rli As New
GisSharpBlog.NetTopologySuite.Algorithm.RobustLineIntersector()
rli.ComputeIntersection(Line1coord1.Coordinate,
Line1coord2.Coordinate, Line2coord1.CoordinateValue,
Line2coord2.CoordinateValue)
'Returns the number of intersection points found. This
will be either 0, 1 or 2.
If rli.HasIntersection = True Then
If rli.IsProper Then
DebugWindow.AddToDebug("is proper")
End If

Dim intersections As Integer = rli.IntersectionNum
For i As Integer = 0 To intersections - 1
Dim IntCoord As Geometries.Coordinate =
rli.GetIntersection(i)
Dim IntPoint As Geometries.Point =
GSfactory.CreatePoint(IntCoord)

Debug.Print("found intersection point too!")
DoEvents()
intersectionPoints.Add(IntPoint)
Next
End If
Next
Next
Return intersectionPoints
End Function

[FObermaier]

Hi mindspit,
without having taken a deep look into your code, how about something
like this?

%<-----
using System;
using System.Collections.Generic;
using GeoAPI.Geometries;
using GisSharpBlog.NetTopologySuite.Geometries;
using GisSharpBlog.NetTopologySuite.IO;

namespace GisSharpBlog.NetTopologySuite.Samples.Technique
{
/// <summary>
/// Shows a techinque for retrieving the location of
/// intersection Points between two geometries
/// </summary>
public class IntersectionPoints
{
public static void TestTwoLinestrings()
{
var rdr = new WKTReader();
var ls1 = (ILineString) rdr.Read("LINESTRING( 0 0, 5 5, 10
0 )");
var ls2 = (ILineString) rdr.Read("LINESTRING( 0 5, 5 0, 10
5 )");

Console.WriteLine(string.Format("Intersection points of
\n'{0}' and\n'{1}':", ls1, ls2));
IGeometry pts = GetIntersectionPoints(ls1, ls2);
Console.WriteLine(pts.ToString());
}

public static void TestLinestringWithPolygon()
{
var rdr = new WKTReader();
var ls = (ILineString)rdr.Read("LINESTRING( -5 10, 25
10 )");
var pl = (IPolygon)rdr.Read("POLYGON(( 0 0, 0 20, 20 20,
20 0, 0 0 ),( 5 5, 15 5, 15 15, 5 15, 5 5 ))");

Console.WriteLine(string.Format("Intersection points of
\n'{0}' and\n'{1}':", ls, pl));
IGeometry pts = GetIntersectionPoints(ls, pl);
Console.WriteLine(pts.ToString());

}
/// <summary>
/// Gets the intersection points between two LineStrings
/// </summary>
/// <param name="ls1">1st LineString</param>
/// <param name="ls2">2nd LineString</param>
/// <returns></returns>
public static IGeometry GetIntersectionPoints(ILineString ls1,
ILineString ls2)
{
IGeometry uls = ls1.Union(ls2);
IGeometry lep1 = GetEndPoints(ls1);
IGeometry lep2 = GetEndPoints(ls2);
IGeometry lep = lep1.Union(lep2);
IGeometry nuls = uls.Union(lep);
IGeometry nlep = GetEndPoints(nuls);

return nlep.Difference(lep);
}
/// <summary>
/// Gets the intersection points between a Linestring and the
ExteriorRing and InteriorRings of a Polygon
/// </summary>
/// <param name="ls">LineString geometry</param>
/// <param name="pl">Polygon geometry</param>
/// <returns></returns>
public static IGeometry GetIntersectionPoints(ILineString ls,
IPolygon pl)
{
IGeometry pts = GetIntersectionPoints(ls,
pl.ExteriorRing);
foreach (ILineString s in pl.InteriorRings)
{
pts = pts.Union(GetIntersectionPoints(ls, s));
}
return pts;
}


/// <summary>
/// Gets endpoints of LineString and MultiLineString
Geometries
/// Original code from
GisSharpBlog.NetTopologySuite.Samples.Technique.LineStringSelfIntersections.cs
/// </summary>
/// <param name="g">Linear geometry</param>
/// <returns>Multipoint geometry</returns>
private static IGeometry GetEndPoints(IGeometry g)
{
var endPtList = new List<ICoordinate>();
if (g is ILineString)
{
var line = (ILineString) g;
endPtList.Add(line.GetCoordinateN(0));
endPtList.Add(line.GetCoordinateN(line.NumPoints -
1));
}
else if (g is IMultiLineString)
{
var mls = (IMultiLineString) g;
for (int i = 0; i < mls.NumGeometries; i++)
{
var line = (ILineString) mls.GetGeometryN(i);
endPtList.Add(line.GetCoordinateN(0));
endPtList.Add(line.GetCoordinateN(line.NumPoints -
1));
}
}
ICoordinate[] endPts = endPtList.ToArray();
return GeometryFactory.Default.CreateMultiPoint(endPts);
}
}
}

----->%

hth
FObermaier

[mindspit]

This produces the same results i think. Your code executes faster
though. I had to make some changes since it was not handling
geometrycollection correctly
I think the result though are not correct.
take a look at this screen shot:
http://energy.chemeng.ntua.gr/result.jpg
the multicolored line is the 1st line and the black line is the
multilinestring or polygon.
The problem is that the point found ( the line is changing color in
that point ) is not correct for some reason. This does not always
produces wrong results.

> ...
>
> read more »

[mindspit]

well my fault ! i just found out that the code works ok. i was making
a wrong check.
sorry and thank you very much again.

> ...
>
> read more »