Como verificar se 4 pontos formam um quadrado?

35

Suponha que eu tenha 4 pontos (eles são de 2 dimensões), que são diferentes uns dos outros, e eu quero saber se eles formam um quadrado. Como fazer isso? (deixe o processo ser o mais simples possível).

    
por MarshalSHI 23.11.2012 / 13:49
fonte

10 respostas

64

Supondo que seu quadrado possa ser rotacionado contra qualquer sistema de coordenadas que você possua, você não pode confiar na repetição de valores X e Y em seus quatro pontos.

O que você pode fazer é calcular as distâncias entre cada um dos quatro pontos. Se você achar o seguinte para ser verdade, você tem um quadrado:

  1. Existem dois pontos, digamos A e C, que são distância x um do outro, e dois outros pontos, digamos B e D, que também são distância x um do outro.

  2. Cada ponto {A, B, C, D} é uma distância igual dos dois pontos que não estão x de distância. Ou seja: se A estiver x longe de C, então será z longe de B e D.

A propósito, a distância z terá que ser SQRT (( x ^ 2) / 2), mas você não precisa confirmar isso. Se as condições 1 e 2 forem verdadeiras, você terá um quadrado. NOTA: Algumas pessoas estão preocupadas com a ineficiência da raiz quadrada. Eu não disse que você deveria fazer este cálculo, eu apenas disse que se você tivesse, você obteria um resultado previsível!

Omínimodetrabalhoquevocêprecisariafazerseriaescolherumponto,digamosAecalcularadistânciaparacadaumdosoutrostrêspontos.SevocêpuderacharqueAéxdeumpontoezemdoisoutrospontos,entãovocêsóprecisachecaressesdoisoutrospontosunscontraosoutros.Seelestambémsãoxumdooutro,entãovocêtemumquadrado.ouseja:

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

ComoAB=AD,verifiqueBD:

  • BD=x

Sóparatercerteza,vocêprecisaverificarosoutroslados:BCeCD.

  • BC=z
  • CD=z

ComoAC=BDecomoAB=AD=BC=CD,esteé,portanto,umquadrado.

Aolongodocaminho,sevocêencontrarmaisdeduasdistânciasdistintas,afiguranãopodeserumquadrado,entãovocêpodeparardeprocurar.

Implementaçãodeexemplodetrabalho

Eucrieiumexemplodetrabalhonojsfiddle(veja aqui ). Na minha explicação do algoritmo, eu uso pontos arbitrários A, B, C e D. Esses pontos arbitrários estão em uma certa ordem para caminhar pelo exemplo. O algoritmo funciona mesmo se os pontos estiverem em uma ordem diferente, no entanto, o exemplo não funcionará necessariamente se esses pontos estiverem em uma ordem diferente.

Agradecimentos a: meshuai, Blrfl, MSalters e Bart van Ingen Schenau por comentários úteis para melhorar esta resposta.

    
por 23.11.2012 / 14:03
fonte
23

Escolha três dos quatro pontos.

Descobrir se é um triângulo isósceles direito, verificando se um dos três vetores entre os pontos é igual a outro girado em 90 graus.

Se sim, calcule o quarto ponto pela adição de vetor e compare-o com o quarto ponto dado.

Note que isso não requer raízes quadradas caras, nem mesmo multiplicação.

    
por 23.11.2012 / 19:59
fonte
14

Acho que a solução mais fácil é a seguinte:

  • Primeiro, calcule o centro dos 4 pontos: center = (A + B + C + D)/4

  • Em seguida, calcule o vetor A - center . Deixe isso ser v := (x,y)

  • Demos v2 o vetor v girado em 90 graus: v2 := (-y, x)

  • Agora, os outros pontos devem ser center - v , center + v2 e center - v2 .

A vantagem desta solução é que você não precisa usar raízes quadradas.

    
por 29.11.2012 / 16:21
fonte
5

Sinto muito, mas algumas respostas não se aplicam.

Para o caso, você mede 3 arestas (digamos AB, AC e AD) para descobrir que duas têm o mesmo tamanho (digamos AC e AD) e uma é maior (digamos AB). Então você medirá CD para ver se é do mesmo tamanho de AB, e você acha que é. Em vez de um quadrado, você poderia ter a foto abaixo, e isso faz com que seja uma solução errada.

Emseguida,tenteoutrasolução:meçatodasasdistânciaspelomenosumavez:AB,AC,AD,BC,BD,CD.Entãovocêdescobreque4delessãoiguaiseosoutros2tambémsãoiguaisentresi.Masvocêpoderiaapenasterumafotocomoabaixo:

Então, essas respostas não estão corretas, apesar das altas votações que receberam.

Uma solução possível: se as duas medidas iguais não conectarem o mesmo ponto. Então, se AB e CD são o mesmo comprimento, todas as outras combinações (AC, AD, BC, BD) também são iguais, você tem um quadrado. Se você tiver o mesmo ponto fazendo o maior comprimento (AB e AC é o maior, e todos os outros são iguais), você tem uma das fotos acima.

    
por 23.11.2012 / 16:10
fonte
3

Deixe os quatro pontos terem vetores de coordenadas a, b, c, d.

Então vamos chamar suas diferenças w = (a-d), x = (b-a), y = (c-b), z = (d-c).

Então w é ortogonal a a se você pode criar w de uma rotação de 90 graus. Matematicamente a matriz de rotação de 90 graus no espaço 2 é ((0, -1), (1, 0)). Assim, a condição se w é uma rotação de 90 graus resulta em

(w_1 == -x_2 e w_2 == x_1)

Se isso acontecer, você precisa verificar se w == -yex = = -z ou

((w_1 == -y_1 e w_2 == -y_2) e (x_1 == -z_1 e x_2 == -z_2))

Se essas três relações mantêm, a, b, c, d formam um quadrado orientado.

    
por 23.11.2012 / 16:00
fonte
2

Semelhante à resposta de starblue

Escolha três dos quatro pontos.

Procure por um vértice em ângulo reto entre eles : Verificando se o produto escalar de quaisquer dois dos três vetores é zero. Se não for encontrado, não um quadrado.

Verifique se os vértices adjacentes a este ângulo estão em ângulo reto também. Se não, não um quadrado.

Verifique se as diagonais são perpendiculares : Se o produto escalar dos vetores entre o primeiro e o quarto vértice e os outros dois vértices (diagonais) for zero, então é um quadrado.

    
por 29.11.2012 / 00:31
fonte
2

Háalgumasboasrespostasaqui,masaperguntaéaabordagemmaissimples.Eudeiumpensamentorápidoeéassimqueeufaria.

Vocêpodedizersequatropontosrepresentamumquadrado(mesmoquegirados),masencontraramédiadosquatropontos.

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

Umavezquevocêtenhaamédia,adistânciaentrecadapontoeamédiateriaqueseramesmaparatodososquatropontos.

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

EDITAR:

Meu erro. Isso só diria se os pontos do formulário estavam em um círculo. Se você também verificar a distância entre pontos, então deve ser um quadrado.

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"

Isso pressupõe que os pontos A, B, C, D não se cruzam (como em uma ordem de enrolamento válida).

    
por 29.11.2012 / 01:06
fonte
1

esta não é uma resposta de acordo com os padrões definidos, mas espero que isso ajude:

[copiado do link abaixo para que você não precise abrir o link] Python 76 caracteres

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

A função S pega uma lista de números complexos como sua entrada (A). Se conhecermos o centro e um canto de um quadrado, podemos reconstruir o quadrado girando o canto 90,180 e 270 graus em torno do ponto central (c). Na rotação do plano complexo em 90 graus sobre a origem é feita multiplicando o ponto por i. Se a nossa forma original e o quadrado reconstruído tiverem os mesmos pontos, então deve ter sido um quadrado.

Isso foi tirado de: Determine se 4 pontos formam um quadrado

Se você gosta da resposta, eu digo, tire alguns momentos para agradecer a pessoa, ou vote na resposta dele nessa página.

    
por 29.11.2012 / 15:43
fonte
1

Acho que você pode fazer isso com simples adição e subtração e encontrar min / max. Termos (corresponde ao diagrama de outras pessoas):

  • Aponte com o maior valor y = > Um
  • mais alto x = > B
  • mais baixo y = > C
  • mais baixo x = > D

Se 4 pontos compartilham apenas 2 x valores e 2 y valores, você tem um quadrado de nível.

Caso contrário, você tem um quadrado se seus pontos satisfizerem o seguinte:

  • A.x + C.x = B.x + D.x
  • A.y + C.y = B.y + D.y
  • A.y - C.y = B.x - D.x

Explicação: Os segmentos de linha A-C e B-D devem se encontrar em seus pontos médios. Assim (A.x + C.x) / 2 é o ponto médio de A-C e (B.x + D.x) / 2 é o ponto médio de B-D. Multiplique cada lado dessa equação por 2 para obter minha primeira equação. A segunda equação é a mesma coisa para valores Y. Formas de diamante (romboides) satisfazem essas propriedades, então você precisa verificar se tem lados iguais - que a largura é a mesma da altura. Essa é a terceira equação.

    
por 01.12.2012 / 22:46
fonte
-3

A solução é semelhante à mídia pensante.

Primeiro passo:

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

Esta propriedade é seguida por square porque é cíclica. agora um círculo para seguir esta propriedade. então, agora é só verificar

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

if (f==1)
  square
else 
  not square

Aqui A.B significa produto de ponto de A e B

    
por 27.07.2016 / 20:58
fonte