Предположим, у меня есть 4 точки (они 2-мерные), которые отличаются друг от друга, и я хочу знать, образуют ли они квадрат. Как это сделать? (пусть процесс будет максимально простым.)
algorithms
math
geometry
MarshalSHI
источник
источник
Ответы:
Предполагая, что ваш квадрат может быть повернут против любой системы координат, которую вы используете, вы не можете рассчитывать на повторение значений X и Y в ваших четырех точках.
Что вы можете сделать, это рассчитать расстояния между каждой из четырех точек. Если вы считаете, что верно следующее, у вас есть квадрат:
Есть две точки, скажем, A и C, которые являются расстоянием x друг от друга, и две другие точки, скажем, B и D, которые также являются расстоянием x друг от друга.
Каждая точка {A, B, C, D} находится на одинаковом расстоянии от двух точек, которые не удалены от x . То есть: если A на x от C, то это будет на z от B и D.
Кстати, расстояние z должно быть SQRT (( x ^ 2) / 2), но вам не нужно это подтверждать. Если условия 1 и 2 выполняются, то у вас есть квадрат. ПРИМЕЧАНИЕ: Некоторые люди обеспокоены неэффективностью квадратного корня. Я не сказал, что вы должны делать этот расчет, я просто сказал, что если бы вы сделали, вы получите предсказуемый результат!
Минимум работы, которую вам нужно будет сделать, - это выбрать точку, скажем, А, и рассчитать расстояние до каждой из трех других точек. Если вы можете обнаружить, что A - это x из одной точки и z из двух других точек, то вам просто нужно сравнить эти две другие точки друг с другом. Если они также x друг от друга, то у вас есть квадрат. то есть:
Поскольку AB = AD, проверьте BD:
Просто чтобы быть уверенным, вам нужно проверить другие стороны: BC и CD.
Поскольку AC = BD и AB = AD = BC = CD, то это квадрат.
По пути, если вы найдете более двух различных краевых расстояний, фигура не может быть квадратной, поэтому вы можете перестать смотреть.
Реализация рабочего примера
Я создал рабочий пример на jsfiddle (см. Здесь ). В своем объяснении алгоритма я использую произвольные точки A, B, C и D. Эти произвольные точки оказываются в определенном порядке, чтобы пройтись по примеру. Алгоритм работает , даже если точки находятся в другом порядке, однако, пример не обязательно работать , если эти точки находятся в другом порядке.
Спасибо: meshuai, Blrfl, MSalters и Bart van Ingen Schenau за полезные комментарии для улучшения этого ответа.
источник
Выберите три из четырех пунктов.
Выясните, является ли это правильным равнобедренным треугольником, проверив, равен ли один из трех векторов между точками другому, повернутому на 90 градусов.
Если это так, вычислите четвертую точку путем сложения векторов и сравните ее с заданной четвертой точкой.
Обратите внимание, что это не требует дорогих квадратных корней, даже умножения.
источник
sqrt
если не важно! Вам не нужно понижать целочисленные вычисления до FP ... не говоря уже об ухудшении точности вычисления FP.Я думаю, что самое простое решение заключается в следующем:
Сначала рассчитаем центр из 4-х точек:
center = (A + B + C + D)/4
Затем рассчитайте вектор
A - center
. Пусть это будетv := (x,y)
Позвольте
v2
быть вектор,v
повернутый на 90 градусов:v2 := (-y, x)
Теперь другие пункты должны быть
center - v
,center + v2
иcenter - v2
.Преимущество этого решения в том, что вам совсем не нужно использовать квадратные корни.
источник
Извините, но некоторые ответы не применяются.
Для случая, когда вы измеряете 3 ребра (скажем, AB, AC и AD), вы обнаружите, что два имеют одинаковый размер (скажем, AC и AD), а один больше (скажем, AB). Затем вы должны измерить CD, чтобы увидеть, является ли он того же размера AB, и вы обнаружите, что это так. Вместо квадрата у вас может быть изображение ниже, и это делает его неправильным решением.
Затем попробуйте другое решение: измерьте все расстояния хотя бы один раз: AB, AC, AD, BC, BD, CD. Затем вы обнаружите, что 4 из них равны, а остальные 2 также равны между собой. Но вы могли бы просто иметь изображение, как показано ниже:
Таким образом, эти ответы не являются правильными, несмотря на высокие голоса, которые они получили.
Одно из возможных решений: если две равные меры не соединяют одну и ту же точку. Итак: если AB и CD имеют одинаковую длину, все остальные комбинации (AC, AD, BC, BD) также равны, у вас есть квадрат. Если у вас одна и та же точка, делающая самую большую длину (AB и AC самые большие, а все остальные равны), у вас есть одна из картин выше.
источник
Пусть четыре точки имеют координатные векторы a, b, c, d.
Затем назовем их различия w = (ad), x = (ba), y = (cb), z = (dc).
Тогда w ортогонально a, если вы можете создать w из поворота на 90 градусов. Математически матрица вращения на 90 градусов в 2-пространстве равна ((0, -1), (1, 0)). Таким образом, условие, является ли w повернутым на 90 градусов, приводит к
(w_1 == -x_2 и w_2 == x_1)
Если это так, то вам нужно проверить, что w == -y и x == -z, или
((w_1 == -y_1 и w_2 == -y_2) и (x_1 == -z_1 и x_2 == -z_2))
Если эти три отношения выполнены, a, b, c, d образуют ориентированный квадрат.
источник
Аналогично ответу от Starblue
Выберите любые три из четырех пунктов.
Ищите среди них прямоугольную вершину : проверяя, является ли произведение точек любых двух из трех векторов на ноль. Если не найдено, не квадрат.
Проверьте, являются ли вершины, смежные с этим углом, также прямоугольными. Если нет, то не квадрат.
Проверьте, являются ли диагонали перпендикулярными : если скалярное произведение векторов между первой и четвертой вершинами и двумя другими вершинами (диагоналями) равно нулю, то это квадрат.
источник
Я думаю, что вы можете сделать это с помощью простого сложения и вычитания и нахождения мин / макс. Условия (соответствует схеме других людей):
Если 4 точки имеют только 2 значения x и 2 y, у вас есть квадрат уровня.
В противном случае у вас есть квадрат, если ваши очки удовлетворяют следующему:
Пояснение: Сегменты линии AC и BD должны встречаться в своих средних точках. Таким образом (Ax + Cx) / 2 является средней точкой AC, а (Bx + Dx) / 2 является средней точкой BD. Умножьте каждую сторону этого уравнения на 2, чтобы получить мое первое уравнение. Второе уравнение то же самое для значений Y. Ромбовидные фигуры будут удовлетворять этим свойствам, поэтому вам нужно убедиться, что у вас есть равные стороны - ширина равна высоте. Это третье уравнение.
источник
Здесь есть несколько хороших ответов, но вопрос задан для самого простого подхода. Я быстро обдумал это, и вот как я это сделаю.
Вы можете сказать, представляют ли четыре точки квадрат (даже если повернут), но находя среднее из четырех точек.
Как только вы получите среднее значение, расстояние между каждой точкой и средним должно быть одинаковым для всех четырех точек.
РЕДАКТИРОВАТЬ:
Моя ошибка. Это только скажет вам, если точки формы были на круге. Если вы также проверите расстояние между точками, то оно должно быть квадратным.
Это предполагает, что точки A, B, C, D не пересекаются (как в действительном порядке намотки).
источник
это не ответ в соответствии с установленными стандартами, но я надеюсь, что это поможет:
[Скопировано по ссылке ниже, поэтому вам не нужно открывать ссылку] Python 76 символов
Функция S принимает в качестве входных данных список комплексных чисел (A). Если мы знаем как центр, так и один угол квадрата, мы можем восстановить квадрат, повернув угол на 90 180 и 270 градусов вокруг центральной точки (с). В комплексной плоскости поворот на 90 градусов вокруг начала координат производится умножением точки на i. Если наша первоначальная форма и восстановленный квадрат имеют одинаковые точки, то это должен быть квадрат.
Это было взято из: Определить, если 4 точки образуют квадрат
Если вам нравится ответ, скажу вам, потратьте несколько минут, чтобы поблагодарить этого человека, или проголосуйте за его ответ на этой странице.
источник
Основная идея (это отвечает на вопрос о том, вносил ли я что-то новое, что было задано ботом, когда я щелкал, чтобы дать ответ):
Мое решение в R представлено ниже. Я предполагаю, что есть ровно четыре пункта и что согласно постановке задачи уже было определено, что точки являются уникальными.
Смотрите работы Нормана Wildberger, особенно его видео на YouTube ( Real рыбы, реальные цифры, реальные рабочие места и сл.) И его книга Божественные Пропорции для обсуждения «quadrance.»
xy
относится к своему роду матрица , принятой R вplot
,points
иlines
функции.Применение
as.data.frame
трюка, чтобы заставить R делать вещи по столбцам.Предложение
optional=T
исключает имена, которые не используются, в любом случае.Это функция для вычисления квадрантов между указанными точками, где пары точек указаны
i2
аргументом.i2
Символ относится к матрице индекса , который имеет один столбец , индекс, и 2 элементов на колонке (такой же вид матрицы , возвращенноеcombn
функцией).Это
.which
представлено в качестве аргумента просто для того, чтобы разоблачить этоformals
и попытаться сообщить, что происходит.Я сказал, что «простой» не включает многострочные функции. Вам придется извинить эту двухстрочную функцию.
Обратите внимание, что первые четыре функции полезны сами по себе, за исключением вопроса о четырех пунктах.
источник
Предположим, что четыре точки A = (ax, ay), B = (bx, by), C = (cx, cy), D = (dx, dy), и они образуют точки квадрата в направлении против часовой стрелки. Мы перемещаем точки так, чтобы A находился в точке (0, 0), вычитая ax из bx, cx и dx и вычитая ay из by, cy и dy, устанавливая ax = ay = 0.
Если точки являются точными углами квадрата в порядке против часовой стрелки, то, учитывая A и B, мы можем вычислить, где C и D: Мы должны иметь (cx, cy) = (bx - by, bx + by) и (dx, dy) = (-by, bx). Таким образом, мы вычисляем квадратное расстояние от того места, где C и D, до того места, где они должны быть: errC = (cx - bx + by) ^ 2 + (cy - bx - by) ^ 2 и errD = (dx + by) ^ 2 + (dy - bx) ^ 2. Мы добавляем их и делим на (bx ^ 2 + на ^ 2), получая err = (errC + errD) / (bx ^ 2 + на ^ 2).
Результатом err будет 0, если идеальный квадрат, или небольшое число, если почти квадрат, и число останется неизменным, за исключением ошибок округления, если мы переместим, масштабируем или повернем точки квадрата. Таким образом, мы можем использовать err, чтобы решить, насколько хорош квадрат.
Но мы не знаем порядок пунктов. B и D должны находиться на одинаковом расстоянии от A; если мы умножим это на квадратный корень из 2, это должно быть расстояние от A до C. Мы используем это, чтобы выяснить, какая точка является C: Вычислить distB = bx ^ 2 + на ^ 2, distD = dx ^ 2 + dy ^ 2. Если distD ≥ 1,5 distB, то мы меняем местами C и D; если distB ≥ 1,5 distD, то мы меняем местами C и B. Теперь C прав.
Мы также можем выяснить, какие точки представляют собой B и D: если мы не догадались, какая из них B, а какая D, то наши вычисления помещают D в совершенно неправильное место, совершенно противоположное тому, где оно находится. Так что, если errD ≥ (bx ^ 2 + на ^ 2), то мы поменяемся местами B и D.
Это правильно расположит B, C и D, если у нас действительно квадрат или хотя бы примерно квадрат. Но если у нас нет даже примерно квадрата, мы знаем, что вычисление ошибки в конце покажет это.
Резюме:
Если мы знаем порядок точек, это, очевидно, можно упростить.
источник
Решение похоже на мышление СМИ.
Первый шаг:
За этим свойством следует квадрат, потому что оно циклическое. Теперь круг, чтобы следовать за этим свойством. так что теперь просто проверьте
Здесь AB означает точечное произведение A и B
источник