Point of intersection of two Polylines

Theory

The point of intersection is a location where two line segments overlap. We can use the function that calculates the intersection of two planes to find the two possible points of intersections. Once we have these two points of intersections we can then calculate the length of the two polylines and the length from each vertex of the polylines to a point of intersection. The sum of the lengths of the vertices should be the length of the polyline in which the vertices belong to if the point of intersection is on the polyline. If the first point of intersection is not on one of the polylines we can then do the same calculations for the second possible point of intersection.

Application

This function will take in the four VELatLongs that define the end points of the two polyline line segments. We will first calculate the two possible points of intersections. We then will calculate the lengths of the two polylines and the distances from the vertices to the first point of intersection. We will then take the length of each polyline and subtract it by the lengths of its vertices to the point of intersection. In theory this should be 0 if the point of intersection is on the line. Since there is a 1% accuracy we will then check to see if the absolute value of this calculation is within 1% of the length of the longest polyline. If the point is not on one of the polylines then the calculation is repeated for the second point of intersection. This function will either return a VELatLong object for -1 if the lines do not intersect.

function pointOfIntersection(latlong1,latlong2,latlong3,latlong4)
{
var poi = intersectionOfPlanes(latlong1,latlong2,latlong3,latlong4);

if(poi!=-1)
{
var lengthP1P2 = haversineDistance(latlong1,latlong2);
var lengthP1I1 = haversineDistance(latlong1,poi[0]);
var lengthP2I1 = haversineDistance(latlong2,poi[0]);
var lengthP3P4 = haversineDistance(latlong3,latlong4);
var lengthP3I1 = haversineDistance(latlong3,poi[0]);
var lengthP4I1 = haversineDistance(latlong4,poi[0]);
var max = Math.max(lengthP1P2,lengthP3P4);
if((Math.abs(lengthP1P2-lengthP1I1-lengthP2I1) < max*0.01) &&
(Math.abs(lengthP3P4-lengthP3I1-lengthP4I1) < max*0.01))
{
return poi[0];
}
else { var lengthP1I2 = haversineDistance(latlong1,poi[1]); var lengthP2I2 = haversineDistance(latlong2,poi[1]); var lengthP3I2 = haversineDistance(latlong3,poi[1]); var lengthP4I2 = haversineDistance(latlong4,poi[1]); if((Math.abs(lengthP1P2-lengthP1I2-lengthP2I2) < max*0.01) &&
(Math.abs(lengthP3P4-lengthP3I2-lengthP4I2) < max*0.01))
{
return poi[1];
}
}
}
return -1;
}

Listing 1 Point of Intersection between two Polylines

Information on the haversineDistance method can be found here: http://rbrundritt.spaces.live.com/blog/cns!E7DBA9A4BFD458C5!317.entry

Information on the intersectionOfPlanes method can be found here: http://rbrundritt.spaces.live.com/blog/cns!E7DBA9A4BFD458C5!438.entry

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s