Nearest points on two geometries

3711
8
10-08-2012 08:28 AM
Highlighted
New Contributor
Hi,

I have two geometries - a polyline and a polygon - and I want to find the two points (one on polyline and one on the polygon) that are the nearest.

According to documentation IProximityOperator has some methods that do return distance between two geometries, but there is no way to get the actual point, unless I am missing something. The only way seems to be query both point collections against the other geometry and then pick the resulting pair with smallest distance using QueryNearestPoint method. Isn't there a better way of doing it?

Cheers
Reply
0 Kudos
8 Replies
Highlighted
MVP Frequent Contributor
Szymon,

If I have understood you correctly you have a polyline and want to find a point along it's length that is the closest point to a polygon and get the corresponding location on the polygon?

The IProximityOperator Interface has a method called ReturnNearestPoint that will return the actual point on the geometry from a point.


The IPolyline has a useful method QueryPointAndDistance, it may help?

One problem I can think of when iterating through the point collection of a polyline is that the nearest location along the polyline to your polygon may not be a vertex but actually the edge of a segment within the polyline, totally depends on the shape of your polygon.

Duncan
Reply
0 Kudos
Highlighted
New Contributor
Hornbydd,

Thanks for your answer.

I know that the nearest point might be on the edge (polyline or polygon), therefore i think it is necessary to iterate over points of both features. This would then get <Geometry,Point> distances from which I'd have to pick the smallest value. The problem is that this might be slow if geometries have lots of points.

I do know the method QueryPointAndDistance. The problem is that it expects a point as the input. The point would then be the nearest one on the other geometry. The question is how to get the nearest point on the other geometry? Manually iterating or using some existing tool which i do not know?

Cheers
Reply
0 Kudos
Highlighted
New Contributor
Szymon, Did you find a solution? I am in the same problem than you.

Thanks in advance

Oscar
Reply
0 Kudos
Highlighted
Occasional Contributor II
One way I think that might work:
1. Call IProximityOperator::ReturnDistance to find the distance between the polyline and polygon.
2. Call ITopologicalOperator::Buffer with the distance as the input to create a polygon.
3. Find the touch point on one geometry to the boundary of the buffer polygon.  This will be the nearest point of the geometry.
4. Using the same steps or call ReturnNearestPoint to find the nearest point on the other geometry.
Reply
0 Kudos
Highlighted
Occasional Contributor
One way I think that might work:
1. Call IProximityOperator::ReturnDistance to find the distance between the polyline and polygon.
2. Call ITopologicalOperator::Buffer with the distance as the input to create a polygon.
3. Find the touch point on one geometry to the boundary of the buffer polygon.  This will be the nearest point of the geometry.
4. Using the same steps or call ReturnNearestPoint to find the nearest point on the other geometry.


Thanks Weifeng! I had the same task, and you got me on the right track. I Just tried a slightly modified implementation that should work for other high-level geometries as well:
1. Call IProximityOperator::ReturnDistance to find the distance between the polyline and polygon.
2. Call ITopologicalOperator::Buffer on the first geometry with the distance as the input to create a polygon.
3. Call ITopologicalOperator::Intersect to find the touch point(s) of the buffer with the second geometry.
4. Call IHitTest::HitTest on the first geometry with all touch points as query points to find the closest point on the first geometry.
5. Call IHitTest::HitTest on the second geometry with the result of 4. that has the shortest distance (if there is more than 1 point, actually the distance should be always the same).
Reply
0 Kudos
Highlighted
Occasional Contributor

While I'll admit that the math shown in the link below is way beyond my understanding, it might prove useful for someone:

Distance between Lines, Segments and their CPA (2D & 3D)

Reply
0 Kudos
Highlighted
Occasional Contributor

I don't think that this code is ideal (see the comments for its weakness) but it seems to get the job done.

        private void ClosestPointsOnTwoGeometries(IGeometry geometry1, IGeometry geometry2, out IPoint pointOnGeometry1ClosestToGeometry2, out IPoint pointOnGeoemtry2ClosestToGeometry1)

        {

            IProximityOperator proxOp1 = (IProximityOperator)geometry1;

            IProximityOperator proxOp2 = (IProximityOperator)geometry2;

            double distanceBetween = proxOp1.ReturnDistance(geometry2);

            //Make the distance slightly greater than half the distance so that the two buffers will intersect

            double distanceToBuffer = (distanceBetween / 2.0) + (distanceBetween / 1000000.0);

            ITopologicalOperator buf1 = (ITopologicalOperator)((ITopologicalOperator)geometry1).Buffer(distanceToBuffer);

            var buf2 = ((ITopologicalOperator)geometry2).Buffer(distanceToBuffer);

            //Note, you would think that two polygons being buffered would result in a polygon, but it actually

            //results in an error. Thus until I can figure out why that is, I'm returning 1 dimension

            //(esriGeometryDimension.esriGeometry1Dimension) instead of 2.  Hoping to resolve this, but this is probably

            //close enough.

            IPolyline intersectionLine = (IPolyline)buf1.Intersect(buf2, esriGeometryDimension.esriGeometry1Dimension);

            //Take the average of the intersection line (which under most circumstances is very short)

            IPoint middleOfIntersectionPoint = new PointClass();

            IPoint fromPoint = intersectionLine.FromPoint;

            IPoint toPoint = intersectionLine.ToPoint;

            middleOfIntersectionPoint.PutCoords( ((fromPoint.X + toPoint.X) / 2.0), ((fromPoint.Y + toPoint.Y) / 2.0));

            pointOnGeometry1ClosestToGeometry2 = proxOp1.ReturnNearestPoint(middleOfIntersectionPoint, esriSegmentExtension.esriNoExtension);

            pointOnGeoemtry2ClosestToGeometry1 = proxOp2.ReturnNearestPoint(middleOfIntersectionPoint, esriSegmentExtension.esriNoExtension);

        }

Reply
0 Kudos
Highlighted
MVP Frequent Contributor

1) you can get Distance IProximityOperator:: ReturnDistance

2) buffer on polyline A with Distance from step1

3) test with IRelationalOperator:disjoint on every ISegment of polyline B with buffer from step2 -> create list of Segments that intersect (IRelationalOperator:disjoint  = false)

4) buffer on polyline B with Distance from step1

5) test with IRelationalOperator:disjoint on every ISegment of polyline A with buffer from step4 -> create list of Segments that intersect (IRelationalOperator:disjoint  = false)

6) Find distance absolute min of two loops (if frompoint and topoint return same distance you have paraller line)

    0..n-1 (listSegmentsA)

      MinDistance (Polyline (listSegmentsB).ReturnDistance(listSegmentA).FromPoint, Polyline (listSegmentsB).ReturnDistance(listSegmentA).ToPoint

0..n-1 (listSegmentsB)

      MinDistance (Polyline (listSegmentsA).ReturnDistance(listSegmentB).FromPoint, Polyline (listSegmentsA).ReturnDistance(listSegmentB).ToPoint

7) using ReturnNearestPoint using Point from dist min of step6

Reply
0 Kudos