Code Golf Asked by Denker on November 17, 2021
Imagine you are on a two dimensional cartesian plane and want to determine your position on it. You know 3 points on that plane and your distance to each of them. While it is always possible to calculate your position from that, doing that in your head is pretty hard. So you decide to write a program for that.
Given 3 points and your distance to them, output the cordinates of your position.
Hint to get started:
Input format for one point here is [[x,y],d]
with x
and y
being the coordinates and d
being the distance to this point. The 3 of those points are arranged in a list. Output will be x
and then y
in a list.
[[[1, 2], 1.414], [[1, 1], 2.236], [[2, 2], 1.0]] -> [2, 3] [[[24.234, -13.902], 31.46], [[12.3242, 234.12], 229.953], [[23.983, 0.321], 25.572]] -> [-1.234, 4.567] [[[973.23, -123.221], 1398.016], [[-12.123, -98.001], 990.537], [[-176.92, 0], 912.087]] -> [12.345, 892.234]
You can generate additional test cases with this Pyth program. Location goes on the first line of the input and the 3 points are on the following 3 lines.
Happy Coding!
-∘(+/)⍥(×⍨)⌹⍥(2-⌿⊢)¯2×⊢
A tacit infix function that can be called like dists f pts
, where pts
contains three centers' coordinates as a 3-row 2-column matrix, and dists
contains three distances to the respective centers.
Uses 18.0 feature ⍥
. TIO's Dyalog Unicode is not updated yet from 17.1, so TIO link uses Dyalog Extended for demonstration purposes.
Uses the same method as R.T.'s Python answer, i.e. constructing a linear system of equations and solving it.
The distance equations are necessarily quadratic. Then how did we get linear ones?
Let's consider just two circles, and denote the point we want to find as $P$, two circles' centers as $C, D$, and their radii as $r_C, r_D$. Also, let's use $A_x, A_y$ for the $x$- and $y$-coordinates of a point $A$. Then the following equations hold:
$$ (P_x-C_x)^2+(P_y-C_y)^2 =r_C^2 \ (P_x-D_x)^2+(P_y-D_y)^2 =r_D^2 \ $$
Then we expand them and subtract the second from the first:
$$ P_x^2-2P_xC_x+C_x^2+P_y^2-2P_yC_y+C_y^2=r_C^2\ P_x^2-2P_xD_x+D_x^2+P_y^2-2P_yD_y+D_y^2=r_D^2\ -2P_x(C_x-D_x)+(C_x^2-D_x^2)-2P_y(C_y-D_y)+(C_y^2-D_y^2)=r_C^2-r_D^2\ -2P_x(C_x-D_x)-2P_y(C_y-D_y)=(r_C^2-C_x^2-C_y^2)-(r_D^2-D_x^2-D_y^2) $$
We've just got one linear equation on $P_x$ and $P_y$. Since we have three circles given, we can take any two pairs and construct two equations, which then solving the system of equations gives the coordinates we want.
-∘(+/)⍥(×⍨)⌹⍥(2-⌿⊢)¯2×⊢ ⍝ Left: dists, Right: pts
-∘(+/)⍥(×⍨) ⍥(2-⌿⊢) ⍝ Constants part
⍥(×⍨) ⍝ Square each number in both dists and pts
∘(+/) ⍝ Row sums of squared pts
- ⍝ Subtract above from squared dists
⍥(2-⌿⊢) ⍝ Take pairwise difference
⍥(2-⌿⊢)¯2×⊢ ⍝ Coefficients part
¯2×⊢ ⍝ -2 times pts
⍥(2-⌿⊢) ⍝ Take pairwise difference between rows
⌹ ⍝ Solve linear equations
Answered by Bubbler on November 17, 2021
Takes input as a list of tuples of form (x,y,d). Let me know if you see a way to golf this further, I feel like there must be but I can't figure it out!
import numpy as N
def L(P):
Z=[p[2]**2-p[0]**2-p[1]**2 for p in P];return N.linalg.solve([[P[i][0]-P[0][0],P[i][1]-P[0][1]]for i in[1,2]],[(Z[0]-Z[i])*0.5 for i in [1,2]])
Answered by R.T. on November 17, 2021
Input is given as a sequence of space-separated floats on stdin: x1 y1 d1 x2 y2 d2 x3 y3 d3
. Output is similar on stdout: x y
.
#define F"%f "
#define G float
#define T(x)(b.x*b.x-a.x*a.x)
typedef struct{G a;G b;G c;}C;G f(C a,C b,G*c){G x=b.b-a.b;*c=(T(a)+T(b)-T(c))/x/2;return(a.a-b.a)/x;}main(){C a,b,c;G x,y,z,t,m;scanf(F F F F F F F F F,&a.a,&a.b,&a.c,&b.a,&b.b,&b.c,&c.a,&c.b,&c.c);x=f(a,a.b==b.b?c:b,&y);z=f(b.b==c.b?a:b,c,&t);m=t-y;m/=x-z;printf(F F"n",m,x*m+y);}
C
is a structure type whose members are an x-coordinate a
, a y-coordinate b
, and a distance (radius) c
. The function f
takes two C
structures and a pointer to a float, and determines the line at which the C
(circles) intersect. The y-intercept of this line is placed into the pointed-to float, and the slope is returned.
The program calls f
on two pairs of circles, then determines the intersection of the produced lines.
Answered by Fox on November 17, 2021
Online use. Copy+paste each equation into an equation box, click "add all" for each box, then click on the point of intersection, then enter in each value as appropriate. each of A
, B
, and C
are the distances for the points (a,b)
, (c,d)
, and (E,f)
, respectively. To get a square root in the value, type sqrt
then the value in the box.
left(x-aright)^2+left(y-bright)^2=AA
left(x-cright)^2+left(y-dright)^2=BB
left(x-Eright)^2+left(y-fright)^2=CC
Or you can take a look here:
Answered by Conor O'Brien on November 17, 2021
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP