10
\$\begingroup\$

The Challenge

Given two vertexes and a point calculate the distance to the line segment defined by those points.

This can be calculated with the following psudocode

def dist(point, v1, v2):
    direction       := normalize(v2-v1)
    distance        := length(v2-v1)
    difference      := point - v1
    pointProgress   := dot(difference, direction)
    if (pointProgress <= 0):
        return magnitude(point - v1)
    else if (pointProgress >= distance):
        return magnitude(point - v2)
    else
        normal := normalize(difference - (direction * pointProgress))
        return dot(difference, normal)

Answers may support either 2 dimensions, or 3, and may optionally support any number of higher or lower dimensions.

As it does not substantially change the difficulty of the challenge, answers need only be accurate to the whole number, and I/O can be assumed to fit within the [0,127] range. This is to allow more languages to focus only on the challenge spec, rather than implementing floating points.

Test Cases

1: point=[005,005], v1=[000,000] v2=[010,000] :: distance=005.00 # Horizontal
2: point=[005,005], v1=[010,000] v2=[010,010] :: distance=005.00 # Vertical
3: point=[000,010], v1=[000,000] v2=[010,010] :: distance=007.07 # Diagonal
4: point=[010,000], v1=[000,000] v2=[010,010] :: distance=007.07 # Diagonal, Clockwise
5: point=[000,000], v1=[002,002] v2=[004,008] :: distance=002.83 # Not near the normal
6: point=[000,002], v1=[002,002] v2=[002,002] :: distance=002.00 # Zero length segment

Rules

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Can you take input as complex numbers? \$\endgroup\$ Aug 28, 2023 at 3:40
  • 1
    \$\begingroup\$ @CommandMaster Per Standard IO, Go for it. \$\endgroup\$
    – ATaco
    Aug 28, 2023 at 4:04
  • 2
    \$\begingroup\$ @Neil The difference is this is the difference to the line segment, rather than the infinitely extended line. As such, in this test case, it's the distance to the [2,2] (The closest point on the line), or √8 \$\endgroup\$
    – ATaco
    Aug 28, 2023 at 9:37
  • \$\begingroup\$ Thanks for the clarification, I didn't understand that at all from reading the question. \$\endgroup\$
    – Neil
    Aug 28, 2023 at 9:47
  • 1
    \$\begingroup\$ :( I found a nice formula for calculating the distance from a point to a full line but I guess it will have to wait till that challenge gets posted \$\endgroup\$
    – mousetail
    Aug 28, 2023 at 9:49

6 Answers 6

9
\$\begingroup\$

MATL, 9 bytes

9W&ZS-|X<

Supports two dimensions. Inputs are complex numbers: first the segment endpoints, then the other point.

Try at MATL it online! Or verify all test cases.

Explanation

9W      % Push 9. Compute 2 raised to that number, that is, 512
&ZS     % Implicit inputs: segment endpoints. Generate vector of 512 evenly
        % spaced numbers in the range defined by the endpoints, including them
-       % Implicit input: point. Subtract, element-wise
|       % Absolute value of each entry
X<      % Minimum. Implicit display
\$\endgroup\$
6
  • 2
    \$\begingroup\$ Nice (ab)use of the loose accuracy requirement! \$\endgroup\$
    – Bubbler
    Aug 28, 2023 at 10:06
  • \$\begingroup\$ @Bubbler I know... I almost feel bad about it :-) \$\endgroup\$
    – Luis Mendo
    Aug 28, 2023 at 10:08
  • \$\begingroup\$ I love this (and copied the approach), but don't you need more than 99 points to satisfy the "accurate to the whole number" requirement with endpoints at 0,0 and 127,127? If rounding to a whole number, the point (0.65,0.65) could be a problem, and if truncating then the point (1,0.3) could be... \$\endgroup\$ Aug 28, 2023 at 15:31
  • \$\begingroup\$ @DominicvanEssen My argument was based on the closest the point can be to the segment, not the farthest. But I'm not sure. Can you ellaborate, i.e. give an input that could result in a wrong integer output? On the other hand, I can increase 99 to 512 with no extra bytes. do you think that number would be enough? \$\endgroup\$
    – Luis Mendo
    Aug 28, 2023 at 15:59
  • 1
    \$\begingroup\$ Using 99 points and with endpoints at 0,0 and 127,127, the point (0.65,0.65) gives output 0.913, but the correct answer is 0. The point (1,0.3) gives output 1.038, but the correct answer is 0.495. But all of this is moot now that you've changed it to 512... \$\endgroup\$ Aug 28, 2023 at 16:07
6
\$\begingroup\$

R, 34 33 bytes

Edit: -1 byte thanks to Giuseppe

\(p,a,b)min(abs(p-seq(a,b,,1e4)))

Attempt This Online!

Input point p and segment endpoints a and b as complex numbers.

Approach copied from Luis Mendo's answer: upvote that!

Accuracy can be improved by changing 1e4 to a higher value (for instance, 1e9 without increasing code-length), but as-is it's easily within the ±1 accuracy in the x,y-range of 0–127.

\$\endgroup\$
1
  • \$\begingroup\$ @Giuseppe - Ah, yes, thanks! \$\endgroup\$ Aug 28, 2023 at 15:51
5
\$\begingroup\$

Charcoal, 65 61 bytes

UMθ₂ΣXE§θ⊕κ⁻λ§ιμ²≔§θ⁰η≔⎇η⊗∕₂Π⁻⊘Σθ⁺θ⟦⁰⟧η⌈θζI⎇›X⌈θ²⁺Xη²Xζ²⌊Φθκζ

Try it online! Link is to verbose version of code. Takes input as a list of the two vertices and the point. Explanation:

UMθ₂ΣXE§θ⊕κ⁻λ§ιμ²

Calculate the lengths of the sides of a triangle with the given points.

≔§θ⁰η

Get the base of the triangle separately.

≔⎇η⊗∕₂Π⁻⊘Σθ⁺θ⟦⁰⟧η⌈θζ

Unless the base is zero, divide the triangle's area by it and double the result, giving the altitude.

I⎇›X⌈θ²⁺Xη²Xζ²⌊Φθκζ

Determine whether the base of the triangle contains the foot, and if so, output the altitude, otherwise output the shorter of the other two sides.

58 54 bytes taking complex numbers as input:

UMθ↔⁻ι§θ⊕κ≔§θ⁰η≔⎇η⊗∕₂Π⁻⊘Σθ⁺θ⟦⁰⟧η⌈θζI⎇›X⌈θ²⁺Xη²Xζ²⌊Φθκζ

Attempt This Online! Link is to verbose version of code.

\$\endgroup\$
2
  • \$\begingroup\$ Nice approach… are you using Heron’s formula for the area? \$\endgroup\$
    – Jonah
    Aug 28, 2023 at 12:52
  • 1
    \$\begingroup\$ @Jonah Yeah, that's the easiest for Charcoal to calculate, although I see now that my algorithm is still faulty, sigh... \$\endgroup\$
    – Neil
    Aug 28, 2023 at 13:20
4
\$\begingroup\$

J, 32 bytes

[:(1#.&.:*:[-]*1<.0>.%. ::0)/-"1

Attempt This Online!

Takes input as v1 f point ,: v2 (a vector v1 on the left side, and a two-row matrix containing point and v2 on the right side). Supports arbitrary dimensions.

The main approach is to translate v1 to origin and compute the vector component of point onto v2. When the value is clamped to the range [0, 1], that times v2 becomes the point on the line segment that is closest to point. Then we can compute the norm of the difference.

[:(1#.&.:*:[-]*1<.0>.%. ::0)/-"1    left: v1, right: point ,: v2
                             -"1    (point - v1) ,: (v2 - v1)
[:(                        )/       run dyadically with the two rows as two args:
                     %. ::0     vector component
               1<.0>.           clamp to [0,1]
           [-]*                 get the distance vector
   1#.&.:*:                     norm of the vector

::0 attached to %. handles the case of zero-length line segment (if it would throw an error, return 0 instead). &.:*: is a fancy way of saying "square something, do something on it, and take its square root".

J, 23 bytes

[:([|@-]*1<.0>.9 o.%)/-

Attempt This Online!

Same algorithm, but takes a complex number for each vector instead, therefore supporting only two dimensions. %. is replaced with % (division) followed by 9 o. (extract real part). Norm is simply |.

\$\endgroup\$
3
\$\begingroup\$

JavaScript (Node.js), 146 144 140 156 bytes

-2 bytes because of oversight noted by @noodleman

-4 bytes thanks to @TheThonnu's suggestion

+16 bytes because I noticed my own error with the solution

Algorithm somewhat yoinked from @Neil's Charcoal answer, though with a slightly different method for handling the "segment" of "line segment."

(a,b,c,d,e,f,S=Math.sqrt)=>((x,y,z)=>Math.min(S((x+y+z)*(x+y-z)*(x-y+z)*(y+z-x))/2/x,y,z))(S((f-d)**2+(e-c)**2),S((f-b)**2+(e-a)**2),S((d-b)**2+(c-a)**2))

(a,b) is the point, (c,d) is vertex 1, (e,f) is vertex 2. Returns a float.

Versions

Version 1 (original + oversight fix) (INCORRECT—SEE COMMENTS)

(S=>(a,b,c,d,e,f)=>((x,y,z)=>S((x+y+z)*(x+y-z)*(x-y+z)*(y+z-x))/2/x)(S((f-d)**2+(e-c)**2),S((f-b)**2+(e-a)**2),S((d-b)**2+(c-a)**2)))(Math.sqrt)

Try this old version online!

Version 2 (uses default arg instead of separate call) (INCORRECT—SEE COMMENTS)

(a,b,c,d,e,f,S=Math.sqrt)=>((x,y,z)=>S((x+y+z)*(x+y-z)*(x-y+z)*(y+z-x))/2/x)(S((f-d)**2+(e-c)**2),S((f-b)**2+(e-a)**2),S((d-b)**2+(c-a)**2))

Try this old version online!

Version 3 (current, fixes issue with solution)

(a,b,c,d,e,f,S=Math.sqrt)=>((x,y,z)=>Math.min(S((x+y+z)*(x+y-z)*(x-y+z)*(y+z-x))/2/x,y,z))(S((f-d)**2+(e-c)**2),S((f-b)**2+(e-a)**2),S((d-b)**2+(c-a)**2))

Explanation

(a,b,c,d,e,f,S=Math.sqrt)=>(...)

The function declaration. Uses S as a default argument in this version instead of a different call.

((x,y,z)=>...)(S((f-d)**2+(e-c)**2),S((f-b)**2+(e-a)**2),S((d-b)**2+(c-a)**2))

This is slightly more efficient than declaring x,y,z as variables outright—it uses another one of those define-exec chains. (Is there a canon term for this?)

x,y,z are the side lengths for a triangle with vertices at the three points, with x being the length of the segment between the two vertices. THIS IS IMPORTANT. To find these, I just used the bog-standard distance formula. Nothing special here.

Math.min(S((x+y+z)*(x+y-z)*(x-y+z)*(y+z-x))/2/x,y,z)

The final part. This calculates the area with [a slightly modified] Heron's formula, and then works backwards to find the height with one tiny optimization. It also accounts for the cases where the endpoints are closer with a Math.min() call.

Links

Try this online! This is a link to the golfed version. The verbose version no longer exists as of v2.

\$\endgroup\$
7
  • \$\begingroup\$ Nice answer. You don't need the F= unless it's a recursive function; it can go in the "header" section on TIO. \$\endgroup\$
    – noodle man
    Aug 28, 2023 at 19:04
  • \$\begingroup\$ It doesn't count towards the byte count, either? \$\endgroup\$
    – Someone
    Aug 28, 2023 at 19:24
  • \$\begingroup\$ @Someone Correct. \$\endgroup\$
    – Jonah
    Aug 28, 2023 at 19:47
  • \$\begingroup\$ 140 bytes? \$\endgroup\$
    – The Thonnu
    Aug 28, 2023 at 19:49
  • \$\begingroup\$ I hadn’t thought of default arguments! Thanks! \$\endgroup\$
    – Someone
    Aug 28, 2023 at 19:55
2
\$\begingroup\$

Mathematica (Wolfram Language) 33 bytes

RegionDistance[Line[{#2, #3}],#]&

Try it online!

This uses Mathematica built-ins, but this program has the benefit of working in any dimension. You could use Mathematica graphics options to see the computation graphically. The TIO link above has the last of the test cases, but in 3D instead of 2D!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.