Совмещение ломаных

[1stpm90]

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

Совмещение ломаных. Две ломаные построены по ребрам сеточной области с целочисленными координатами. Требуется составить алгоритм—программу проверки совпадения двух ломаных, составленных из отрезков, с точностью до параллельного переноса и поворота на 90°, 180°, 270°. Исходные данные — число отрезков ломаных и значения координат их концов — определяются в текстовом файле. Выходной файл результатов должен содержать признак 1, если ломаные совпадают, и 0 — в противном случае.
Пример файла исходных данных:
4 — количество отрезков первой ломаной
0 0 1 0 3 0 2 0 1 0 2 0 3 0 3 1
2 — количество отрезков второй ломаной
1 1 1 4 0 4 1 4
Пример файла результатов:
1 — ломаные совпадают.

[Nerazumovskiy]

Как вы уже догадались, программу писать лень.
А вот алгоритм который я придумал:
Ломаные совпадают если одна(короткая) полность находиться во второй.
Сначало надо попытаться свести ломаные к каноничному виду, для етого перместим начало ломаных в точку (0,0) .
Далее выбираем самую длинную ломаную у крутим ее (строим 4 ломаных с поворотом на 90 180 и 270 градусов от начальной).
Теперь надо подумать как ето сделать в кординатах.
Ну перенос делается легко. Поворот на 180 градусов тоже делается несложно(меняем знак у кординат точки и все).
С поворотом на 90 градусов не все так очевидно.
Ну понятно что надо поменять кординату по Х и по У местами, но етого мало. Если нарисовать какуюто ломаную и посмотреть как меняються кординаты то можна заметить что надо ещо както менять знак у кординат.
То что смог заметить я выглялит так. Елси ми крутим против часовой стрлеки то такие случаи (если не мучиться на обобщение):
1) если у x>0 y<0 то надо для поворота на 90 градусов делаем у положительным, а потом уже меняем их местами.
2) если x>0 y>0 меняем знак у х а потом свап.
3) и 4) случай аналогично.
Ну теперь когда у нас ломаные каноничны то надо подвигать меньшую кривую и проверить совпадает ли она с какойто из 4-ех построеных. Все.

Добавлено спустя 12 минут 1 секунду:

Пока писал придумал ещо один метод.
Рассмотрим ломаную в полярных кординатах.
Тогда ломаная будет задаватся только углом поворота и длинной шага.
В таом представлении сравнивать ломание очень легко:
на первом отрезка сначало сравниваем длинну шага у двух ломаных,
а потом ели совпадают шаги то определяем разницу между поворотами(запоминаем его) отрезков далее берем следующие отрезки по длинне и по уже сохраненому повороту.
Если хоть в не совпадает поворот или длинна то обнуляем все и сравниваем все заново.
Ещо можна ввести оптимизацыю в виде проверки можем ли мы теоретически поместить короткую ломаную в оставшейся части прямой.

[bekas]

"1stpm90", попробуйте потестировать следующий эскизный код для обнаружения
совпадения ломаных. Молчаливо предполагается, что данные вводятся
без ошибок и ломаные не замкнуты (это так?), иначе программа грохнется.
Обычно для таких задач такое требование соблюдается.

В случае проблем - будем устранять "дрова", в случае их отсутствия -
займемся разбором, комментариями, оптимизацией и другими полезными
вещами...

#include <memory.h>
#include <string.h>
#include <iostream> 
using namespace std; 

struct decart
{
  int x;
  int y;
};

int cos4[] = {1, 0, -1,  0};
int sin4[] = {0, 1,  0, -1};

int n1, n2;
struct decart *line1, *line2, *nline1, *nline2;

// true, если три точки образуют прямую линию
bool isline(struct decart *p)
{
  return  (p[0].x * p[1].y + p[1].x * p[2].y + p[2].x * p[0].y) -
          (p[0].y * p[1].x + p[1].y * p[2].x + p[2].y * p[0].x) == 0;
}

// В списке отрезков 'src' длиной cnt найти соприкасаемый с
// текущей строящейся ломаной отрезок
// (априори считаем, что данные введены без
// ошибок, поэтому такой отрезок всегда находим)
// (x0,y0) - координаты началa текущей ломаной
// (x1,y1) - координаты конца текущей ломаной
//
// return: true  - присоединение найденного отрезка слева
//         false - присоединение найденного отрезка справа
//         Новые координаты слева или справа возвращаются через 'result'
bool isleft(struct decart *src, int x0, int y0, int x1, int y1, struct decart *result, int cnt)
{
  bool          left;
  struct decart *begin;

  left  = true;
  begin = src;

  for(;;)
  {
    if(src[0].x == x0 && src[0].y == y0)
    {
      result[0] = src[1];
      break;
    }
    if(src[0].x == x1 && src[0].y == y1)
    {
      result[0] = src[1];
      left = false;
      break;
    }
    if(src[1].x == x0 && src[1].y == y0)
    {
      result[0] = src[0];
      break;
    }
    if(src[1].x == x1 && src[1].y == y1)
    {
      result[0] = src[0];
      left = false;
      break;
    }
    src += 2;
  }
  memmove(src, src + 2, (cnt * 2 - 2 - (src - begin)) * sizeof(struct decart));
  return(left);
}

// Склеивание отдельных отрезков в сплошную ломаную
int sort_line(struct decart *src, struct decart *dest, int cnt)
{
  struct decart *begin, tmp;

  begin   = dest;
  dest[0] = src[0];
  dest[1] = src[1];
  dest   += 2;
  src    += 2;

  while(--cnt)
  {
    if(isleft(src, begin[0].x, begin[0].y, dest[-1].x, dest[-1].y, &tmp, cnt))
    {
      memmove(begin + 1, begin, (dest - begin) * sizeof(struct decart));
      begin[0] = tmp;
    }
    else
    {
      dest[0] = tmp;
    }
    ++dest;
  }

  return(dest - begin);
}

// Выбросить среднюю точку из трех точек, если эти
// три точки располагаются на одной линии
int del_punkt(struct decart *p, int cnt)
{
  int           i;
  struct decart *tmp;
  bool          yes_delete;

  do
  {
    yes_delete = false;
    for(tmp = p,i = cnt - 2; i; --i,++tmp)
    {
      if(isline(tmp))
      {
        memmove(tmp + 1, tmp + 2, (cnt - 2 - (tmp - p)) * sizeof(struct decart));
        --cnt;
        yes_delete = true;
        break;
      }
    }
  } while(yes_delete);
  return(cnt);
}

bool eq_line(struct decart *line1, struct decart *line2, int cnt, int step)
{
  int i, j, k, x, y;

  for(i = 0; i < 4; ++i)
  {
    for(j = k = 0; j < cnt; ++j,k += step)
    {
      x =  line1[k].x * cos4[i] + line1[k].y * sin4[i];
      y = -line1[k].x * sin4[i] + line1[k].y * cos4[i];
      if(line2[k].x != x || line2[k].y != y)
        break;
    }
    if(j == cnt)
      return(true);
  }
  return(false);
}

void input_date(void)
{
  int i;

  cout << "?"; 
  cin >> n1 >> n2; 

  line1   = new struct decart[n1 * 2];
  line2   = new struct decart[n2 * 2];
  nline1  = new struct decart[n1 + 1];
  nline2  = new struct decart[n2 + 1];

  for(i = 0; i < n1 * 2; ++i)
  {
    cin >> line1[i].x >> line1[i].y;
  }

  for(i = 0; i < n2 * 2; ++i)
  {
    cin >> line2[i].x >> line2[i].y;
  }
}

void eoj(char c)
{
  delete[] line1;
  delete[] line2;
  delete[] nline1;
  delete[] nline2;

  cout << c << '\n';
}

int main(int argc, char* argv[])
{
  int i, x1, x2, y1, y2;

  input_date();

  n1 = sort_line(line1, nline1, n1);
  n2 = sort_line(line2, nline2, n2);

  n1 = del_punkt(nline1, n1);
  n2 = del_punkt(nline2, n2);

  if(n1 != n2)
  {
    eoj('0');
    return(0);
  }

  // Сдвиг по левому краю
  x1 = nline1[0].x;
  y1 = nline1[0].y;
  x2 = nline2[0].x;
  y2 = nline2[0].y;
  for(i = 0; i < n1; ++i)
  {
    nline1[i].x -= x1;
    nline1[i].y -= y1;
    nline2[i].x -= x2;
    nline2[i].y -= y2;
  }

  if(eq_line(nline1 + 1, nline2 + 1, n1 - 1, +1))
  {
    eoj('1');
    return(0);
  }

  // Сдвиг по правому краю
  x1 = nline1[n1 - 1].x;
  y1 = nline1[n1 - 1].y;
  for(i = 0; i < n1; ++i)
  {
    nline1[i].x -= x1;
    nline1[i].y -= y1;
  }

  if(eq_line(nline1 + n1 - 2, nline2 + n1 - 2, n1 - 1, -1))
  {
    eoj('1');
    return(0);
  }

  eoj('0');
  return 0;
}

[1stpm90]

bekas, Спасибо большое.
Каким образом вводятся данные? и что делает функция eq_line? как осуществляются повороты?

4 — количество отрезков первой ломаной
0 0 1 0 3 0 2 0 1 0 2 0 3 0 3 1
Х Y X Y X Y X Y
0.0 1.0 3.0 2.0 1.0 2.0 3.0 3.1

[bekas]

Сначала вводятся 2 числа, определяющих число отрезков 1-й и 2-й линии, а потом вводятся координаты отрезков этих двух линий.

eq_line поворачивает одну линию относительно другой 4 раза на соответствующую величину градусов(поворот на 0 градусов используется для определения совпадения одной линии с другой дословно). Если во время любого из этих поворотов происходит совпадение линий, функция возвращает успех, иначе - неудачу.

Теорию поворотов смотрите в любом учебнике аналитической геометрии - через синусы и косинусы (в программе это массивы cos4 и sin4).

[Алексей К.]

Необходимые для совмещения поворот и перенос определяются однозначно по первому отрезку каждой ломаной. Убеждаемся, что они одинаковой длины, определяем угол, убеждаемся, что он 0,90,180 или 270 (=-90), далее используем только этот поворот, а не 4 штуки. Возможно, начала ломаных удобно будет перевести в начало координат и потом проверять только поворот. Что-то типа

case   0:  x_1=x_2, y_1 =y_2;
case +90:  x_1=y_2, y_1 =-x_2;
case -90:  x_1=-y_2, y_1 =x_2;
case 180:  x_1=-x_2, y_1 =-y_2;