Лучший способ найти точку на окружности, ближайшую к заданной точке

Учитывая точку (pX, pY) и окружность с известным центром (cX,cY) и радиусом (r), какой кратчайший объем кода вы можете придумать, чтобы найти точку на окружности, ближайшую к (pX, пг) ?

У меня есть работающий код, но он включает преобразование окружности в уравнение формы (x - cX) ^ 2 + (y - cY) ^ 2 = r ^ 2 (где r - радиус) и использование уравнения линии от точки (pX, pY) до (cX, cY), чтобы создать квадратное уравнение, которое необходимо решить.

Как только я устраню ошибки, это сработает, но это кажется таким неэлегантным решением.


algorithm geometry language-agnostic
person Matt Mitchell    schedule 19.11.2008    source источник
comment
На самом деле это было для игры, но, тем не менее, решение было найдено.   -  person Matt Mitchell    schedule 03.09.2010

Ответы (8)


arrow_upward
67
arrow_downward

где P — точка, C — центр, а R — радиус на подходящем «математическом» языке:

V = (P - C); Answer = C + V / |V| * R;

где |V| это длина В.

OK, OK

double vX = pX - cX;
double vY = pY - cY;
double magV = sqrt(vX*vX + vY*vY);
double aX = cX + vX / magV * R;
double aY = cY + vY / magV * R;

легко расширяется до> 2 измерений.

person Mike Dunlavey    schedule 19.11.2008
comment
Я реализовал бит математики, который вы опубликовали, до того, как вы написали свой код. Однако я обнаружил, что мне нужно иметь pX - vX, а не pX + pY, чтобы получить ближайшую сторону. В любом случае спасибо за это - мне любопытно посмотреть, есть ли более короткие решения. - person Matt Mitchell; 19.11.2008
comment
В/|В| является единичным вектором от C к P, поэтому я просто умножил его на R и добавил к C. Не могли бы вы умножить на -R, чтобы получить более дальнюю точку? - person Mike Dunlavey; 19.11.2008
comment
Я вижу свою ошибку. Я должен был сказать C + V/|V| * Р - person Mike Dunlavey; 19.11.2008
comment
Хех, я все равно использовал C + :-) - person Matt Mitchell; 19.11.2008
comment
Отношение расстояния к успеху, деленному на время, должно быть рекордным. - person Mike Dunlavey; 19.11.2008
comment
А как насчет того, когда данный понит совпадает с центром? Частный случай, с которым вам нужно иметь дело. - person WW.; 19.11.2008
comment
А еще если радиус равен нулю - это все равно круг? - person WW.; 19.11.2008
comment
@WW ... Я вижу, что ты там сделал - person Matt Mitchell; 19.11.2008
comment
Вы могли бы немного упростить объяснение (ИМО), если бы просто сказали «Найти курс от центра круга до нужной точки», нормализовать и умножить на радиус. Итак, если вектор A = центр и вектор B = ваша точка внутри или снаружи указанного круга A + (B - A).normalized * radius; Теперь все это предполагает, что вы используете структуру или аналогичную для векторов или, по крайней мере, определили основные математические операторы/функции для ваших векторов... что OP не сказал, что они сделали, но я думаю, что это делает ваши действия более понятными, вы могли бы затем предоставьте необходимые операции для нормализации. - person James McGhee; 01.10.2018

arrow_upward
7
arrow_downward

я бы провел линию из центра в точку, и вычислил где этот график пересекает окружность oO я думаю не так уж и сложно

person Community    schedule 19.11.2008
comment
... или пересечет круг, если внутри круга. - person Brad Gilbert; 19.11.2008

arrow_upward
3
arrow_downward

Решите сначала математически, а потом переведите в код. Помните, что самая короткая линия между точкой и краем круга также будет проходить через его центр (как указано @litb).

person Daniel Spiewak    schedule 19.11.2008

arrow_upward
2
arrow_downward

  1. Точка кратчайшего расстояния лежит на пересечении окружности и линии, проходящей через центр и точку ввода. Также центр, точки входа и выхода лежат на прямой линии

  2. пусть центр будет (xc, yc), а кратчайшая точка от входа (xi, yi) будет (x, y), тогда sqrt ((xc-x) ^ 2 + (yc-y) ^ 2) = r

  3. поскольку центр, точки входа и выхода лежат на прямой линии, наклон, рассчитанный между любой из двух этих точек, должен быть одинаковым.

(yc-yi)/(xc-xi) = (y-yc)/(x-xc)

4. Решение уравнений 2 и 3 должно дать нам самую короткую точку.

person user830818    schedule 31.08.2012

arrow_upward
1
arrow_downward

Запустите функции, умножьте на r и добавьте pX или pY в зависимости от ситуации.

person Windows programmer    schedule 19.11.2008
comment
Почему бы вам не использовать триггер в задаче триггера? - person mmcdole; 19.11.2008
comment
Тригонометрия часто (обычно) очень медленная по сравнению с другими методами. Одним из примеров является вычисление кратчайшего расстояния между точкой и отрезком линии; решение матричной алгебры намного быстрее, чем тригон. - person MusiGenesis; 19.11.2008
comment
Как правило, если вы используете триггер, вы, вероятно, делаете это неправильно. Почти всегда есть более простые/быстрые методы с использованием векторов или других конструкций. - person phkahler; 08.01.2010

arrow_upward
1
arrow_downward

Считайте центр круга исходной точкой, преобразуйте координаты (pX, pY) в полярные координаты, (тета, r') замените r' на r исходного круга и снова преобразуйте в декартовы координаты ( и скорректировать происхождение).

person Rob Walker    schedule 19.11.2008

arrow_upward
1
arrow_downward

Вы просили самый короткий код, вот он. В четыре строки это можно сделать, хотя там еще и квадратичный. Я считал, что точка находится вне круга. Я не рассматривал, что произойдет, если точка окажется прямо над или под центром окружности, то есть cX=pX.

m=(cY-pY)/(cX-pX);  //slope
b=cY-m*cX;  //or Py-m*Px.  Now you have a line in the form y=m*x+b
X=(  (2mcY)*((-2*m*cY)^2-4*(cY^2+cX^2-b^2-2*b*cY-r^2)*(-1-m^2))^(1/2)  )/(2*(cY^2+cX^2-b^2-2*bc*Y-r^2));
Y=mX+b;

1] Получите уравнение для линии, соединяющей точку и центр окружности.

2] Переместите линию на расстояние одного радиуса от центра, чтобы найти точку на окружности. То есть: radius=a^2+b^2, что равно: r=((cY-Y)+(cX-X))^(1/2)

3] Решите квадратично. X=quadratic_solver(r=((cY-Y)+(cX-X))^(1/2),X), что, если вы подставите Y=m*X+b, вы получите этот ад выше.

4] X и Y — ваши результаты на круге.

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

person Alex    schedule 19.11.2008
comment
Это выглядит знакомо. Товарищ по команде на соревновании по программированию использовал это решение и получил два подобных решения. Мы закончили со всеми остальными вопросами, так что мы все работали вместе, но не смогли найти правило, для которого самое близкое и самое дальнее. Я применил грубую силу. Это не домашнее задание, это - person Windows programmer; 19.11.2008

arrow_upward
1
arrow_downward

Простой способ представить это с точки зрения изображения и легко превратить в код: возьмем вектор (pX - cX, pY - cY) из центра в точку. Разделить на его длину sqrt(бла-бла-бла), умножить на радиус. Добавьте это к (cX, cY).

person Mike Kantor    schedule 19.11.2008