Лучший способ найти точку на окружности, ближайшую к данной точке
Учитывая точку (pX, pY) и круг с известным центром (cX, cY) и радиусом (r), какой кратчайший объем кода вы можете придумать, чтобы найти точку на окружности, ближайшую к (pX, pY)?
У меня есть какой-то код для работы, но он включает преобразование круга в уравнение формы (x - cX) ^ 2 + (y - cY) ^ 2 = r ^ 2 (где r - радиус) и использование уравнения линии от точки (pX, pY) до (cX, cY), чтобы создать квадратное уравнение, которое нужно решить.
Как только я устраню ошибки, все будет в порядке, но это кажется таким неэлегантным решением.
Ответы 8
Триггерные функции, умножьте на r и добавьте pX или pY в зависимости от ситуации.
Почему бы вам избежать использования триггера в триггерной задаче?
Тригонометрия часто (обычно) очень медленная по сравнению с другими методами. Один из примеров - вычисление кратчайшего расстояния между точкой и отрезком линии; решение матричной алгебры намного быстрее, чем триггерное.
Как показывает практика, если вы используете триггер, вы, вероятно, делаете это неправильно. Почти всегда есть более простые / быстрые методы с использованием векторов или других конструкций.
Я бы провел линию от центра к точке и вычислил, где этот график пересекает круг oO, я думаю, не так сложно
... или пересекли бы круг, если бы внутри круга.
Сначала решите это математически, а затем переведите в код. Помните, что самая короткая линия между точкой и краем круга также будет проходить через его центр (как указано в @litb).
Считайте центр круга своим началом, преобразуйте координаты (pX, pY) в полярные координаты, (theta, r ') замените r' на r исходного круга и преобразуйте обратно в декартовы координаты ( и отрегулируйте происхождение).
где P - точка, C - центр, а R - радиус, на подходящем "математическом" языке:
V = (P - C); Answer = C + V / |V| * R;
где | V | длина V.
ЛАДНО ЛАДНО
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 измерений.
Я реализовал часть математики, которую вы опубликовали до того, как вы написали свой код. Однако я обнаружил, что мне нужно иметь pX - vX, а не pX + pY, чтобы получить ближайшую сторону. В любом случае спасибо за это - мне любопытно посмотреть, есть ли какие-то более короткие решения.
V / | V | - это единичный вектор от C к P, поэтому я просто умножил его на R и добавил к C. Разве вы не умножили бы на -R, чтобы получить дальнейшую точку?
Я вижу свою ошибку. Я должен был сказать C + V / | V | * Р
Хех, я все равно использовал C + :-)
Отношение расстояния к успеху, разделенное на время, должно установить рекорд.
А что насчет того, когда указанная точка совпадает с центром? Особый случай, с которым нужно иметь дело.
А также, если радиус равен нулю - это все еще круг?
@WW ... я вижу, что ты там делал
Вы могли бы немного упростить объяснение (ИМО), если бы вы просто сказали: «Найти заголовок от центра круга до желаемой точки, нормализовать и умножить на радиус». Итак, если вектор A = центр и вектор B = ваша точка внутри или за пределами указанного круга A + (B - A) .normalized * radius; Теперь все это предполагает, что вы используете структуру или аналогичный для векторов или, по крайней мере, определили базовые математические операторы / функции для ваших векторов ... что OP не сказал, что они сделали, но я думаю, что делает то, что вы делаете, более ясным, вы могли затем предоставьте необходимые операции для нормализации ..
Вы просили самый короткий код, вот он. В четыре строчки это можно сделать, хотя квадратичная еще есть. Я считал, что точка находится вне круга. Я не рассматривал, что происходит, если точка находится прямо над или под центром круга, то есть 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] Переместитесь по линии на расстояние одного радиуса от центра, чтобы найти точку на окружности. То есть: радиус = 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 - ваши результаты на круге.
Я почти уверен, что где-то допустил ошибку, пожалуйста, оставьте комментарий, если кто-то что-то найдет. Конечно, это вырожденный ответ, один ответ наиболее далек от вашей точки зрения, а другой - наиболее близкий.
Выглядит знакомо. Товарищ по команде в соревновании по программированию использовал это решение и в итоге получил два таких решения. Мы ответили на все остальные вопросы, поэтому мы все работали вместе, но не смогли найти правило, для которого ближе всего, а какое дальше. Я набросился на грубую силу. Это не домашнее задание, это
Легко представить это в терминах изображения и легко превратить в код: возьмите вектор (pX - cX, pY - cY) от центра к точке. Разделите его на длину sqrt (бла-бла-бла), умножьте на радиус. Добавьте это в (cX, cY).
Точка кратчайшего расстояния находится на пересечении окружности и прямой, проходящей через центр и входную точку. Также центр, точки входа и выхода лежат на прямой линии.
пусть центр будет (xc, yc), а кратчайшая точка на входе (xi, yi) будет (x, y), тогда sqrt ((xc-x) ^ 2 + (yc-y) ^ 2) = г
поскольку центр, точки входа и выхода лежат на прямой линии, наклон рассчитывается между любой из двух пунктов должен совпадать.
(yc-yi) / (xc-xi) = (y-yc) / (x-xc)
4. решение уравнений 2 и 3 должно дать нам кратчайший путь.
На самом деле был для игры, но, тем не менее, получил решение.