7 ParkingSlot::ParkingSlot(Point p, double h, double W, double L) :
9 Point(p.x() + W * cos(h - M_PI / 2.0),
10 p.y() + W * sin(h - M_PI / 2.0)),
11 Point(p.x() + W * cos(h - M_PI / 2.0) + L * cos(h),
12 p.y() + W * sin(h - M_PI / 2.0) + L * sin(h)),
13 Point(p.x() + L * cos(h), p.y() + L * sin(h))}),
14 entry_(border_[0], border_[3]),
15 rear_(border_[0], border_[1]),
16 curb_(border_[1], border_[2]),
17 front_(border_[2], border_[3])
21 ParkingSlot::ParkingSlot(double lrx, double lry, double rrx, double rry,
22 double rfx, double rfy, double lfx, double lfy) :
23 border_({Point(lrx, lry), Point(rrx, rry),
24 Point(rfx, rfy), Point(lfx, lfy)}),
25 entry_(border_[0], border_[3]),
26 rear_(border_[0], border_[1]),
27 curb_(border_[1], border_[2]),
28 front_(border_[2], border_[3])
33 ParkingSlot::len() const
35 return this->entry_.len();
39 ParkingSlot::w() const
41 return this->rear_.len();
45 ParkingSlot::lfx() const
47 return this->border_[3].x();
51 ParkingSlot::lfy() const
53 return this->border_[3].y();
57 ParkingSlot::lrx() const
59 return this->border_[0].x();
63 ParkingSlot::lry() const
65 return this->border_[0].y();
69 ParkingSlot::rrx() const
71 return this->border_[1].x();
75 ParkingSlot::rry() const
77 return this->border_[1].y();
81 ParkingSlot::rfx() const
83 return this->border_[2].x();
87 ParkingSlot::rfy() const
89 return this->border_[2].y();
93 ParkingSlot::h() const
95 return atan2(this->lfy() - this->lry(), this->lfx() - this->lrx());
99 ParkingSlot::parallel() const
101 return this->entry_.len() > this->rear_.len();
105 ParkingSlot::right() const
107 return this->border_[1].on_right_side_of(this->entry_);
111 ParkingSlot::swap_side()
113 this->border_[1].rotate(this->border_[0], M_PI);
114 this->border_[2].rotate(this->border_[3], M_PI);
118 ParkingSlot::parked(BicycleCar const& c) const
120 auto b_len = sizeof(this->border_) / sizeof(this->border_[0]);
121 std::vector<Point> b(this->border_, this->border_ + b_len);
122 return c.lf().inside_of(b) && c.lr().inside_of(b)
123 && c.rr().inside_of(b) && c.rf().inside_of(b);
127 ParkingSlot::collide(BicycleCar const& c) const
129 return c.left().intersects_with(this->rear_)
130 && c.left().intersects_with(this->curb_)
131 && c.left().intersects_with(this->front_)
132 && c.rear().intersects_with(this->rear_)
133 && c.rear().intersects_with(this->curb_)
134 && c.rear().intersects_with(this->front_)
135 && c.right().intersects_with(this->rear_)
136 && c.right().intersects_with(this->curb_)
137 && c.right().intersects_with(this->front_)
138 && c.front().intersects_with(this->rear_)
139 && c.front().intersects_with(this->curb_)
140 && c.front().intersects_with(this->front_);
143 std::vector<BicycleCar>
144 ParkingSlot::drive_in_slot(BicycleCar c, unsigned int& max)
146 assert(this->parallel());
147 assert(this->right());
148 assert(c.len() < this->len());
149 assert(c.w() < this->w());
150 std::vector<BicycleCar> path;
151 path.reserve(max + 2);
153 unsigned int cusp = 0;
155 if (c.h() < this->h()) {
156 return std::vector<BicycleCar>();
158 if (this->parked(c)) {
165 if (this->collide(c)) {
178 ParkingSlot::fe(BicycleCar c, unsigned int& max)
180 assert(this->parallel());
181 assert(this->right());
183 double clen = this->offset_ + this->len() - c.df();
184 double cw = this->offset_ + c.w() / 2.0;
185 c.x(this->lrx() + clen * cos(c.h()) + cw * cos(c.h() + M_PI / 2.0));
186 c.y(this->lry() + clen * sin(c.h()) + cw * sin(c.h() + M_PI / 2.0));
189 auto const& b3 = this->border_[3];
190 this->curb_.intersects_with(b3, c.len());
192 auto const& rr = c.rr();
193 auto const& i1 = this->curb_.i1();
194 auto const& i2 = this->curb_.i2();
195 if (rr.edist(i1) < rr.edist(i2)) {
196 max_to_slot = rr.min_angle_between(b3, i1);
198 max_to_slot = rr.min_angle_between(b3, i2);
200 std::vector<BicycleCar> starts;
201 double a_to_slot = 0.0;
202 while (a_to_slot < max_to_slot) {
207 std::vector<std::vector<BicycleCar>> entries;
208 for (auto s: starts) {
209 auto r = this->drive_in_slot(s, max);
211 entries.push_back(r);
214 assert(entries.size() > 0);
215 auto& c1 = entries.front().front();
216 auto& c2 = entries.back().front();
217 double b = std::min(c1.h(), c2.h());
218 double e = std::max(c1.h(), c2.h());
220 Point b1(c1.x() - clen * cos(c1.h()), c1.y() - clen * sin(c1.h()));
221 Point b2(c2.x() - clen * cos(c2.h()), c2.y() - clen * sin(c2.h()));
222 Point e1(c1.x() + clen * cos(c1.h()), c1.y() + clen * sin(c1.h()));
223 Point e2(c2.x() + clen * cos(c2.h()), c2.y() + clen * sin(c2.h()));
226 li1.intersects_with(li2);
236 operator<<(std::ostream& o, ParkingSlot const& s)
239 o << s.border_[0] << ",";
240 o << s.border_[1] << ",";
241 o << s.border_[2] << ",";