2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Совмещение ломаных
Сообщение26.12.2008, 08:06 


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

Совмещение ломаных. Две ломаные построены по ребрам сеточной области с целочисленными координатами. Требуется составить алгоритм—программу проверки совпадения двух ломаных, составленных из отрезков, с точностью до параллельного переноса и поворота на 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 — ломаные совпадают.

 Профиль  
                  
 
 
Сообщение27.12.2008, 20:48 


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

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

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

 Профиль  
                  
 
 
Сообщение28.12.2008, 22:00 


27/11/05
183
Северодонецк
"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;
}

 Профиль  
                  
 
 
Сообщение09.01.2009, 14:47 


23/12/08
4
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

 Профиль  
                  
 
 
Сообщение09.01.2009, 19:34 


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

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

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

 Профиль  
                  
 
 
Сообщение09.01.2009, 19:54 


29/09/06
4552
Необходимые для совмещения поворот и перенос определяются однозначно по первому отрезку каждой ломаной. Убеждаемся, что они одинаковой длины, определяем угол, убеждаемся, что он 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;

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group