0

I am solving an algorithmic problem which sounds like this:

Given a three-dimensional space and segments in it. Find the point with minimal distance to all of the segments. Example input: in the first line N - the number of segments, in the N next lines given the begin and the end of each segment: x1 y1 z1 x2 y2 z2

I know what kind of a given problem it is (a geometrical median) and I already know how to find the minimal distance between point and segment (Cartesian distance and a nice code provided here), but what I need - is a point (x, y, z) on a segment to which I found the distance. I need to know it to approximate my result.

Here is the code I have

# finds distance between point and segment
def lineseg_dist(p, a, b):
    d = np.divide(b - a, np.linalg.norm(b - a))
    s = np.dot(a - p, d)
    t = np.dot(p - b, d)
    h = np.maximum.reduce([s, t, 0])
    c = np.cross(p - a, d)
    return np.hypot(h, np.linalg.norm(c))

#segment 
seg = [[1, 1, 1], [2, 2, 2]]
lineseg_dist([0, 0, 0], np.array(seg[0]), np.array(seg[1])) #1.73205

For example distance from [0, 0, 0] point to segment is known and we can say that the closest point of the segment to us is [1, 1, 1]. But how do we find the nearest point in other cases?

Andrii Syd
  • 308
  • 5
  • 15
  • Does this answer your question? [Find the shortest distance between a point and line segments (not line)](https://stackoverflow.com/questions/27161533/find-the-shortest-distance-between-a-point-and-line-segments-not-line) – Daniel F Nov 03 '20 at 12:53
  • Unfortunately, this question does not contain the answer. I need the coordinates of a point to which I found the nearest distance – Andrii Syd Nov 03 '20 at 13:05
  • Please try to formulate your question programatically, with your input data structure, expected output, and some pseudo-code to show what you think should work, but doesn't – Daniel F Nov 03 '20 at 13:08
  • Solve for 2 line segments, then generalize. – stark Nov 03 '20 at 13:46
  • 1
    What is `minimal distance to all of the segments`?? Minumum sum of distances? Something else? – MBo Nov 03 '20 at 14:09
  • @Mbo It means the point in the middle where the distance from a point to each segment would be minimal – Andrii Syd Nov 03 '20 at 14:52
  • 1
    @Andrii Syd Sorry, it is not mathematical definition. Minimal distance from a point to a segment is zero, when point lies on the segment. But what for two segments? For three? It is necessary to define some measure of proximity. – MBo Nov 03 '20 at 15:04

1 Answers1

4

From your last paragraph I understand you need to find a point in a segment that is closest to another point.

This function returns both the closest point and the distance:

def closest_point_and_distance(p, a, b):
    s = b - a
    w = p - a
    ps = np.dot(w, s)
    if ps <= 0:
        return a, np.linalg.norm(w)
    l2 = np.dot(s, s)
    if ps >= l2:
        closest = b
    else:
        closest = a + ps / l2 * s
    return closest, np.linalg.norm(p - closest)

It is also faster than the code you have.

aerobiomat
  • 2,883
  • 1
  • 16
  • 19
  • 2
    By the way, I forgot to mention that the function is based on the dist_Point_to_Segment() function in this page: http://geomalgorithms.com/a02-_lines.html – aerobiomat Nov 04 '20 at 10:20