Point to Segment Distance

Problem #77

Tags: geometry mathematics implementation c-1 c-0

Who solved this?

No translations... yet

Very common problem in computational geometry is to find distance between the point and the line segment. It is heavily exploited in programming 3D video games when recalculating visibility of walls for player while redrawing each frame (i.e it is could be solved for 1000 wall fragments in each frame and about 50 frames are completely recalculated during each second).

The definition of the distance between point and segment is like following:

For example, see the picture above - line segment is drawn with blue and perpendiculars from 2nd and 3rd points fall directly onto this segment, so they represent the distance from these points. On other hand perpendiculars from 1st and 4th points fall out of segment (and they are not shown), so that distances are defined simply by the nearest end of a segment (distances from all points are represented with grey lines). The line on which the segment lays is shown with light-green.

Input data will contain the number of test-cases in first line.
The following lines contain six values each: x1 y1 x2 y2 xp yp - denoting the segment between points (x1,y1) and (x2,y2) and the point (xp,yp) to which a distance should be calculated.
Answer should contain distances from points to segments for each test-case, separated with spaces.

Example:

input data:
3
1 1 5 5 2 3
2 3 7 8 2 0
12 8 18 3 5 7

answer:
0.707106781 3 7.07106781187

Note that in the second test-case the shortest distance from point is to the end of a segment, not to a line to which the segment belongs.

Please, provide answers with accuracy of 1e-7 or better.

You need to login to get test data and submit solution.