Как проверить, образуют ли 4 точки квадрат?

35

Предположим, у меня есть 4 точки (они 2-мерные), которые отличаются друг от друга, и я хочу знать, образуют ли они квадрат. Как это сделать? (пусть процесс будет максимально простым.)

MarshalSHI
источник
3
Я так понимаю, вам нужно учитывать повернутые квадраты?
Мартейн Питерс
У вас есть информация о порядке начисления баллов вообще? Т.е. вы можете сказать, являются ли две точки смежными или образуют диагональ? (эта информация может быть использована для упрощения процесса)
Даниэль Б
1
@DanielB Нет другой информации. Это как у меня есть белая бумага, и я рисую на ней 4 точки случайным образом. Тогда я хочу знать, образуют ли они квадрат.
MarshalSHI
5
В частности, если точки представлены в виде чисел с плавающей запятой, полезно включить смысл «допуска» в любое из предложенных ниже сравнений. Точные проверки на равенство могут потерпеть неудачу для результатов операций с плавающей запятой, даже если мы, люди, считаем их «достаточно близкими».
Стефан А. Терре
Это пахнет домашним заданием. Не то чтобы с этим что-то не так. : / whathaveyoutried.com
Джим Г.

Ответы:

65

Предполагая, что ваш квадрат может быть повернут против любой системы координат, которую вы используете, вы не можете рассчитывать на повторение значений X и Y в ваших четырех точках.

Что вы можете сделать, это рассчитать расстояния между каждой из четырех точек. Если вы считаете, что верно следующее, у вас есть квадрат:

  1. Есть две точки, скажем, A и C, которые являются расстоянием x друг от друга, и две другие точки, скажем, B и D, которые также являются расстоянием x друг от друга.

  2. Каждая точка {A, B, C, D} находится на одинаковом расстоянии от двух точек, которые не удалены от x . То есть: если A на x от C, то это будет на z от B и D.

Кстати, расстояние z должно быть SQRT (( x ^ 2) / 2), но вам не нужно это подтверждать. Если условия 1 и 2 выполняются, то у вас есть квадрат. ПРИМЕЧАНИЕ: Некоторые люди обеспокоены неэффективностью квадратного корня. Я не сказал, что вы должны делать этот расчет, я просто сказал, что если бы вы сделали, вы получите предсказуемый результат!

Иллюстрация Квадратных Правил

Минимум работы, которую вам нужно будет сделать, - это выбрать точку, скажем, А, и рассчитать расстояние до каждой из трех других точек. Если вы можете обнаружить, что A - это x из одной точки и z из двух других точек, то вам просто нужно сравнить эти две другие точки друг с другом. Если они также x друг от друга, то у вас есть квадрат. то есть:

  • AB = z
  • AC = x
  • AD = z

Поскольку AB = AD, проверьте BD:

  • BD = x

Просто чтобы быть уверенным, вам нужно проверить другие стороны: BC и CD.

  • BC = Z
  • CD = z

Поскольку AC = BD и AB = AD = BC = CD, то это квадрат.

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


Реализация рабочего примера

Я создал рабочий пример на jsfiddle (см. Здесь ). В своем объяснении алгоритма я использую произвольные точки A, B, C и D. Эти произвольные точки оказываются в определенном порядке, чтобы пройтись по примеру. Алгоритм работает , даже если точки находятся в другом порядке, однако, пример не обязательно работать , если эти точки находятся в другом порядке.


Спасибо: meshuai, Blrfl, MSalters и Bart van Ingen Schenau за полезные комментарии для улучшения этого ответа.

Джоэл Браун
источник
19
Вы можете замкнуть этот процесс и не беспокоиться о порядке расположения точек, измеряя расстояние между ними и отслеживая количество найденных уникальных расстояний. Как только вы превысите два ( x и z Джоэла ), фигура не будет квадратной.
Blrfl
3
Другой оптимизацией было бы сравнение квадратов расстояний, а не расстояний.
vaughandroid
4
@Blrfl: ваш тест не работает. Пусть ABCD - ромб с AB = BC = CD = DA = 1, AC = 1 (короткая диагональ), тогда AD ~ 1.7 (длинная диагональ) / у вас есть только две длины x и z, но фигура не квадрат ,
MSalters
2
@JoelBrown: можно создать форму трапеции с диагоналями AC = BD = x, сторонами AB = BC = AD = z и последней стороной CD = y! = Z.
Барт ван Инген Шенау
2
Достаточно справедливо, однако отметим, что OP явно сказал 2 измерения.
Джоэл Браун
24

Выберите три из четырех пунктов.

Выясните, является ли это правильным равнобедренным треугольником, проверив, равен ли один из трех векторов между точками другому, повернутому на 90 градусов.

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

Обратите внимание, что это не требует дорогих квадратных корней, даже умножения.

starblue
источник
Один из двух хороших ответов. Не используйте, sqrtесли не важно! Вам не нужно понижать целочисленные вычисления до FP ... не говоря уже об ухудшении точности вычисления FP.
К.Стефф
Спасибо. хороший.
MarshalSHI,
Теперь это правильный способ сделать это. Умножение здесь действительно не нужно.
Приходите с
Как вы находите, если 2 вектора перпендикулярны друг другу без их точечного произведения, которое включает умножение?
Паван Манджунат
1
(x, y) повернутый на прямой угол равен (-y, x) или (y, -x), в зависимости от того, поворачиваете ли вы в положительном или отрицательном направлении, соответственно.
звездный синий
17

Я думаю, что самое простое решение заключается в следующем:

  • Сначала рассчитаем центр из 4-х точек: center = (A + B + C + D)/4

  • Затем рассчитайте вектор A - center. Пусть это будетv := (x,y)

  • Позвольте v2быть вектор, vповернутый на 90 градусов:v2 := (-y, x)

  • Теперь другие пункты должны быть center - v, center + v2и center - v2.

Преимущество этого решения в том, что вам совсем не нужно использовать квадратные корни.

Элиан Эббинг
источник
2
Да. Это наиболее понятный и, возможно, самый простой способ реализации.
Эрик Г
Вроде как векторное равенство сегментов. Кто-нибудь может уточнить или доказать, почему это работает?
vCillusion
Не удается, в частности, для случаев (0,0), (2,1), (3, -1), (1, -2) - квадрат не выровнен по оси
vCillusion
1
Это работает для этого случая. Центральная точка (1,5, -0,5), первая точка (0, 0) и три другие точки: (1,5, -0,5) + (1,5, -0,5) = (3, -1); (1,5, -0,5) + (0,5, 1,5) = (2, 1) и (1,5, -0,5) - (0,5, 1,5) = (1, -2), что означает, что это квадрат. Доказательство ... симметрия?
aragaer
1
«Решению расстояния» нужны квадратные корни, но есть «решение расстояния в квадрате», которое не нужно никому. Ваш может быть еще более эффективным ...
Maaartinus
5

Извините, но некоторые ответы не применяются.

Для случая, когда вы измеряете 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 самые большие, а все остальные равны), у вас есть одна из картин выше.

woliveirajr
источник
нет, его алгоритм говорит, что 2 ребра расстояний x не разделяют точку. но вы просто делите C. Итак, предположим, что AC равен x, тогда BD должен быть другим x вместо вашего BC.
MarshalSHI
3

Пусть четыре точки имеют координатные векторы 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 образуют ориентированный квадрат.

Марк Зальцер
источник
1
Я думаю, что прямоугольник также может удовлетворить ваши условия.
MarshalSHI
Нет, первое условие не выполняется ортогональными, но не одинаковыми по длине векторами.
Марк Зальцер
1
да, я просто скучаю по первому Но 4 балла не упорядочены. Итак, нам нужно больше шагов, я думаю, чтобы подтвердить.
MarshalSHI
Да ... если не возникнет более умной идеи, нужно будет зацикливаться. Я думаю, что нужен внешний цикл для вычисления w, x, y, z из каждого возможного упорядочения a, b, c, d и одного внутреннего цикла для каждого возможного упорядочения кортежа w, x, y, z.
Марк Зальцер
2

Аналогично ответу от Starblue

Выберите любые три из четырех пунктов.

Ищите среди них прямоугольную вершину : проверяя, является ли произведение точек любых двух из трех векторов на ноль. Если не найдено, не квадрат.

Проверьте, являются ли вершины, смежные с этим углом, также прямоугольными. Если нет, то не квадрат.

Проверьте, являются ли диагонали перпендикулярными : если скалярное произведение векторов между первой и четвертой вершинами и двумя другими вершинами (диагоналями) равно нулю, то это квадрат.

Максимум
источник
Хорошая идея, но вам все равно нужно проверить, что 4-я вершина находится на правильном расстоянии от других точек. Вы только проверяете, что это по диагонали.
starblue
@starblue Правильно! В противном случае он может сформировать воздушного змея. Обновлено.
Макс
2

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

  • Точка с наибольшим значением y => A
  • самый высокий х => B
  • самый низкий у => C
  • самый низкий x => D

Если 4 точки имеют только 2 значения x и 2 y, у вас есть квадрат уровня.

В противном случае у вас есть квадрат, если ваши очки удовлетворяют следующему:

  • Ax + Cx = Bx + Dx
  • Ay + Cy = By + Dy
  • Ay - Cy = Bx - Dx

Пояснение: Сегменты линии AC и BD должны встречаться в своих средних точках. Таким образом (Ax + Cx) / 2 является средней точкой AC, а (Bx + Dx) / 2 является средней точкой BD. Умножьте каждую сторону этого уравнения на 2, чтобы получить мое первое уравнение. Второе уравнение то же самое для значений Y. Ромбовидные фигуры будут удовлетворять этим свойствам, поэтому вам нужно убедиться, что у вас есть равные стороны - ширина равна высоте. Это третье уравнение.

GlenPeterson
источник
2

введите описание изображения здесь

Здесь есть несколько хороших ответов, но вопрос задан для самого простого подхода. Я быстро обдумал это, и вот как я это сделаю.

Вы можете сказать, представляют ли четыре точки квадрат (даже если повернут), но находя среднее из четырех точек.

R = (A+B+C+D)/4

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

if(dist(R,A) == dist(R,B) == dist(R,C) == dist(R,D) then
   print "Is Square"
else
   print "Is Not Square"

РЕДАКТИРОВАТЬ:

Моя ошибка. Это только скажет вам, если точки формы были на круге. Если вы также проверите расстояние между точками, то оно должно быть квадратным.

if(dist(R,A) == dist(R,B) == dist(R,C) == dist(R,D) AND
  (dist(A,B) == dist(B,C) == dist(C,D) == dist(A,D) then
   print "Is Square"
else
   print "Is Not Square"

Это предполагает, что точки A, B, C, D не пересекаются (как в действительном порядке намотки).

Reactgular
источник
1

это не ответ в соответствии с установленными стандартами, но я надеюсь, что это поможет:

[Скопировано по ссылке ниже, поэтому вам не нужно открывать ссылку] Python 76 символов

def S(A):c=sum(A)/4.0;return set(A)==set((A[0]-c)*1j**i+c for i in range(4))

Функция S принимает в качестве входных данных список комплексных чисел (A). Если мы знаем как центр, так и один угол квадрата, мы можем восстановить квадрат, повернув угол на 90 180 и 270 градусов вокруг центральной точки (с). В комплексной плоскости поворот на 90 градусов вокруг начала координат производится умножением точки на i. Если наша первоначальная форма и восстановленный квадрат имеют одинаковые точки, то это должен быть квадрат.

Это было взято из: Определить, если 4 точки образуют квадрат

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

bad_keypoints
источник
1
Вы можете суммировать алгоритм здесь. Вы ссылаетесь на другой сайт SE, что немного лучше, чем указание на другой сайт, но мы хотим, чтобы ответ был на этой странице, где задается вопрос. Теперь люди должны нажать еще раз, чтобы узнать, каким может быть ответ.
Мартейн Питерс
0

Основная идея (это отвечает на вопрос о том, вносил ли я что-то новое, что было задано ботом, когда я щелкал, чтобы дать ответ):

  • ромб с равными диагоналями - это квадрат.
  • «как можно проще» включает в себя:
    • нет деления,
    • без квадратных корней,
    • нет разветвления,
    • нет поиска,
    • нет проверки угла или погони,
    • нет векторов,
    • без преобразований,
    • нет комплексных чисел,
    • нет многострочных функций, и
    • нет импорта специальных пакетов (используйте только встроенные файлы).
    • (И никаких имперских притязаний!)

Мое решение в R представлено ниже. Я предполагаю, что есть ровно четыре пункта и что согласно постановке задачи уже было определено, что точки являются уникальными.

sumsq <- function(x) sum(x^2)

quadrances.xy <- function(xy) vapply(
    as.data.frame(t(diff(xy)), optional=T), sumsq, 1)

Смотрите работы Нормана Wildberger, особенно его видео на YouTube ( Real рыбы, реальные цифры, реальные рабочие места и сл.) И его книга Божественные Пропорции для обсуждения «quadrance.»

xyотносится к своему роду матрица , принятой R в plot, pointsи linesфункции.

Применение as.data.frameтрюка, чтобы заставить R делать вещи по столбцам.

Предложение optional=Tисключает имена, которые не используются, в любом случае.

quadrances.xy..i2. <- function(xy, i2) vapply(
    as.data.frame(i2, optional=T),
    function(k) quadrances.xy(m[k,]),
    1)

Это функция для вычисления квадрантов между указанными точками, где пары точек указаны i2аргументом. i2Символ относится к матрице индекса , который имеет один столбец , индекс, и 2 элементов на колонке (такой же вид матрицы , возвращенное combnфункцией).

quadrance.every.xy <- function(xy, .which=combn(nrow(xy), 2))
        quadrances.xy..i2.(xy, .which)

Это .whichпредставлено в качестве аргумента просто для того, чтобы разоблачить это formalsи попытаться сообщить, что происходит.

is.square.xy <- function(xy) {
    qq <- sort(quadrance.every.xy(xy))
    all(qq[2:4] == qq[1]) && # ALL SIDES (SHORT QUADRANCES) EQUAL
    qq[5] == qq[6] # ALL DIAGONALS (LONG QUADRANCES) EQUAL
}

Я сказал, что «простой» не включает многострочные функции. Вам придется извинить эту двухстрочную функцию.

xy <- t(matrix(c(3,0,  7,3,  4,7,  0,4), ncol=4))
xy
#      [,1] [,2]
# [1,]    3    0
# [2,]    7    3
# [3,]    4    7
# [4,]    0    4
is.square.xy(xy)
# [1] TRUE

Обратите внимание, что первые четыре функции полезны сами по себе, за исключением вопроса о четырех пунктах.

Ана Нимбус
источник
0

Предположим, что четыре точки 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, если у нас действительно квадрат или хотя бы примерно квадрат. Но если у нас нет даже примерно квадрата, мы знаем, что вычисление ошибки в конце покажет это.

Резюме:

  1. Вычтите топор из bx, cx, dx. Вычтите ay из by, cy, dy.
  2. Пусть distB = bx ^ 2 + через ^ 2, distD = dx ^ 2 + dy ^ 2.
  3. Если distD ≥ 1,5 * distB, поменяйте местами C и D и снова рассчитайте distD.
  4. В противном случае, если distB ≥ 1,5 * distD, поменяйте местами B и C и снова вычислите distB.
  5. Пусть errD = (dx + by) ^ 2 + (dy - bx) ^ 2.
  6. Если errD ≥ distB, то поменяйте местами B и D, поменяйте местами distB и distD, снова рассчитайте errD.
  7. Пусть errC = (cx - bx + by) ^ 2 + (cy - bx - by) ^ 2.
  8. Пусть err = (errC + errD) / distB.
  9. Решите, есть ли у нас квадрат или почти квадрат, в зависимости от значения err.

Если мы знаем порядок точек, это, очевидно, можно упростить.

gnasher729
источник
-3

Решение похоже на мышление СМИ.

Первый шаг:

x = (A+B+C+D)/4
f=0
if(dist(x,A) == dist(x,B) == dist(x,C) == dist(x,D) 
   f=1
else
   f=0

За этим свойством следует квадрат, потому что оно циклическое. Теперь круг, чтобы следовать за этим свойством. так что теперь просто проверьте

if(A.B==B.C==C.D==D.A==0)
  f=1
else 
  f=0

if (f==1)
  square
else 
  not square

Здесь AB означает точечное произведение A и B

singh13
источник