decision_control/slotplanner.cc

   1 /*
   2 This file is part of I am car.
   3
   4 I am car is free software: you can redistribute it and/or modify
   5 it under the terms of the GNU General Public License as published by
   6 the Free Software Foundation, either version 3 of the License, or
   7 (at your option) any later version.
   8
   9 I am car is distributed in the hope that it will be useful,
  10 but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 GNU General Public License for more details.
  13
  14 You should have received a copy of the GNU General Public License
  15 along with I am car. If not, see <http://www.gnu.org/licenses/>.
  16 */
  17
  18 #include <algorithm>
  19 #include <cmath>
  20 #include <list>
  21 #include <queue>
  22 #include "slotplanner.h"
  23
  24 ParallelSlot::ParallelSlot()
  25 {}
  26
  27 // getter
  28 std::vector<RRTNode *> &ParallelSlot::goals()
  29 {
  30         return this->goals_;
  31 }
  32
  33 RRTNode *ParallelSlot::getMidd()
  34 {
  35         if (this->cusp().size() > 0)
  36                 return this->cusp().front().front();
  37         else
  38                 return nullptr;
  39 }
  40
  41 std::vector<std::vector<RRTNode *>> &ParallelSlot::cusp()
  42 {
  43         return this->cusp_;
  44 }
  45
  46 float ParallelSlot::DH() const
  47 {
  48         return this->DH_;
  49 }
  50
  51 PolygonObstacle &ParallelSlot::slot()
  52 {
  53         return this->slot_;
  54 }
  55
  56 float ParallelSlot::slotHeading()
  57 {
  58         return this->slotHeading_;
  59 }
  60
  61 SlotSide ParallelSlot::slotSide()
  62 {
  63         return this->slotSide_;
  64 }
  65
  66 SlotType ParallelSlot::slotType()
  67 {
  68         return this->slotType_;
  69 }
  70
  71 float ParallelSlot::poseHeading()
  72 {
  73         return this->poseHeading_;
  74 }
  75
  76 // setter
  77 void ParallelSlot::DH(float dh)
  78 {
  79         this->DH_ = dh;
  80 }
  81
  82 void ParallelSlot::setAll()
  83 {
  84         // slot heading
  85         float y0 = this->slot().bnodes()[0]->y();
  86         float x0 = this->slot().bnodes()[0]->x();
  87         float y3 = this->slot().bnodes()[3]->y();
  88         float x3 = this->slot().bnodes()[3]->x();
  89         float dy = y3 - y0;
  90         float dx = x3 - x0;
  91         this->slotHeading_ = atan2(dy, dx);
  92         // pose heading
  93         float y1 = this->slot().bnodes()[1]->y();
  94         float x1 = this->slot().bnodes()[1]->x();
  95         dy = y0 - y1;
  96         dx = x0 - x1;
  97         this->poseHeading_ = atan2(dy, dx);
  98         // slot side
  99         if (sgn((x1 - x0) * (y3 - y0) - (y1 - y0) * (x3 - x0)) < 0)
 100                 this->slotSide_ = LEFT;
 101         else
 102                 this->slotSide_ = RIGHT;
 103         // slot type
 104         float d1 = EDIST(
 105                 this->slot().bnodes()[0],
 106                 this->slot().bnodes()[1]
 107         );
 108         float d2 = EDIST(
 109                 this->slot().bnodes()[1],
 110                 this->slot().bnodes()[2]
 111         );
 112         if (d1 > d2)
 113                 this->slotType_ = PERPENDICULAR;
 114         else
 115                 this->slotType_ = PARALLEL;
 116 }
 117
 118 // other
 119 void ParallelSlot::fip(
 120         std::vector<CircleObstacle>& co,
 121         std::vector<SegmentObstacle>& so
 122 )
 123 {
 124         this->setAll();
 125         if (this->slotType() == PERPENDICULAR) {
 126                 std::vector<RRTNode *> tmpc;
 127                 BicycleCar *tmpf = this->getFP();
 128                 BicycleCar *tmpb = this->getISPP(tmpf);
 129                 RRTNode *cc;
 130                 if (this->slotSide() == LEFT)
 131                         cc = tmpb->ccl();
 132                 else
 133                         cc = tmpb->ccr();
 134                 if (this->slotSide() == LEFT)
 135                         this->DH(1 * 0.5 / tmpb->out_radi());
 136                 else
 137                         this->DH(-1 * 0.5 / tmpb->out_radi());
 138                 BicycleCar *p;
 139                 int i = 1;
 140                 p = tmpb->move(cc, i * this->DH());
 141                 while (
 142                         !this->slot().collide(p->frame())
 143                         && ((
 144                                 this->slotSide() == LEFT
 145                                 && (
 146                                         p->h() < this->slotHeading()
 147                                         || (
 148                                                 sgn(p->h()) != sgn(
 149                                                         this->slotHeading()
 150                                                 )
 151                                                 && p->h()
 152                                                 < this->slotHeading()
 153                                                 + 2 * M_PI
 154                                         )
 155                                 )
 156                         ) || (
 157                                 this->slotSide() == RIGHT
 158                                 && (
 159                                         p->h() > this->slotHeading()
 160                                         || p->h() < 0
 161                                 )
 162                         ))
 163                 ) {
 164                         if (tmpc.size() == 0) {
 165                                 i = 0;
 166                                 p = this->getFP();
 167                         }
 168                         bool end = false;
 169                         std::vector<RRTEdge *> eds = p->frame();
 170                         for (auto o: co)
 171                                 if (o.collide(eds))
 172                                         end = true;
 173                         for (auto o: so)
 174                                 if (o.collide(eds))
 175                                         end = true;
 176                         for (auto e: eds)
 177                                 delete e;
 178                         if (end)
 179                                 break;
 180                         this->goals_.push_back(p);
 181                         tmpc.push_back(p);
 182                         i += 1;
 183                         p = tmpb->move(cc, i * this->DH());
 184                 }
 185                 if (tmpc.size() > 0)
 186                         this->cusp().push_back(tmpc);
 187                 return;
 188         }
 189         // see https://courses.cs.washington.edu/courses/cse326/03su/homework/hw3/bfs.html
 190         // RRTNode.s() works as iteration level
 191         std::queue<BicycleCar *, std::list<BicycleCar *>> q;
 192         std::queue<BicycleCar *, std::list<BicycleCar *>> empty;
 193         int di = -1;
 194         if (this->slotSide() == LEFT)
 195                 di = 1;
 196         BicycleCar *CC = this->getEPC();
 197         BicycleCar *B = this->getEP();
 198         this->DH(di * 0.01 / CC->out_radi());
 199         BicycleCar *c;
 200         int i = 0;
 201         c = B->move(CC, -i * di * 0.01 / CC->diag_radi());
 202         while (!this->slot().collide(c->frame())) {
 203                 bool end = false;
 204                 std::vector<RRTEdge *> eds = c->frame();
 205                 for (auto o: co)
 206                         if (o.collide(eds))
 207                                 end = true;
 208                 for (auto o: so)
 209                         if (o.collide(eds))
 210                                 end = true;
 211                 for (auto e: eds)
 212                         delete e;
 213                 if (!end)
 214                         q.push(c);
 215                 c = B->move(CC, -i * di * 0.01 / CC->diag_radi());
 216                 i += 1;
 217         }
 218         delete c; // not in q and collide
 219         while (!q.empty()) {
 220                 c = q.front();
 221                 q.pop();
 222                 if (this->isInside(c)) {
 223                         goto createcuspandfinish;
 224                 } else if (c->s() < 9) {
 225                         BicycleCar *cc = this->flnc(c, co, so);
 226                         cc->s(c->s() + 1);
 227                         cc->bcparent(c);
 228                         q.push(cc);
 229                 } else {
 230                         delete c; // not in q and collide
 231                 }
 232         }
 233         std::swap(q, empty);
 234         return;
 235 createcuspandfinish:
 236         std::vector<RRTNode *> cusp;
 237         while (c) {
 238                 cusp.push_back(new RRTNode(c->x(), c->y(), c->h()));
 239                 c = c->bcparent();
 240         }
 241         std::reverse(cusp.begin(), cusp.end());
 242         this->cusp().push_back(cusp);
 243         std::swap(q, empty);
 244 }
 245
 246 void ParallelSlot::fipf(
 247         std::vector<CircleObstacle>& co,
 248         std::vector<SegmentObstacle>& so
 249 )
 250 {
 251         this->setAll();
 252         std::vector<RRTNode *> tmpc;
 253         BicycleCar *tmpf = this->getFPf();
 254         BicycleCar *tmpb = this->getISPPf(tmpf);
 255         RRTNode *cc;
 256         if (this->slotSide() == LEFT)
 257                 cc = tmpb->ccl();
 258         else
 259                 cc = tmpb->ccr();
 260         if (this->slotSide() == LEFT)
 261                 this->DH(-1 * 0.5 / tmpb->out_radi());
 262         else
 263                 this->DH(1 * 0.5 / tmpb->out_radi());
 264         BicycleCar *p;
 265         int i = 1;
 266         p = tmpb->move(cc, i * this->DH());
 267         while (
 268                 !this->slot().collide(p->frame())
 269                 && ((
 270                         this->slotSide() == LEFT
 271                         && p->h() > this->slotHeading()
 272                 ) || (
 273                         this->slotSide() == RIGHT
 274                         && p->h() < this->slotHeading()
 275                 ))
 276         ) {
 277                 if (tmpc.size() == 0) {
 278                         i = 0;
 279                         p = this->getFPf();
 280                 }
 281                 bool end = false;
 282                 std::vector<RRTEdge *> eds = p->frame();
 283                 for (auto o: co)
 284                         if (o.collide(eds))
 285                                 end = true;
 286                 for (auto o: so)
 287                         if (o.collide(eds))
 288                                 end = true;
 289                 for (auto e: eds)
 290                         delete e;
 291                 if (end)
 292                         break;
 293                 this->goals_.push_back(p);
 294                 tmpc.push_back(p);
 295                 i += 1;
 296                 p = tmpb->move(cc, i * this->DH());
 297         }
 298         if (tmpc.size() > 0)
 299                 this->cusp().push_back(tmpc);
 300         return;
 301 }
 302
 303 BicycleCar *ParallelSlot::flnc(
 304         BicycleCar *B,
 305         std::vector<CircleObstacle>& co,
 306         std::vector<SegmentObstacle>& so
 307 )
 308 {
 309         RRTNode *cc;
 310         if (this->slotSide() == LEFT) {
 311                 if (int(B->s()) % 2 == 0)
 312                         cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 313                 else
 314                         cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 315         } else {
 316                 if (int(B->s()) % 2 == 0)
 317                         cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 318                 else
 319                         cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 320         }
 321         BicycleCar *p;
 322         int i = 1;
 323         p = B->move(cc, i * this->DH());
 324         while (
 325                 !this->slot().collide(p->frame())
 326                 && std::abs(this->slotHeading() - p->h()) < M_PI / 2
 327         ) {
 328                 delete p;
 329                 i += 10;
 330                 p = B->move(cc, i * this->DH());
 331                 bool end = false;
 332                 std::vector<RRTEdge *> eds = p->frame();
 333                 for (auto o: co)
 334                         if (o.collide(eds))
 335                                 end = true;
 336                 for (auto o: so)
 337                         if (o.collide(eds))
 338                                 end = true;
 339                 for (auto e: eds)
 340                         delete e;
 341                 if (end)
 342                         break;
 343         }
 344         i -= 10;
 345         p = B->move(cc, i * this->DH());
 346         while (
 347                 !this->slot().collide(p->frame())
 348                 && std::abs(this->slotHeading() - p->h()) < M_PI / 2
 349         ) {
 350                 if (this->isInside(p)) {
 351                         i += 1;
 352                         break;
 353                 }
 354                 delete p;
 355                 i += 1;
 356                 p = B->move(cc, i * this->DH());
 357                 bool end = false;
 358                 std::vector<RRTEdge *> eds = p->frame();
 359                 for (auto o: co)
 360                         if (o.collide(eds))
 361                                 end = true;
 362                 for (auto o: so)
 363                         if (o.collide(eds))
 364                                 end = true;
 365                 for (auto e: eds)
 366                         delete e;
 367                 if (end)
 368                         break;
 369         }
 370         delete p;
 371         return B->move(cc, (i - 1) * this->DH());
 372 }
 373
 374 void ParallelSlot::fipr(RRTNode *n)
 375 {
 376         return this->fipr(new BicycleCar(n->x(), n->y(), n->h()));
 377 }
 378
 379 void ParallelSlot::fipr(BicycleCar *B)
 380 {
 381         std::vector<RRTNode *> cusp;
 382         cusp.push_back(new RRTNode(B->x(), B->y(), B->h()));
 383         int di = 1;
 384         if (this->slotSide() == LEFT)
 385                 di = -1;
 386         if (this->slotType() == PERPENDICULAR) {
 387                 this->DH(di * 0.01 / B->out_radi()); // TODO car in slot h()
 388                 RRTNode *cc;
 389                 if (this->slotSide() == LEFT)
 390                         cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 391                 else
 392                         cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 393                 BicycleCar *p;
 394                 int i = 1;
 395                 p = B->move(cc, i * this->DH());
 396                 while (
 397                         !this->slot().collide(p->frame())
 398                         && this->slot().collide(p)
 399                 ) {
 400                         delete p;
 401                         i += 10;
 402                         p = B->move(cc, i * this->DH());
 403                 }
 404                 i -= 10;
 405                 p = B->move(cc, i * this->DH());
 406                 while (
 407                         !this->slot().collide(p->frame())
 408                         && this->slot().collide(p)
 409                 ) {
 410                         delete p;
 411                         i += 1;
 412                         p = B->move(cc, i * this->DH());
 413                 }
 414                 i -= 1;
 415                 p = B->move(cc, i * this->DH());
 416                 cusp.push_back(new RRTNode(p->x(), p->y(), p->h()));
 417                 std::reverse(cusp.begin(), cusp.end());
 418                 this->cusp().push_back(cusp);
 419                 return;
 420         }
 421         this->DH(di * 0.01 / B->out_radi());
 422         BicycleCar *c;
 423         c = this->flncr(B);
 424         c->s(B->s() + 1);
 425         while ((
 426                 this->slotSide() == LEFT
 427                 && this->slot().collide(new RRTNode(c->lfx(), c->lfy(), 0))
 428         ) || (
 429                 this->slotSide() == RIGHT
 430                 && this->slot().collide(new RRTNode(c->rfx(), c->rfy(), 0))
 431         )) {
 432                 cusp.push_back(new RRTNode(c->x(), c->y(), c->h()));
 433                 BicycleCar *cc = this->flncr(c);
 434                 cc->s(c->s() + 1);
 435                 delete c;
 436                 c = cc;
 437         }
 438         cusp.push_back(new RRTNode(c->x(), c->y(), c->h()));
 439         std::reverse(cusp.begin(), cusp.end());
 440         this->cusp().push_back(cusp);
 441 }
 442
 443 BicycleCar *ParallelSlot::flncr(BicycleCar *B)
 444 {
 445         RRTNode *cc;
 446         if (this->slotSide() == LEFT) {
 447                 if (int(B->s()) % 2 == 0)
 448                         cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 449                 else
 450                         cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 451         } else {
 452                 if (int(B->s()) % 2 == 0)
 453                         cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 454                 else
 455                         cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 456         }
 457         BicycleCar *p;
 458         int i = 1;
 459         p = B->move(cc, i * this->DH());
 460         while (
 461                 !this->slot().collide(p->frame())
 462                 && ((
 463                         this->slotSide() == LEFT
 464                         && this->slot().collide(new RRTNode(
 465                                 p->lfx(),
 466                                 p->lfy(),
 467                                 0
 468                         ))
 469                 ) || (
 470                         this->slotSide() == RIGHT
 471                         && this->slot().collide(new RRTNode(
 472                                 p->rfx(),
 473                                 p->rfy(),
 474                                 0
 475                         ))
 476                 ))
 477         ) {
 478                 delete p;
 479                 i += 10;
 480                 p = B->move(cc, i * this->DH());
 481         }
 482         i -= 10;
 483         p = B->move(cc, i * this->DH());
 484         while (!this->slot().collide(p->frame())) {
 485                 if(
 486                         this->slotSide() == LEFT
 487                         && !this->slot().collide(new RRTNode(
 488                                 p->lfx(),
 489                                 p->lfy(),
 490                                 0
 491                         ))
 492                 ) {
 493                         i += 1;
 494                         break;
 495                 }
 496                 if(
 497                         this->slotSide() == RIGHT
 498                         && !this->slot().collide(new RRTNode(
 499                                 p->rfx(),
 500                                 p->rfy(),
 501                                 0
 502                         ))
 503                 ) {
 504                         i += 1;
 505                         break;
 506                 }
 507                 i += 1;
 508                 p = B->move(cc, i * this->DH());
 509         }
 510         delete p;
 511         return B->move(cc, (i - 1) * this->DH());
 512 }
 513
 514 RRTNode *ParallelSlot::fposecenter()
 515 {
 516         return this->slot().bnodes().back();
 517 }
 518
 519 bool ParallelSlot::flast(
 520         RRTNode *P,
 521         bool right,
 522         int il,
 523         std::vector<RRTNode *> &cusp
 524 )
 525 {
 526         BicycleCar *B = new BicycleCar(P->x(), P->y(), P->h());
 527         RRTNode *cc;
 528         if (right)
 529                 cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 530         else
 531                 cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 532         BicycleCar *p;
 533         int i = 1;
 534         p = B->move(cc, i * this->DH());
 535         while (!this->slot().collide(p->frame())
 536                         && (
 537                                 (this->DH() > 0 && p->x() <= 0)
 538                                 || (this->DH() < 0 && p->x() >= 0)
 539                         )) {
 540                 delete p;
 541                 i += 10;
 542                 p = B->move(cc, i * this->DH());
 543         }
 544         i -= 10;
 545         p = B->move(cc, i * this->DH());
 546         while (!this->slot().collide(p->frame())
 547                         && (
 548                                 (this->DH() > 0 && p->x() <= 0)
 549                                 || (this->DH() < 0 && p->x() >= 0)
 550                         )) {
 551                 if (this->DH() > 0 && p->rfx() <= 0 && p->rrx() <= 0) {
 552                         i += 1;
 553                         break;
 554                 }
 555                 if (this->DH() < 0 && p->lfx() >= 0 && p->lrx() >= 0) {
 556                         i += 1;
 557                         break;
 558                 }
 559                 delete p;
 560                 i += 1;
 561                 p = B->move(cc, i * this->DH());
 562         }
 563         delete p;
 564         p = B->move(cc, (i - 1) * this->DH());
 565         if (this->DH() > 0 && p->rfx() <= 0 && p->rrx() <= 0) {
 566                 cusp.push_back(p);
 567                 return true;
 568         } else if (this->DH() < 0 && p->lfx() >= 0 && p->lrx() >= 0) {
 569                 cusp.push_back(p);
 570                 return true;
 571         } else if (il < 8) {
 572                 cusp.push_back(p);
 573                 return this->flast(p, !right, il + 1, cusp);
 574         }
 575         return false;
 576 }
 577
 578 void ParallelSlot::fpose()
 579 {
 580         bool left = false; // right parking slot
 581         float di = -1;
 582         BicycleCar *CC = new BicycleCar(
 583                 this->fposecenter()->x(),
 584                 this->fposecenter()->y() - 0.01,
 585                 this->slotHeading()
 586         );
 587         BicycleCar *B = new BicycleCar(
 588                 CC->x() - CC->width() / 2,
 589                 CC->y() - (CC->length() + CC->wheelbase()) / 2,
 590                 this->slotHeading()
 591         );
 592         if (this->slot().bnodes()[0]->x() > this->slot().bnodes()[1]->x()) {
 593                 left = true;
 594                 di = 1;
 595                 delete B;
 596                 B = new BicycleCar(
 597                         CC->x() + CC->width() / 2,
 598                         CC->y() - (CC->length() + CC->wheelbase()) / 2,
 599                         this->slotHeading()
 600                 );
 601         }
 602         this->DH(di * 0.01 / CC->out_radi());
 603         BicycleCar *p;
 604         int i = 0;
 605         p = B->move(CC, -i * di * 0.01 / CC->diag_radi());
 606         while (!this->slot().collide(p->frame())) {
 607                 std::vector<RRTNode *> tmpcusp;
 608                 tmpcusp.push_back(new BicycleCar(p->x(), p->y(), p->h()));
 609                 if (this->flast(p, left, 0, tmpcusp)) {
 610                         this->cusp().push_back(tmpcusp);
 611                         return;
 612                 }
 613                 i += 1;
 614                 delete p;
 615                 p = B->move(CC, -i * di * 0.01 / CC->diag_radi());
 616         }
 617 }
 618
 619 BicycleCar *ParallelSlot::getEP()
 620 {
 621         // new pose for parallel parking to right slot
 622         float tnx;
 623         float tny;
 624         float nx;
 625         float ny;
 626         BicycleCar *CC = this->getEPC();
 627         // move left by car width / 2
 628         tnx = CC->x() + CC->width() / 2 * cos(CC->h() + M_PI / 2);
 629         tny = CC->y() + CC->width() / 2 * sin(CC->h() + M_PI / 2);
 630         if (this->slotSide() == LEFT) {
 631                 // move right by car width / 2
 632                 tnx = CC->x() + CC->width() / 2 * cos(CC->h() - M_PI / 2);
 633                 tny = CC->y() + CC->width() / 2 * sin(CC->h() - M_PI / 2);
 634         }
 635         if (this->slotType() == PARALLEL) {
 636                 // move down
 637                 nx = tnx - (CC->length() + CC->wheelbase()) / 2 * cos(CC->h());
 638                 ny = tny - (CC->length() + CC->wheelbase()) / 2 * sin(CC->h());
 639         } else {
 640                 // move down
 641                 nx = tnx + (CC->length() - CC->wheelbase()) / 2 * cos(CC->h());
 642                 ny = tny + (CC->length() - CC->wheelbase()) / 2 * sin(CC->h());
 643         }
 644         return new BicycleCar(nx, ny, CC->h());
 645 }
 646
 647 BicycleCar *ParallelSlot::getEPC()
 648 {
 649         // new pose for parallel parking to right slot
 650         float ta;
 651         float nx;
 652         float ny;
 653         ta = this->slotHeading() + M_PI;
 654         if (this->slotSide() == RIGHT)
 655                 ta -= M_PI / 4;
 656         else
 657                 ta += M_PI / 4;
 658         nx = this->fposecenter()->x() + 0.01 * cos(ta);
 659         ny = this->fposecenter()->y() + 0.01 * sin(ta);
 660         return new BicycleCar(nx, ny, this->slotHeading());
 661 }
 662
 663 BicycleCar *ParallelSlot::getFP()
 664 {
 665         this->setAll();
 666         float x = this->slot().bnodes()[0]->x();
 667         float y = this->slot().bnodes()[0]->y();
 668         float h = this->slotHeading();
 669         float ph = this->poseHeading();
 670         float nx;
 671         float ny;
 672         if (this->slotType() == PARALLEL) {
 673                 if (this->slotSide() == LEFT) {
 674                         nx = x + BCAR_WIDTH / 2 * cos(h + M_PI / 2);
 675                         ny = y + BCAR_WIDTH / 2 * sin(h + M_PI / 2);
 676                 } else {
 677                         nx = x + BCAR_WIDTH / 2 * cos(h - M_PI / 2);
 678                         ny = y + BCAR_WIDTH / 2 * sin(h - M_PI / 2);
 679                 }
 680                 x = nx + ((BCAR_LENGTH - BCAR_WHEEL_BASE) / 2 + 0.01) * cos(h);
 681                 y = ny + ((BCAR_LENGTH - BCAR_WHEEL_BASE) / 2 + 0.01) * sin(h);
 682         } else {
 683                 if (this->slotSide() == LEFT) {
 684                         nx = x + (BCAR_LENGTH + BCAR_WHEEL_BASE) / 2
 685                                 * cos(ph + M_PI);
 686                         ny = y + (BCAR_LENGTH + BCAR_WHEEL_BASE) / 2
 687                                 * sin(ph + M_PI);
 688                         x = nx + (BCAR_DIAG_RRADI) * cos(h);
 689                         y = ny + (BCAR_DIAG_RRADI) * sin(h);
 690                 } else {
 691                         nx = x + (BCAR_LENGTH + BCAR_WHEEL_BASE) / 2
 692                                 * cos(ph + M_PI);
 693                         ny = y + (BCAR_LENGTH + BCAR_WHEEL_BASE) / 2
 694                                 * sin(ph + M_PI);
 695                         x = nx + (BCAR_DIAG_RRADI) * cos(h);
 696                         y = ny + (BCAR_DIAG_RRADI) * sin(h);
 697                 }
 698         }
 699         return new BicycleCar(x, y, ph);
 700 }
 701
 702 BicycleCar *ParallelSlot::getISPP(BicycleCar *B)
 703 {
 704         // rigt side (for right parking slot)
 705         float x = this->slot().bnodes().back()->x();
 706         float y = this->slot().bnodes().back()->y();
 707         float x1;
 708         float y1;
 709         if (this->slotSide() == LEFT) {
 710                 x1 = B->ccl()->x();
 711                 y1 = B->ccl()->y();
 712         } else {
 713                 x1 = B->ccr()->x();
 714                 y1 = B->ccr()->y();
 715         }
 716         float IR = BCAR_IN_RADI;
 717         float a = 1;
 718         float b = (x1 - x) * 2 * cos(B->h()) + (y1 - y) * 2 * sin(B->h());
 719         float c = pow(x - x1, 2) + pow(y - y1, 2) - pow(IR, 2);
 720         float D = pow(b, 2) - 4 * a * c;
 721         float delta;
 722         delta = -b - sqrt(D);
 723         delta /= 2 * a;
 724         float delta_1 = delta;
 725         // left front (for right parking slot)
 726         x = this->slot().bnodes().front()->x();
 727         y = this->slot().bnodes().front()->y();
 728         IR = BCAR_OUT_RADI;
 729         a = 1;
 730         b = (x1 - x) * 2 * cos(B->h()) + (y1 - y) * 2 * sin(B->h());
 731         c = pow(x - x1, 2) + pow(y - y1, 2) - pow(IR, 2);
 732         D = pow(b, 2) - 4 * a * c;
 733         //delta = -b + sqrt(D);
 734         //delta /= 2 * a;
 735         float delta_2 = delta;
 736         delta = -b - sqrt(D);
 737         delta /= 2 * a;
 738         float delta_3 = delta;
 739         delta = std::max(delta_1, std::max(delta_2, delta_3));
 740         return new BicycleCar(
 741                 B->x() + delta * cos(B->h()),
 742                 B->y() + delta * sin(B->h()),
 743                 B->h()
 744         );
 745 }
 746
 747 BicycleCar *ParallelSlot::getFPf()
 748 {
 749         this->setAll();
 750         float x = this->slot().bnodes().front()->x();
 751         float y = this->slot().bnodes().front()->y();
 752         float h = this->slotHeading();
 753         float ph = this->poseHeading();
 754         ph += M_PI;
 755         while (ph > M_PI)
 756                 ph -= 2 * M_PI;
 757         while (ph <= -M_PI)
 758                 ph += 2 * M_PI;
 759         float nx;
 760         float ny;
 761         nx = x + (BCAR_LENGTH - BCAR_WHEEL_BASE) / 2 * cos(ph);
 762         ny = y + (BCAR_LENGTH - BCAR_WHEEL_BASE) / 2 * sin(ph);
 763         x = nx + (BCAR_DIAG_RRADI) * cos(h);
 764         y = ny + (BCAR_DIAG_RRADI) * sin(h);
 765         return new BicycleCar(x, y, ph);
 766 }
 767
 768 BicycleCar *ParallelSlot::getISPPf(BicycleCar *B)
 769 {
 770         // right rear (for right parking slot)
 771         float x = this->slot().bnodes().front()->x();
 772         float y = this->slot().bnodes().front()->y();
 773         float x1;
 774         float y1;
 775         if (this->slotSide() == LEFT) {
 776                 x1 = B->ccl()->x();
 777                 y1 = B->ccl()->y();
 778         } else {
 779                 x1 = B->ccr()->x();
 780                 y1 = B->ccr()->y();
 781         }
 782         float IR = BCAR_IN_RADI;
 783         float a = 1;
 784         float b = (x - x1) * 2 * cos(B->h()) + (y - y1) * 2 * sin(B->h());
 785         float c = pow(x - x1, 2) + pow(y - y1, 2) - pow(IR, 2);
 786         float D = pow(b, 2) - 4 * a * c;
 787         float delta;
 788         delta = -b - sqrt(D); // TODO why this works?
 789         delta /= 2 * a;
 790         float delta_1 = delta;
 791         // left front (for right parking slot)
 792         x = this->slot().bnodes().back()->x();
 793         y = this->slot().bnodes().back()->y();
 794         IR = BCAR_OUT_RADI;
 795         a = 1;
 796         b = (x - x1) * 2 * cos(B->h()) + (y - y1) * 2 * sin(B->h());
 797         c = pow(x - x1, 2) + pow(y - y1, 2) - pow(IR, 2);
 798         D = pow(b, 2) - 4 * a * c;
 799         delta = -b + sqrt(D);
 800         delta /= 2 * a;
 801         float delta_2 = delta;
 802         delta = -b - sqrt(D);
 803         delta /= 2 * a;
 804         float delta_3 = delta;
 805         delta = std::max(delta_1, std::max(delta_2, delta_3));
 806         return new BicycleCar(
 807                 B->x() - delta * cos(B->h()),
 808                 B->y() - delta * sin(B->h()),
 809                 B->h()
 810         );
 811 }
 812
 813 bool ParallelSlot::isInside(BicycleCar *c)
 814 {
 815         bool inside = true;
 816         RRTNode *tmpn;
 817         tmpn = new RRTNode(c->lfx(), c->lfy(), 0);
 818         if (!this->slot().collide(tmpn))
 819                 inside = false;
 820         delete tmpn;
 821         tmpn = new RRTNode(c->lrx(), c->lry(), 0);
 822         if (!this->slot().collide(tmpn))
 823                 inside = false;
 824         delete tmpn;
 825         tmpn = new RRTNode(c->rrx(), c->rry(), 0);
 826         if (!this->slot().collide(tmpn))
 827                 inside = false;
 828         delete tmpn;
 829         tmpn = new RRTNode(c->rfx(), c->rfy(), 0);
 830         if (!this->slot().collide(tmpn))
 831                 inside = false;
 832         delete tmpn;
 833         return inside;
 834 }
 835
 836 struct SamplingInfo ParallelSlot::getSamplingInfo()
 837 {
 838         struct SamplingInfo si;
 839         RRTNode *n = this->getMidd();
 840         if (n == nullptr)
 841                 return si;
 842         BicycleCar *bc = new BicycleCar(n->x(), n->y(), n->h());
 843         RRTNode *cc;
 844         if (this->slotSide() == LEFT)
 845                 cc = bc->ccl();
 846         else
 847                 cc = bc->ccr();
 848         if (this->slotType() == PARALLEL) {
 849                 BicycleCar *nbc = bc->move(cc, this->slotHeading() - n->h());
 850                 si.x0 = nbc->x();
 851                 si.y0 = nbc->y();
 852                 si.h0 = nbc->h();
 853                 si.x = BCAR_WIDTH;
 854                 si.y = BCAR_WIDTH;
 855                 si.h = M_PI / 8;
 856         } else {
 857                 BicycleCar *nbc;
 858                 if (this->slotSide() == LEFT)
 859                         nbc = bc->move(cc, M_PI/4);
 860                 else
 861                         nbc = bc->move(cc, -M_PI/4);
 862                 si.x0 = nbc->x();
 863                 si.y0 = nbc->y();
 864                 si.h0 = nbc->h();
 865                 si.x = BCAR_WIDTH;
 866                 si.y = BCAR_WIDTH;
 867                 si.h = M_PI / 8;
 868         }
 869         return si;
 870 }