Вопрос по algorithm, c++ – Прочитать координаты 4 точки. Они делают квадрат?

4

Я вычисляю расстояние между точками, и если расстояния равны, точка образует квадрат, иначе нет. Мой код работает, только если я читаю координаты в следующем порядке A (x, y), B (x, y), C (x, y), D (x, y) или наоборот. Но если я читаю так, например, A (x, y), B (x, y), D (x, y), C (x, y), это не сработает, потому что метод dist вычислит квадратные значения. длина диагонали. Как я могу решить эту проблему?

#include <iostream>
using namespace std;

struct {
    int x;
    int y;
}a[10];

int dist(int x1, int y1, int x2, int y2)
{
    int c1, c2;
    c1 = x2-x1;
    c2 = y2-y1;
    return (c1*c1)+(c2*c2);
}

int main()
{
    int d1, d2, d3, d4;
    for (int i=1; i<=4; i++)
    {
        cout << 'X' << i << '='; cin >> a[i].x;
        cout << 'Y' << i << '='; cin >> a[i].y;
    }
    d1 = dist(a[1].x, a[1].y, a[2].x, a[2].y);
    d2 = dist(a[2].x, a[2].y, a[3].x, a[3].y);
    d3 = dist(a[3].x, a[3].y, a[4].x, a[4].y);
    d4 = dist(a[4].x, a[4].y, a[1].x, a[1].y);
    if(d1==d2 && d1==d3 && d1==d4)
        cout << "Is a square";
    else
        cout << "Is not a square";
    return 0;
}
Если расстояния равны, у тебя есть ромб, а не обязательно квадрат Kos
Вам также следует проверить углы / диагонали. Каждая из четырех точек должна иметь две линии, перпендикулярные друг другу, одинаковой длины и одну диагональ длиныsqrt(2*x*x). chris

Ваш Ответ

4   ответа
9

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

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

Всего точек между точками 6. Подсчитайте их все. Из этих 6 четыре должны быть равны (назовите их длинуx). - это гарантирует ромб

Два других должны быть равны между собой (назовите их длинуy). это гарантирует прямоугольник

Соедините ромб и прямоугольник иBAM - площадь

@ Кос, на самом деле, эта форма не будет соответствовать первому требованию. Luchian Grigore
Cool, но еще одна вещь: вы предполагали, что форма выпуклая. У ОП есть проблемы, когда форма вогнутая, например▶◀, и этого будет недостаточно. Вы также должны принять во внимание заказ. Kos
Я не могу согласиться. Проверка расстояний без учета их порядка рассматривает фигуру как набор из 4 угловых точек, что делает▶◀ и прямоугольник неразличимы. Порядок вершин необходим для различени Kos
@ Леонардо, если они все одинаковые, у тебя шесть нулей hamstergene
Но это не прямоугольник, но он удовлетворяет вашему тесту прямоугольника на основе расстояния. Kos
2

продуктов. Каждая вершина A должна иметь две другие вершины B и C, так что AB и AC находятся под прямым углом (0 внутреннее произведение), а также одну вершину D, так что AB и AD, а также AC и AD находятся точно под 45 градусами (нормализовано). скалярное произведение = acos (45 градусов), т.е. ~ 0,6675). Если это верно для всех четырех вершин, у вас есть квадрат.

2

скажем, A) и считайте, что это начало координат. Получите 3 вектора, сформированные от начала координат до каждого угла (AB, AC, AD). В векторе они даны B-A, C-A и D-A. Рассчитайте внутреннее произведение каждого вектора на другой. Если вершины образуют прямоугольник, одно внутреннее произведение будет равно нулю (векторы перпендикулярных ребер). Если они образуют квадрат, то остальные 2 внутренних произведения также должны быть равны друг другу из-за общего угла в 45 градусов между ними. Таким образом, если один внутренний продукт равен нулю, а два других равны друг другу, а 4 расстояния одинаковы, у вас есть квадрат.

0

ояние в квадрате (что проще, конечно), то для любой пары ребер длиной L1, L2 верно следующее

L1 == L2 || 2*L1 == L2 || L1 = 2*L2

Вы можете создать следующий фрагмент кода для реализации этого:

int isSquare (point *p1, point *p2, point *p3, point *p4) {
double dx, dy;
double dd[6];
point *pp[4];

pp[0]=p1; pp[1]=p2; pp[2]=p3; pp[3]=p4;
int ii, jj, kk, nn;
kk = 0;
// loop over all combinations of first and second point
// six in all
for(ii=0; ii<3; ii++) {
  for(jj=ii+1; jj<4; jj++) {
    dx = pp[ii]->x - pp[jj]->x;
    dy = pp[ii]->y - pp[jj]->y;
    dd[kk]= dx*dx + dy*dy;
    if (dd[kk]==0) return 0; // two identical points: not a square
    if(kk>1) {
      for(nn= 0; nn < kk-1; nn++) {
        // if both are "sides", we expect their length to be the same;
        // if one is a diagonal and the other a side, their ratio is 2
        // since we are working with the square of the number
        if (!(((2*dd[nn] == dd[kk] ) || \
               (dd[nn] == dd[kk])    || \
               (2*dd[kk] == dd[nn] )))) return 0;
      }
    }
     kk++;
  }
}
return 1; // got here: all combinations tested OK, we have a square

}

Похожие вопросы