Алгоритм - обход пылесосом территории

=DeaD=

omlin писал(а):

а у меня все ок.... уже везде ставил где можно...

Просто мы с Виталием не считаем что это "ОК"

omlin писал(а):

=DeaD= писал(а):

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

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

Это принципиально неотличимо от другой формы помещения и никакими простыми методами не лечится.

omlin писал(а):

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

Не лечится простыми способами.

omlin писал(а):

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

Ну это у вас какой-то совсем неидеальный компас.

omlin писал(а):

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

Да масса вариантов, хоть вообще исказить все координаты точек по всей карте, мы ведь эту погрешность постепенно накопили?

Но в целом не будет на практике такой вариант работать, поскольку погрешность которую вы накопите не даст вам сомкнуть линии, поэтому надо будет реализовывать что-то существенно более сложное.

omlin

=DeaD= писал(а):

Просто мы с Виталием не считаем что это "ОК"

данная задача решается алгоритмом второго этапа

по-прежнему жду конкретных идей:
1) по решению вопроса несмыкаемости
2) по более красивому воплощению определения типа контура (внешний или внутренний)

думаю здесь полностью решит проблему математика
сам вспоминаю пока что универский курс (а может и школьный :shock:

)

=DeaD=

omlin писал(а):

1) по решению вопроса несмыкаемости

А чем мой ответ не устраивает?

omlin писал(а):

2) по более красивому воплощению определения типа контура (внешний или внутренний)

Направление контура всегда определялось ориентированной площадью фигуры. Ориентированная площадь треугольника (x1,y1)-(x2,y2)-(x3,y3) есть Sd=[ (x2-x1)*(y3-y1)-(y2-y1)*(x3-x1) ]/2, также известная как плоское векторное произведение. Ориентированная площадь много-угольника с вершинами N0,N1,N2, ... ,Nk есть сумма площадей треугольников N0-N1-N2 + N0-N2-N3 + N0-N3-N4 + ... + N0-N(k-1)-Nk.

blindman

omlin писал(а):

у кого-нибудь есть идеи, как сделать это более красиво?

Берем произвольную точку из тех, где робот находился во время обхода контура. Любой луч с началом в этой точке пересечет внутренний контур нечетное число раз, а внешний - четное. Ноль считаем четным числом, касание - за два пересечения.

=DeaD=

blindman писал(а):

Берем произвольную точку из тех, где робот находился во время обхода контура. Любой луч с началом в этой точке пересечет внутренний контур нечетное число раз, а внешний - четное. Ноль считаем четным числом, касание - за два пересечения.

Запаритесь отличать касания от пересечений в точке излома

blindman

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

=DeaD=

blindman писал(а):

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

Вот попробуйте прописать полностью

Вот мой вариант:

Код:

rfwInt rfwSectionsCrossing(rfwSection S1,rfwSection S2,rfwPoint &P,rfwSection &S)
{
  rfwFloat u,v;
  rfwLine L1,L2;
  L1.a=S1.xa-S1.xb; L1.b=S2.xa-S2.xb; L1.c=S1.xa-S2.xa;
  L2.a=S1.ya-S1.yb; L2.b=S2.ya-S2.yb; L2.c=S1.ya-S2.ya;
  rfwFloat d=L1.a*L2.b-L1.b*L2.a;
  rfwFloat d1=L2.b*L1.c-L2.c*L1.b;
  rfwFloat d2=L1.c*L2.a-L2.c*L1.a;
  //printf("d=%d\nd1=%d\nd2=%d\n",d,d1,d2);
  if(d==0){
    if(d1==0 && d2==0){
      //Same line
      rfwFloat length1=(S1.xb-S1.xa)*(S1.xb-S1.xa)+(S1.yb-S1.ya)*(S1.yb-S1.ya);
      rfwFloat u2a=((S2.xa-S1.xa)*(S1.xb-S1.xa)+(S2.ya-S1.ya)*(S1.yb-S1.ya))/length1;
      rfwFloat u2b=((S2.xb-S1.xa)*(S1.xb-S1.xa)+(S2.yb-S1.ya)*(S1.yb-S1.ya))/length1;
      rfwFloat max_u=max(u2a,u2b);
      rfwFloat min_u=min(u2a,u2b);
      if(max_u<0 || min_u>1){
        return -1; //Empty
      }else{
        u2a=max(0,min_u);
        u2b=min(1,max_u);
        S.xa=S1.xa+u2a*(S1.xb-S1.xa);
        S.ya=S1.ya+u2a*(S1.yb-S1.ya);
        S.xb=S1.xa+u2b*(S1.xb-S1.xa);
        S.yb=S1.ya+u2b*(S1.yb-S1.ya);
        return 0; //Section S1+u*(S2-S1), where u2a<=u<=u2b
      };
    }else{
      return -1; //Empty
    };
  }else{
    u=d1/d;
    v=d2/d;
    if(u>=0 && u<=1 && v>=0 && v<=1){
      P.x=S1.xa+u*(S1.xb-S1.xa);
      P.y=S1.ya+u*(S1.yb-S1.ya);
      return 1; //Point
    }else{
      return -1; //Empty
    };
  };
};
 
rfwInt rfwLineAndPolygonSectionCrossing(rfwInt x1, rfwInt y1, rfwInt x2, rfwInt y2, rfwInt xp, rfwInt yp, rfwInt xc, rfwInt yc, rfwInt xn, rfwInt yn){
  if(x1==x2 && y1==y2){ return 0; };
  rfwSection s0,s1,sr;
  rfwPoint pr;
  s0.xa=x1; s0.ya=y1;
  s0.xb=x2; s0.yb=y2;
  s1.xa=xp; s1.ya=yp;
  s1.xb=xc; s1.yb=yc;
  rfwInt res=rfwSectionsCrossing(s0,s1,pr,sr);
  if(res==-1){ return 0; };
  if(res==0){
    //Intersection is section "sr"
    if( ( (sr.xa-xc)*(xc-xp)+(sr.ya-yc)*(yc-yp)>0)
     && (-(sr.xa-xc)*(yn-yc)+(sr.ya-yc)*(xn-xc)>0) ){ return 1; };
    if( ( (sr.xb-xc)*(xc-xp)+(sr.yb-yc)*(yc-yp)>0)
     && (-(sr.xb-xc)*(yn-yc)+(sr.yb-yc)*(xn-xc)>0) ){ return 1; };
    return 0;
  };
  if(res==1){
    //Intersection is point "pr"
    if(pr.x==xp && pr.y==yp){ return 0; }; //PR=P
    if(pr.x==xc && pr.y==yc){ //PR=C
      if( -(xn-xc)*(yc-yp)+(yn-yc)*(xc-xp)>0 ){ //Angle PCN<=180 deg
        if( (-(x1-xc)*(yc-yp)+(y1-yc)*(xc-xp)>0)
         && (-(x1-xc)*(yn-yc)+(y1-yc)*(xn-xc)>0) ){ return 1; };
        if( (-(x2-xc)*(yc-yp)+(y2-yc)*(xc-xp)>0)
         && (-(x2-xc)*(yn-yc)+(y2-yc)*(xn-xc)>0) ){ return 1; };
        return 0;
      }else{ //Angle PCN>180 deg
        if( (-(x1-xc)*(yc-yp)+(y1-yc)*(xc-xp)>0)
         || (-(x1-xc)*(yn-yc)+(y1-yc)*(xn-xc)>0) ){ return 1; };
        if( (-(x2-xc)*(yc-yp)+(y2-yc)*(xc-xp)>0)
         || (-(x2-xc)*(yn-yc)+(y2-yc)*(xn-xc)>0) ){ return 1; };
        return 0;
      };
    }else{ //PR belongs to interval (P,C)
      if( -(x1-xc)*(yc-yp)+(y1-yc)*(xc-xp)>0 ){ return 1; };
      if( -(x2-xc)*(yc-yp)+(y2-yc)*(xc-xp)>0 ){ return 1; };
      return 0;
    };
  };
 
};

Не самый очевидный код, правда ведь?

blindman

Ваще неочевидный.

Код в такую жару писать лениво - сил много уходит, а мне еще работать надо

Алгоритм такой: выбираем произвольный отрезок контура, и точку с той стороны от него, где робот находился во время обхода. Пускаем луч из этой точки перпендикулярно отрезку. Если считать, что отрезок указывает направление "вперед", и препятствие при обходе находилось слева, то и луч направляем "влево". Перебираем все отрезки контура, определяя пересекает их луч или нет. Если не пересекает, переходим к следующему отрезку. Иначе, увеличиваем счетчик пересечений, и проверяем является ли точка пересечения одним из концов текущего отрезка. Если не является переходим к следующему отрезку. Иначе, берем второй отрезок, проходящий через эту же точку, и смотрим, как расположены другие концы этих отрезков по отношению к лучу. Если по одну сторону, то это касание - увеличиваем счетчи, иначе пересечение - счетчик не трогаем. В любом случае, второй отрезок, прошедший через точку пересечения, исключаем из перебора. Цикл.

Случай, когда отрезок лежит на прямой, через которую проходит луч, можно рассматривать как касание или пересечение - результат от этого не меняется.

=DeaD=

blindman писал(а):

проверяем является ли точка пересечения одним из концов текущего отрезка. Если не является переходим к следующему отрезку. Иначе, берем второй отрезок, проходящий через эту же точку, и смотрим, как расположены другие концы этих отрезков по отношению к лучу. Если по одну сторону, то это касание - увеличиваем счетчи, иначе пересечение - счетчик не трогаем. В любом случае, второй отрезок, прошедший через точку пересечения, исключаем из перебора. Цикл.

Не будет работать, если у вас один из отрезков будет лежать на луче вашем. Например, мы попадаем лучем в пересечение отрезков AB и BC, при этом A лежит левее луча, B лежит на луче и C лежит на луче. Дальше отрезок CD может быть направлен левее луча или правее луча, ваш алгоритм этого не различает.

Короче нифига не просто получается. Сравните с безумной простотой метода через ориентированную площадь многоугольника

PS: Кстати, я задумался, у меня похоже ситуация тоже не рассмотрена нормально с отрезком на луче

(( надо проверять.

EdGull

вот так вот господа и рождается в споре истина... :wink:

blindman

=DeaD= писал(а):

Не будет работать, если у вас один из отрезков будет лежать на луче вашем. Например, мы попадаем лучем в пересечение отрезков AB и BC, при этом A лежит левее луча, B лежит на луче и C лежит на луче. Дальше отрезок CD может быть направлен левее луча или правее луча, ваш алгоритм этого не различает.

Точно. Согласен.

Значит, надо немного поправить алгоритм: учитывать, с какой стороны от луча находится конец отрезка. В одну сторону - счетчик +1, в другую +2.

Вложение:

contur.png [ 21.79 КиБ | Просмотров: 7622 ]

На верхнем рисунке: точка X +1, B +1, C +1, Y +1 = 4
На нижнем: точка X +1, B +1, C +2 = 4

В обоих случаях счетчик четный

=DeaD=

blindman писал(а):

Значит, надо немного поправить алгоритм: учитывать, с какой стороны от луча находится конец отрезка. В одну сторону - счетчик +1, в другую +2.

Ну так то да, вариант, но всё равно ориентированная площадь на 2 порядка проще и на порядок быстрее этот же ответ даст.

omlin

вау! мысль у народа пошла. это радует! :Bravo:

ибо хуже всего, когда сплошная критика и никаких конструктивных предложений

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

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

но с небольшими погрешностями, зато, все нормально.

и перешел ко второму этапу...
(разбиение помещения на прямоугольные области и последовательный их обход)
но за 15 минут остававшиеся от обеда - успел только сделать смыкание и нарисовать автомат второго этапа
доделаю чуток попозже

Добавлено спустя 8 минут 56 секунд:
с ориентированной площадью вариант использую обязательно

как я и подозревал, всему решением стала геометрия, и ничего более...

=DeaD=

omlin писал(а):

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

Не понял, а как вы угадываете, что вот именно эта линия последняя?

omlin

красный квадрат, появляющийся при первом достижении стены - это маяк
достигнув его во второй раз, делаем вывод, что обход контура завершен

roboforum.ru

Алгоритм - обход пылесосом территории

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