Алгоритм пересечения окружности - PullRequest
Новая
       6

Алгоритм пересечения окружности

1 голос
/ 19 января 2012

У меня есть массив точек, из которых (точек) я знаю координаты (в моей координатной плоскости х / у). Тогда у меня есть точка неизвестных координат, но я знаю расстояние до этой точки от "известных" точек. Я ищу "неизвестные" координаты точки. Должна быть своего рода триангуляция.

Я думал об описании ситуации с системой уравнений.

Предположим, эти данные: 

coord[n] basePoints;
double[n] dist;
coord result;

Давайте думать как: 

struct {
    double x,y;
};

Теперь уравнение окружности: 

x^2 + y^2 + ax + bx + c = 0
where:
a = basePoint[i].x
b = basePoint[i].y
c = a^2 + b^2 + r^2
r = dist[i]

В этом случае нам нужно 3 точки, чтобы точно определить положение точки результата, поэтому нам нужна система из трех уравнений. Вопрос в следующем: есть ли какой-нибудь быстрый способ узнать координаты результата, а нет, есть ли алгоритм, которому нужно следовать?

редактирование:

Я нашел алгоритм, который искал здесь Трилатерация с использованием 3 точек широты и долготы и 3 расстояний .

Также большое спасибо @hardmath за название метода и статью в Википедии.

Ответы [ 2 ]

3 голосов
/ 19 января 2012

Решение проблемы: у вас есть n окружности с центром в basePoint[n] с радиусом dist[n], которые, как известно, имеют одну общую точку пересечения.Вы хотите найти эту точку.

Возьмите первые два круга и найдите их точки пересечения.Есть либо 1, либо 2 (или 0, но тогда проблема не имеет решения).Если 1, это должен быть ответ.Если 2, устраните неоднозначность со следующим кругом.Вы можете проверить, что точка находится на всех других кругах.

0 голосов
/ 19 января 2012

Прежде всего, вы говорите, что у вас есть координаты n точек и расстояние до другой точки (таким образом, n расстояний).

, если у вас есть координаты только из 2 точек, и у вас есть расстояние между этими 2 координатами и третьей точкой (неизвестно), скажем, X (x, y).

Допустим, ваша первая точка A (x1, y1), а вторая точка B (x2, y2)

Теперь вы хотите найти неизвестную точку X (x, y)

Вы можете получить расстояние между A и x, как это 

d1 = sqrt((x1-x)^2 +(y1-y)^2)

здесь вы уже знаете x1, y1 и d

и аналогично расстояние между B и X будет 

d2 = sqrt((x2-x)^2-(y2-y)^2)

Итак, по этим 2 уравнениям вы получите 2 линейных уравнения с 2 неизвестными переменными этого типа 

mx+ny - d1 = 0

 and 

 px+ qy - d2 = 0

Вы можете решить эти два уравнения, чтобы получить координаты x и y точки X (x, y).

вы не упомянули, какой язык программирования вы используете, но вы можете реализовать это, используя любой язык программирования по вашему выбору. Вам не нужны n точек и n расстояний для вычисления неизвестной точки, вы можете рассчитать ее, используя всего 2 точки.

...