2 This file is part of I am car.
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.
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.
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/>.
22 #include "slotplanner.h"
24 ParallelSlot::ParallelSlot()
28 std::vector<RRTNode *> &ParallelSlot::goals()
33 RRTNode *ParallelSlot::getMidd()
35 if (this->cusp().size() > 0)
36 return this->cusp().front().front();
41 std::vector<std::vector<RRTNode *>> &ParallelSlot::cusp()
46 float ParallelSlot::DH() const
51 PolygonObstacle &ParallelSlot::slot()
56 float ParallelSlot::slotHeading()
58 return this->slotHeading_;
61 SlotSide ParallelSlot::slotSide()
63 return this->slotSide_;
66 SlotType ParallelSlot::slotType()
68 return this->slotType_;
71 float ParallelSlot::poseHeading()
73 return this->poseHeading_;
77 void ParallelSlot::DH(float dh)
82 void ParallelSlot::setAll()
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();
91 this->slotHeading_ = atan2(dy, dx);
93 float y1 = this->slot().bnodes()[1]->y();
94 float x1 = this->slot().bnodes()[1]->x();
97 this->poseHeading_ = atan2(dy, dx);
99 if (sgn((x1 - x0) * (y3 - y0) - (y1 - y0) * (x3 - x0)) < 0)
100 this->slotSide_ = LEFT;
102 this->slotSide_ = RIGHT;
105 this->slot().bnodes()[0],
106 this->slot().bnodes()[1]
109 this->slot().bnodes()[1],
110 this->slot().bnodes()[2]
113 this->slotType_ = PERPENDICULAR;
115 this->slotType_ = PARALLEL;
119 void ParallelSlot::fip(
120 std::vector<CircleObstacle>& co,
121 std::vector<SegmentObstacle>& so
125 if (this->slotType() == PERPENDICULAR) {
126 std::vector<RRTNode *> tmpc;
127 BicycleCar *tmpf = this->getFP();
128 BicycleCar *tmpb = this->getISPP(tmpf);
130 if (this->slotSide() == LEFT)
134 if (this->slotSide() == LEFT)
135 this->DH(1 * 0.5 / tmpb->out_radi());
137 this->DH(-1 * 0.5 / tmpb->out_radi());
140 p = tmpb->move(cc, i * this->DH());
142 !this->slot().collide(p->frame())
144 this->slotSide() == LEFT
146 p->h() < this->slotHeading()
152 < this->slotHeading()
157 this->slotSide() == RIGHT
159 p->h() > this->slotHeading()
164 if (tmpc.size() == 0) {
169 std::vector<RRTEdge *> eds = p->frame();
180 this->goals_.push_back(p);
183 p = tmpb->move(cc, i * this->DH());
186 this->cusp().push_back(tmpc);
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;
194 if (this->slotSide() == LEFT)
196 BicycleCar *CC = this->getEPC();
197 BicycleCar *B = this->getEP();
198 this->DH(di * 0.01 / CC->out_radi());
201 c = B->move(CC, -i * di * 0.01 / CC->diag_radi());
202 while (!this->slot().collide(c->frame())) {
204 std::vector<RRTEdge *> eds = c->frame();
215 c = B->move(CC, -i * di * 0.01 / CC->diag_radi());
218 delete c; // not in q and collide
222 if (this->isInside(c)) {
223 goto createcuspandfinish;
224 } else if (c->s() < 9) {
225 BicycleCar *cc = this->flnc(c, co, so);
230 delete c; // not in q and collide
236 std::vector<RRTNode *> cusp;
238 cusp.push_back(new RRTNode(c->x(), c->y(), c->h()));
241 std::reverse(cusp.begin(), cusp.end());
242 this->cusp().push_back(cusp);
246 void ParallelSlot::fipf(
247 std::vector<CircleObstacle>& co,
248 std::vector<SegmentObstacle>& so
252 std::vector<RRTNode *> tmpc;
253 BicycleCar *tmpf = this->getFPf();
254 BicycleCar *tmpb = this->getISPPf(tmpf);
256 if (this->slotSide() == LEFT)
260 if (this->slotSide() == LEFT)
261 this->DH(-1 * 0.5 / tmpb->out_radi());
263 this->DH(1 * 0.5 / tmpb->out_radi());
266 p = tmpb->move(cc, i * this->DH());
268 !this->slot().collide(p->frame())
270 this->slotSide() == LEFT
271 && p->h() > this->slotHeading()
273 this->slotSide() == RIGHT
274 && p->h() < this->slotHeading()
277 if (tmpc.size() == 0) {
282 std::vector<RRTEdge *> eds = p->frame();
293 this->goals_.push_back(p);
296 p = tmpb->move(cc, i * this->DH());
299 this->cusp().push_back(tmpc);
303 BicycleCar *ParallelSlot::flnc(
305 std::vector<CircleObstacle>& co,
306 std::vector<SegmentObstacle>& so
310 if (this->slotSide() == LEFT) {
311 if (int(B->s()) % 2 == 0)
312 cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
314 cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
316 if (int(B->s()) % 2 == 0)
317 cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
319 cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
323 p = B->move(cc, i * this->DH());
325 !this->slot().collide(p->frame())
326 && std::abs(this->slotHeading() - p->h()) < M_PI / 2
330 p = B->move(cc, i * this->DH());
332 std::vector<RRTEdge *> eds = p->frame();
345 p = B->move(cc, i * this->DH());
347 !this->slot().collide(p->frame())
348 && std::abs(this->slotHeading() - p->h()) < M_PI / 2
350 if (this->isInside(p)) {
356 p = B->move(cc, i * this->DH());
358 std::vector<RRTEdge *> eds = p->frame();
371 return B->move(cc, (i - 1) * this->DH());
374 void ParallelSlot::fipr(RRTNode *n)
376 return this->fipr(new BicycleCar(n->x(), n->y(), n->h()));
379 void ParallelSlot::fipr(BicycleCar *B)
381 std::vector<RRTNode *> cusp;
382 cusp.push_back(new RRTNode(B->x(), B->y(), B->h()));
384 if (this->slotSide() == LEFT)
386 if (this->slotType() == PERPENDICULAR) {
387 this->DH(di * 0.01 / B->out_radi()); // TODO car in slot h()
389 if (this->slotSide() == LEFT)
390 cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
392 cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
395 p = B->move(cc, i * this->DH());
397 !this->slot().collide(p->frame())
398 && this->slot().collide(p)
402 p = B->move(cc, i * this->DH());
405 p = B->move(cc, i * this->DH());
407 !this->slot().collide(p->frame())
408 && this->slot().collide(p)
412 p = B->move(cc, i * this->DH());
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);
421 this->DH(di * 0.01 / B->out_radi());
426 this->slotSide() == LEFT
427 && this->slot().collide(new RRTNode(c->lfx(), c->lfy(), 0))
429 this->slotSide() == RIGHT
430 && this->slot().collide(new RRTNode(c->rfx(), c->rfy(), 0))
432 cusp.push_back(new RRTNode(c->x(), c->y(), c->h()));
433 BicycleCar *cc = this->flncr(c);
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);
443 BicycleCar *ParallelSlot::flncr(BicycleCar *B)
446 if (this->slotSide() == LEFT) {
447 if (int(B->s()) % 2 == 0)
448 cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
450 cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
452 if (int(B->s()) % 2 == 0)
453 cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
455 cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
459 p = B->move(cc, i * this->DH());
461 !this->slot().collide(p->frame())
463 this->slotSide() == LEFT
464 && this->slot().collide(new RRTNode(
470 this->slotSide() == RIGHT
471 && this->slot().collide(new RRTNode(
480 p = B->move(cc, i * this->DH());
483 p = B->move(cc, i * this->DH());
484 while (!this->slot().collide(p->frame())) {
486 this->slotSide() == LEFT
487 && !this->slot().collide(new RRTNode(
497 this->slotSide() == RIGHT
498 && !this->slot().collide(new RRTNode(
508 p = B->move(cc, i * this->DH());
511 return B->move(cc, (i - 1) * this->DH());
514 RRTNode *ParallelSlot::fposecenter()
516 return this->slot().bnodes().back();
519 bool ParallelSlot::flast(
523 std::vector<RRTNode *> &cusp
526 BicycleCar *B = new BicycleCar(P->x(), P->y(), P->h());
529 cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
531 cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
534 p = B->move(cc, i * this->DH());
535 while (!this->slot().collide(p->frame())
537 (this->DH() > 0 && p->x() <= 0)
538 || (this->DH() < 0 && p->x() >= 0)
542 p = B->move(cc, i * this->DH());
545 p = B->move(cc, i * this->DH());
546 while (!this->slot().collide(p->frame())
548 (this->DH() > 0 && p->x() <= 0)
549 || (this->DH() < 0 && p->x() >= 0)
551 if (this->DH() > 0 && p->rfx() <= 0 && p->rrx() <= 0) {
555 if (this->DH() < 0 && p->lfx() >= 0 && p->lrx() >= 0) {
561 p = B->move(cc, i * this->DH());
564 p = B->move(cc, (i - 1) * this->DH());
565 if (this->DH() > 0 && p->rfx() <= 0 && p->rrx() <= 0) {
568 } else if (this->DH() < 0 && p->lfx() >= 0 && p->lrx() >= 0) {
573 return this->flast(p, !right, il + 1, cusp);
578 void ParallelSlot::fpose()
580 bool left = false; // right parking slot
582 BicycleCar *CC = new BicycleCar(
583 this->fposecenter()->x(),
584 this->fposecenter()->y() - 0.01,
587 BicycleCar *B = new BicycleCar(
588 CC->x() - CC->width() / 2,
589 CC->y() - (CC->length() + CC->wheelbase()) / 2,
592 if (this->slot().bnodes()[0]->x() > this->slot().bnodes()[1]->x()) {
597 CC->x() + CC->width() / 2,
598 CC->y() - (CC->length() + CC->wheelbase()) / 2,
602 this->DH(di * 0.01 / CC->out_radi());
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);
615 p = B->move(CC, -i * di * 0.01 / CC->diag_radi());
619 BicycleCar *ParallelSlot::getEP()
621 // new pose for parallel parking to right slot
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);
635 if (this->slotType() == PARALLEL) {
637 nx = tnx - (CC->length() + CC->wheelbase()) / 2 * cos(CC->h());
638 ny = tny - (CC->length() + CC->wheelbase()) / 2 * sin(CC->h());
641 nx = tnx + (CC->length() - CC->wheelbase()) / 2 * cos(CC->h());
642 ny = tny + (CC->length() - CC->wheelbase()) / 2 * sin(CC->h());
644 return new BicycleCar(nx, ny, CC->h());
647 BicycleCar *ParallelSlot::getEPC()
649 // new pose for parallel parking to right slot
653 ta = this->slotHeading() + M_PI;
654 if (this->slotSide() == RIGHT)
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());
663 BicycleCar *ParallelSlot::getFP()
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();
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);
677 nx = x + BCAR_WIDTH / 2 * cos(h - M_PI / 2);
678 ny = y + BCAR_WIDTH / 2 * sin(h - M_PI / 2);
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);
683 if (this->slotSide() == LEFT) {
684 nx = x + (BCAR_LENGTH + BCAR_WHEEL_BASE) / 2
686 ny = y + (BCAR_LENGTH + BCAR_WHEEL_BASE) / 2
688 x = nx + (BCAR_DIAG_RRADI) * cos(h);
689 y = ny + (BCAR_DIAG_RRADI) * sin(h);
691 nx = x + (BCAR_LENGTH + BCAR_WHEEL_BASE) / 2
693 ny = y + (BCAR_LENGTH + BCAR_WHEEL_BASE) / 2
695 x = nx + (BCAR_DIAG_RRADI) * cos(h);
696 y = ny + (BCAR_DIAG_RRADI) * sin(h);
699 return new BicycleCar(x, y, ph);
702 BicycleCar *ParallelSlot::getISPP(BicycleCar *B)
704 // rigt side (for right parking slot)
705 float x = this->slot().bnodes().back()->x();
706 float y = this->slot().bnodes().back()->y();
709 if (this->slotSide() == LEFT) {
716 float IR = BCAR_IN_RADI;
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;
722 delta = -b - sqrt(D);
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();
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);
735 float delta_2 = delta;
736 delta = -b - sqrt(D);
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()),
747 BicycleCar *ParallelSlot::getFPf()
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();
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);
768 BicycleCar *ParallelSlot::getISPPf(BicycleCar *B)
770 // right rear (for right parking slot)
771 float x = this->slot().bnodes().front()->x();
772 float y = this->slot().bnodes().front()->y();
775 if (this->slotSide() == LEFT) {
782 float IR = BCAR_IN_RADI;
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;
788 delta = -b - sqrt(D); // TODO why this works?
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();
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);
801 float delta_2 = delta;
802 delta = -b - sqrt(D);
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()),
813 bool ParallelSlot::isInside(BicycleCar *c)
817 tmpn = new RRTNode(c->lfx(), c->lfy(), 0);
818 if (!this->slot().collide(tmpn))
821 tmpn = new RRTNode(c->lrx(), c->lry(), 0);
822 if (!this->slot().collide(tmpn))
825 tmpn = new RRTNode(c->rrx(), c->rry(), 0);
826 if (!this->slot().collide(tmpn))
829 tmpn = new RRTNode(c->rfx(), c->rfy(), 0);
830 if (!this->slot().collide(tmpn))
836 struct SamplingInfo ParallelSlot::getSamplingInfo()
838 struct SamplingInfo si;
839 RRTNode *n = this->getMidd();
842 BicycleCar *bc = new BicycleCar(n->x(), n->y(), n->h());
844 if (this->slotSide() == LEFT)
848 if (this->slotType() == PARALLEL) {
849 BicycleCar *nbc = bc->move(cc, this->slotHeading() - n->h());
858 if (this->slotSide() == LEFT)
859 nbc = bc->move(cc, M_PI/4);
861 nbc = bc->move(cc, -M_PI/4);