Geometry/math question

[togFox]

Not sure how to explain this:

Given three known points on a plane, I need to determine the x/y of a fourth point.

The only information I have on the fourth point is the distance to three other points.

Arbitrary example:

Known points x/y

Point A: 12, 5
Point B: 21,11
Point C: 17 15
Point D: ?, ?

Distance between Point A and Point D = 9 units
Distance between Point B and Point D = 11 units
Distance between Point C and Point D = 7 units

How to determine D?

I'm sure circle's and circumference and intersects are involved.

Also note Arbitrary example is random and may be unsolvable.

[Andlac028]

You can solve this oriblem by first finding intersections of pairs of circles, and then checking, if some point is in all intersections of pairs of circles.

To find intersections of pair of circles, just use some formula. After quick search, I found for example this.

Maybe it is not the most efficient method, but it is simple and intuitive.

[Bigfoot71]

It is roughly an equation with two unknowns, here is how I did it personally:

Code: Select all

local ax, ay = 120, 50
local bx, by = 210, 110
local cx, cy = 170, 150

local distAD = 90
local distBD = 110
local distCD = 70


-- Determination of the position of D --

local a = 2 * (bx - ax)
local b = 2 * (by - ay)
local c = distAD^2 - distBD^2 - ax^2 + bx^2 - ay^2 + by^2
local d = 2 * (cx - bx)
local e = 2 * (cy - by)
local f = distBD^2 - distCD^2 - bx^2 + cx^2 - by^2 + cy^2

local dx = (c*e - b*f) / (a*e - b*d)
local dy = (c*d - a*f) / (b*d - a*e)



-- Verification with given distances --

print("distAD: ", math.sqrt((ax-dx)^2+(ay-dy)^2), distAD)
print("distBD: ", math.sqrt((bx-dx)^2+(by-dy)^2), distBD)
print("distCD: ", math.sqrt((cx-dx)^2+(cy-dy)^2), distCD)



-- Shows points --

function love.draw()

    love.graphics.setColor(1,0,0)

    -- POINT A

    love.graphics.circle("fill", ax,ay,4)

    -- POINT B

    love.graphics.circle("fill", bx,by,4)

    -- POINT C

    love.graphics.circle("fill", cx,cy,4)

    -- POINT D --

    love.graphics.setColor(0,1,0)
    love.graphics.circle("fill", dx,dy,4)

end

Return:

Code: Select all

distAD: 	86.857482246622	90
distBD: 	107.44404228352	110
distCD: 	65.910714016935	70

I don't know if it will be the most precise method (because of all evidence several answers would be possible in this case) but it at least has the advantage of giving a not too imprecise answer

Here is an explanation of the calculations performed:

Code: Select all

-- Calculation of coefficients for trilateration --

local a = 2 * (bx - ax) -- Coefficient a
local b = 2 * (by - ay) -- Coefficient b
local c = distAD^2 - distBD^2 - ax^2 + bx^2 - ay^2 + by^2 -- Coefficient c
local d = 2 * (cx - bx) -- Coefficient d
local e = 2 * (cy - by) -- Coefficient e
local f = distBD^2 - distCD^2 - bx^2 + cx^2 - by^2 + cy^2 -- Coefficient f

-- Solving linear equations to determine the position of D --

local dx = (c*e - b*f) / (a*e - b*d) -- Approximate x coordinate of D
local dy = (c*d - a*f) / (b*d - a*e) -- Approximate y coordinate of D

Surely by using another iterative method the result could be more precise but obviously much less efficient.

Also obviously by drawing circles with the given distances in radius, the point sought should be the intersection of the circles if there are any, here is another possible method, more precise, very surely not optimized and which may fail but which represents well what we would do by hand (check only two dists):

Code: Select all

local ax, ay = 120, 50
local bx, by = 210, 110
local cx, cy = 170, 150

local distAD = 90
local distBD = 110
local distCD = 70


-- Check intersection (function & perform) --

local function getIntersection(x1, y1, r1, x2, y2, r2)
    local d = math.sqrt((x2-x1)^2 + (y2-y1)^2)
    if d > r1 + r2 or d < math.abs(r1-r2) then
        return nil
    end
    local a = (r1^2 - r2^2 + d^2) / (2*d)
    local h = math.sqrt(r1^2 - a^2)
    local x3 = x1 + a*(x2-x1)/d
    local y3 = y1 + a*(y2-y1)/d
    local x4_1 = x3 + h*(y2-y1)/d
    local x4_2 = x3 - h*(y2-y1)/d
    local y4_1 = y3 - h*(x2-x1)/d
    local y4_2 = y3 + h*(x2-x1)/d
    return x4_1, y4_1, x4_2, y4_2
end

local dx1, dy1, dx2, dy2 = getIntersection(ax, ay, distAD, bx, by, distBD)

if dx1 and dy1 then
    dx, dy = dx1, dy1
elseif dx2 and dy2 then
    dx, dy = dx2, dy2
else
    dx, dy = nil, nil
end


-- Check distances with original --

if dx and dy then
    print("distAD: ", math.sqrt((ax-dx)^2+(ay-dy)^2), distAD)
    print("distBD: ", math.sqrt((bx-dx)^2+(by-dy)^2), distBD)
    print("distCD: ", math.sqrt((cx-dx)^2+(cy-dy)^2), distCD)
else
    print("The circles do not intersect.")
end


-- Show the points --

function love.draw()
    love.graphics.setColor(1, 0, 0)
    love.graphics.circle("fill", ax, ay, 4)
    love.graphics.circle("fill", bx, by, 4)
    love.graphics.circle("fill", cx, cy, 4)
    if dx and dy then
        love.graphics.setColor(0, 1, 0)
        love.graphics.circle("fill", dx, dy, 4)
    end
end

Return:

Code: Select all

distAD: 	90	90
distBD: 	110	110
distCD: 	151.19637965115	70

Because I like the problem I made a more complete version of my second example which verifies all possible intersections and returns the best (code to be optimized obviously):

Code: Select all

local ax, ay = 120, 50
local bx, by = 210, 110
local cx, cy = 170, 150

local distAD = 90
local distBD = 110
local distCD = 70


-- Check intersection (function & perform) --

local function getIntersection(x1, y1, r1, x2, y2, r2)
    local d = math.sqrt((x2-x1)^2 + (y2-y1)^2)
    if d > r1 + r2 or d < math.abs(r1-r2) then
        return nil
    end
    local a = (r1^2 - r2^2 + d^2) / (2*d)
    local h = math.sqrt(r1^2 - a^2)
    local x3 = x1 + a*(x2-x1)/d
    local y3 = y1 + a*(y2-y1)/d
    local x4_1 = x3 + h*(y2-y1)/d
    local x4_2 = x3 - h*(y2-y1)/d
    local y4_1 = y3 - h*(x2-x1)/d
    local y4_2 = y3 + h*(x2-x1)/d
    return x4_1, y4_1, x4_2, y4_2
end


-- Check intersection between all circles --

local all_circles = {
    {ax, ay, distAD},
    {bx, by, distBD},
    {cx, cy, distCD}
}

local intersections = {}
for i = 1, #all_circles do
    for j = i + 1, #all_circles do
        local x1, y1, r1 = unpack(all_circles[i])
        local x2, y2, r2 = unpack(all_circles[j])
        local dx1, dy1, dx2, dy2 = getIntersection(x1, y1, r1, x2, y2, r2)
        if dx1 and dy1 then
            table.insert(intersections, {dx1, dy1})
        end
        if dx2 and dy2 then
            table.insert(intersections, {dx2, dy2})
        end
    end
end


-- Find the intersection closest to all the points --

local min_distance = math.huge
local best_intersection = nil
for _, point in ipairs(intersections) do
    local distance = 0
    for _, circle in ipairs(all_circles) do
        local x, y, r = unpack(circle)
        distance = distance + math.abs(math.sqrt((x-point[1])^2 + (y-point[2])^2) - r)
    end
    if distance < min_distance then
        min_distance = distance
        best_intersection = point
    end
end


-- Check distances with original --

if best_intersection then
    local dx, dy = best_intersection[1], best_intersection[2]
    print("distAD: ", math.sqrt((ax-dx)^2+(ay-dy)^2), distAD)
    print("distBD: ", math.sqrt((bx-dx)^2+(by-dy)^2), distBD)
    print("distCD: ", math.sqrt((cx-dx)^2+(cy-dy)^2), distCD)
else
    print("The circles do not intersect.")
end


-- Show the points --

function love.draw()
    love.graphics.setColor(1, 0, 0)
    for _, circle in ipairs(all_circles) do
        love.graphics.circle("fill", circle[1], circle[2], 4)
    end
    if best_intersection then
        love.graphics.setColor(0, 1, 0)
        love.graphics.circle("fill", best_intersection[1], best_intersection[2], 4)
    end
end

Return:

Code: Select all

distAD: 	90	90
distBD: 	112.49549421694	110
distCD: 	70	70

[pgimeno]

I think you have a point too much. If you trace a circle with the given distance as a radius from point A, and another with the given distance as a radius from point B, they can intersect:

1. In all points, if A = B and the radii are equal. That's a degenerate case that I guess you're not interested in.
2. In two points.
3. In one point, if they are tangent.
4. In no points.

The most common cases are 2 and 4. In cases 2 and 3, unless the third point's distance exactly equals one of the intersections, the problem won't have a solution.

This program illustrates the problem using your points:

Code: Select all

local s = 20
function love.draw()
  love.graphics.setColor(1, 1, 1)
  love.graphics.circle("line",12*s,5*s,9*s)
  love.graphics.circle("line",21*s,11*s,11*s)
  love.graphics.setColor(1, 1, 0)
  love.graphics.circle("line", 17*s, 15*s, 7*s)
end

s is the scale. The white circles are point A (12, 5) with radius 9 and point B (21, 11) with radius 11. There are only two points at the given distances of both points A and B (at the intersections of the circles), and the yellow circle (point C (17, 15) with radius 7) doesn't touch it so the problem doesn't have any solution. In general, if A, B and C are arbitrary, there won't be a solution. There are even many cases where there's no solution with just two points - think if they are apart by 20 units and the given distance to each is 2 units, for example.

[togFox]

I suggested 3 points because orientation matters. For example knowing the distance between two points can determine spacial relativity (that a thing?) But I wouldn't know if the point is "above" or below. If you get my meaning.

I didn't say this in OP but there might be a 5th point introduced so orientation becomes important (I think).

Think of a network of points growing over time with the only knowledge being how far it is from other points.

[Bigfoot71]

I suggested 3 points because orientation matters. For example knowing the distance between two points can determine spacial relativity (that a thing?) But I wouldn't know if the point is "above" or below. If you get my meaning.

I didn't say this in OP but there might be a 5th point introduced so orientation becomes important (I think).

Think of a network of points growing over time with the only knowledge being how far it is from other points.

Not necessarily and in some cases it could still be an approximation if the case is not true or if several solutions would be possible.

I have produced a better case of concrete example. Here is a real case realized quickly on GeoGebra (you can ignore the angles, I used them in another test):


I will first reuse the trilateration technique that I tried to use above, a technique that does not require the orientations of D with respect to ABC (I said this following a slight misunderstanding of the post, but the example still stands):

Code: Select all

-- Coordinates of points A, B and C --

local Ax, Ay = 15, 10
local Bx, By = 140.65, 30.92
local Cx, Cy = 18.76, 68.15

-- Distance of D from points A, B and C --

local distAD = 107.44
local distBD = 72.7
local distCD = 75.13

-- Function that calculates the coordinates of D from given distances --

local function trilaterate(Ax, Ay, distAD, Bx, By, distBD, Cx, Cy, distCD)
  local A = (Ax^2 + Ay^2 - distAD^2)
  local B = (Bx^2 + By^2 - distBD^2)
  local C = (Cx^2 + Cy^2 - distCD^2)
  local x = (A*(Cy-By) + B*(Ay-Cy) + C*(By-Ay)) / (2*(Ax*(Cy-By) + Bx*(Ay-Cy) + Cx*(By-Ay)))
  local y = (A*(Cx-Bx) + B*(Ax-Cx) + C*(Bx-Ax)) / (2*(Ay*(Cx-Bx) + By*(Ax-Cx) + Cy*(Bx-Ax)))
  return x, y
end

local Dx, Dy = trilaterate(Ax, Ay, distAD, Bx, By, distBD, Cx, Cy, distCD)

-- Verification with given distances --

print("distAD: ", math.sqrt((Ax-Dx)^2+(Ay-Dy)^2), distAD)
print("distBD: ", math.sqrt((Bx-Dx)^2+(By-Dy)^2), distBD)
print("distCD: ", math.sqrt((Cx-Dx)^2+(Cy-Dy)^2), distCD)

-- Show the points --

function love.draw()

    love.graphics.setColor(1,0,0)

    -- POINTS ABC

    love.graphics.circle("fill", Ax,Ay,4)
    love.graphics.circle("fill", Bx,By,4)
    love.graphics.circle("fill", Cx,Cy,4)

    -- POINT D --

    love.graphics.setColor(0,1,0)
    love.graphics.circle("fill", Dx,Dy,4)

end

This returns:

Code: Select all

distAD:         107.44156163867 107.44
distBD:         72.702307854403 72.7
distCD:         75.132233211561 75.13

We can therefore see that this solution may suffice if the case is true and precise enough.

Now the same case with the last example I proposed in my previous post, the circle intersection technique gives us:

Code: Select all

distAD:         107.44  107.44
distBD:         72.7    72.7
distCD:         75.132068023763 75.13

Obviously, the more marks there are, the more a method like trilateration will give a potentially exact answer and the less the technique of intersection of circles will give different solutions. Only there are still other possible techniques with a 4th reference point.

Now if in your case several solutions are possible and the orientation matters you can readapt the technique of intersection of the circles by also obtaining the angle closest to that desired.

You can also better detail the exact problem you are facing in your project, maybe other more suitable solutions would be possible and I will be happy to write it if you need it and if I can

Edit: For posterity I still made a possible example with 4 points ABCD where we must find E from its distance with each point:

Code: Select all

local square = function (x) return x*x end

-- Coordinates of points A, B, C and D --

local Ax, Ay = 15, 10
local Bx, By = 140.65, 30.92
local Cx, Cy = 18.76, 68.15
local Dx, Dy = 91.99, 84.94

-- Distance of E from points A, B, C and D --

local distAE = 168.43
local distBE = 61.15
local distCE = 147.21
local distDE = 72.78

-- Calculation of the position of point E --

local K1 = (square(distAE) - square(distBE) + square(Bx) - square(Ax) + square(By) - square(Ay)) / 2
local K2 = (square(distAE) - square(distCE) + square(Cx) - square(Ax) + square(Cy) - square(Ay)) / 2
local K3 = (square(distAE) - square(distDE) + square(Dx) - square(Ax) + square(Dy) - square(Ay)) / 2

local Ex = ((K1 * (Cy - Ay) - K2 * (By - Ay)) / ((Bx - Ax) * (Cy - Ay) - (Cx - Ax) * (By - Ay)))
local Ey = ((K1 - Ex * (Bx - Ax)) / (By - Ay))

-- Verification with given distances --

print("distAE: ", math.sqrt((Ax-Ex)^2+(Ay-Ey)^2), distAE)
print("distBE: ", math.sqrt((Bx-Ex)^2+(By-Ey)^2), distBE)
print("distCE: ", math.sqrt((Cx-Ex)^2+(Cy-Ey)^2), distCE)
print("distDE: ", math.sqrt((Dx-Ex)^2+(Dy-Ey)^2), distDE)

-- Show the points --

function love.draw()

    love.graphics.setColor(1,0,0)

    -- POINTS ABCD

    love.graphics.circle("fill", Ax,Ay,4)
    love.graphics.circle("fill", Bx,By,4)
    love.graphics.circle("fill", Cx,Cy,4)
    love.graphics.circle("fill", Dx,Dy,4)

    -- POINT E --

    love.graphics.setColor(0,1,0)
    love.graphics.circle("fill", Ex,Ey,4)

end

This returns:

Code: Select all

distAE:         168.42317498175 168.43
distBE:         61.131198834428 61.15
distCE:         147.20219112138 147.21
distDE:         72.778800590316 72.78

Otherwise when I speak of trilateration and intersections of circles it is always the same principle, I use the two terms to differentiate the slightly different methods in their application that I have been able to use.

Question: I would really like to know what the exact problem is, how can you determine a distance (which must be theoretical) without having the position of the point sought, surely there is another solution to this problem.

[togFox]

I'm thinking of starting a top down kingdom building project and I'd like a spawn system where events, good and bad, will spawn in a certain proximity from each village. For example, I need to spawn a group of hostile raiders but where?

I'd spawn it further away from secure villages but closer to newly established villages. This can give a level of realism and a "territorial " feel.

The math and code here is very helpful. Thanks. I sense this has been fun to think about

(I've. not seen geogebra tool before)

[Bigfoot71]

I'm thinking of starting a top down kingdom building project and I'd like a spawn system where events, good and bad, will spawn in a certain proximity from each village. For example, I need to spawn a group of hostile raiders but where?

I'd spawn it further away from secure villages but closer to newly established villages. This can give a level of realism and a "territorial " feel.

The math and code here is very helpful. Thanks. I sense this has been fun to think about

(I've. not seen geogebra tool before)

Ah okay, I'm not sure that such a rule is the most optimized then, especially if there is an indeterminate number of villages on the map.
You could simply set up a rule that spawns the horde around the radius of a randomly destitute village while checking that it is not within a certain distance to other surrounding villages if that matters. You could also increase the probability of selecting a village according to its "level of protection".

I made a mini example of what it might look like because it amuses me indeed

I imagined this on a whim and code it in half an hour, I put what I said except the calculation of probability of selection of a village and it iterates all the villages when testing so it's not too optimized, there's probably even better as a general rule, this is just an example, maybe someone who's worked on an strategy game before could elaborate.

Otherwise concerning GeoGebra I learned to use this program when I was in middle school and since then I have never left it, it is super useful in this kind of case (an online version also exists)

[togFox]

I think you're 1/2 way to some sort of gamified mouse clicker with those two examples.