55 std::copy(v.begin(), v.end(), std::back_inserter(*
this));
60 std::copy(beg, end, std::back_inserter(*
this));
85 for (const_iterator i = begin(); i != (end() - 1); i++) {
91 (i + 1)->y() - p.
y());
96 (end() - 1)->x() - p.
x(),
97 (end() - 1)->y() - p.
y());
100 begin()->y() - p.
y());
103 return (!(fabs(angle) <
M_PI));
117 for (const_iterator i = begin(); i != end() - 1; i++) {
118 if (poly.
crosses(*i, *(i + 1))) {
122 if (size() > 2 && poly.
crosses(back(), front())) {
133 if ((size() == 0) || (poly.size() == 0)) {
137 for (const_iterator i = begin(); i != end() - 1; i++) {
140 if (fabs(closest.
z() - (*i).z()) < zThreshold) {
146 for (const_iterator i = poly.begin(); i != poly.end() - 1; i++) {
149 if (fabs(closest.
z() - (*i).z()) < zThreshold) {
163 for (const_iterator i = begin(); i != end() - 1; i++) {
177 for (const_iterator i = begin(); i != end() - 1; i++) {
188 for (const_iterator i = begin(); i != end() - 1; i++) {
190 if (
intersects(*i, *(i + 1), p1, p2, withinDist, &x, &y, &m)) {
200 for (const_iterator i = begin(); i != end() - 1; i++) {
218 if (index >= 0 && index < (
int)size()) {
220 }
else if (index < 0 && -index <= (
int)size()) {
221 return at((
int)size() + index);
223 throw ProcessError(
"Index out of range in bracket operator of PositionVector");
237 if (index >= 0 && index < (
int)size()) {
239 }
else if (index < 0 && -index <= (
int)size()) {
240 return at((
int)size() + index);
242 throw ProcessError(
"Index out of range in bracket operator of PositionVector");
255 const_iterator i = begin();
256 double seenLength = 0;
258 const double nextLength = (*i).distanceTo(*(i + 1));
259 if (seenLength + nextLength > pos) {
262 seenLength += nextLength;
263 }
while (++i != end() - 1);
264 if (lateralOffset == 0 || size() < 2) {
267 return positionAtOffset(*(end() - 2), *(end() - 1), (*(end() - 2)).distanceTo(*(end() - 1)), lateralOffset);
280 const_iterator i = begin();
281 double seenLength = 0;
283 const double nextLength = (*i).distanceTo2D(*(i + 1));
284 if (seenLength + nextLength > pos) {
287 seenLength += nextLength;
288 }
while (++i != end() - 1);
301 const_iterator i = begin();
302 double seenLength = 0;
307 if (seenLength + nextLength > pos) {
310 seenLength += nextLength;
311 }
while (++i != end() - 1);
329 const_iterator i = begin();
330 double seenLength = 0;
335 if (seenLength + nextLength > pos) {
338 seenLength += nextLength;
339 }
while (++i != end() - 1);
349 if (pos < 0. || dist < pos) {
352 if (lateralOffset != 0) {
360 return p1 + (p2 - p1) * (pos / dist) + offset;
365 return p1 + (p2 - p1) * (pos / dist);
372 if (pos < 0 || dist < pos) {
375 if (lateralOffset != 0) {
380 return p1 + (p2 - p1) * (pos / dist) + offset;
385 return p1 + (p2 - p1) * (pos / dist);
409 return Position(x / (
double) size(), y / (
double) size(), z / (
double)size());
420 tmp.push_back(tmp[0]);
422 const int endIndex = (int)tmp.size() - 1;
426 if (tmp.
area() != 0) {
428 for (
int i = 0; i < endIndex; i++) {
429 const double z = tmp[i].x() * tmp[i + 1].y() - tmp[i + 1].x() * tmp[i].y();
431 x += (tmp[i].x() + tmp[i + 1].x()) * z;
432 y += (tmp[i].y() + tmp[i + 1].y()) * z;
439 double lengthSum = 0;
440 for (
int i = 0; i < endIndex; i++) {
441 double length = tmp[i].distanceTo(tmp[i + 1]);
442 x += (tmp[i].x() + tmp[i + 1].x()) *
length / 2;
443 y += (tmp[i].y() + tmp[i + 1].y()) *
length / 2;
446 if (lengthSum == 0) {
450 return Position(x / lengthSum, y / lengthSum);
458 for (
int i = 0; i < static_cast<int>(size()); i++) {
459 (*this)[i] = centroid + (((*this)[i] - centroid) * factor);
467 for (
int i = 0; i < static_cast<int>(size()); i++) {
468 (*this)[i] = centroid + (((*this)[i] - centroid) + offset);
489 for (const_iterator i = begin(); i != end() - 1; i++) {
490 len += (*i).distanceTo(*(i + 1));
502 for (const_iterator i = begin(); i != end() - 1; i++) {
503 len += (*i).distanceTo2D(*(i + 1));
517 tmp.push_back(tmp[0]);
519 const int endIndex = (int)tmp.size() - 1;
521 for (
int i = 0; i < endIndex; i++) {
522 area += tmp[i].x() * tmp[i + 1].y() - tmp[i + 1].x() * tmp[i].y();
536 for (const_iterator i = begin(); i != end() - 1; i++) {
537 if (poly.
around(*i, offset)) {
551 std::pair<PositionVector, PositionVector>
557 if (where < 0 || where > len) {
560 if (where <= POSITION_EPS || where >= len -
POSITION_EPS) {
564 first.push_back((*
this)[0]);
566 const_iterator it = begin() + 1;
567 double next = use2D ? first.back().distanceTo2D(*it) : first.back().distanceTo(*it);
571 first.push_back(*it);
573 next = use2D ? first.back().distanceTo2D(*it) : first.back().distanceTo(*it);
575 if (fabs(where - (seen + next)) >
POSITION_EPS || it == end() - 1) {
584 first.push_back(*it);
587 for (; it != end(); it++) {
588 second.push_back(*it);
590 assert(first.size() >= 2);
591 assert(second.size() >= 2);
592 assert(first.back() == second.front());
594 return std::pair<PositionVector, PositionVector>(first, second);
600 for (PositionVector::const_iterator i = geom.begin(); i != geom.end(); i++) {
601 if (i != geom.begin()) {
618 for (
int i = 0; i < (int)size(); i++) {
619 (*this)[i].add(xoff, yoff, zoff);
626 sub(offset.
x(), offset.
y(), offset.
z());
632 for (
int i = 0; i < (int)size(); i++) {
633 (*this)[i].add(-xoff, -yoff, -zoff);
640 add(offset.
x(), offset.
y(), offset.
z());
647 for (
auto i1 = begin(); i1 != end(); ++i1) {
648 pv.push_back(*i1 + offset);
656 for (
int i = 0; i < (int)size(); i++) {
657 (*this)[i].mul(1, -1);
667 return atan2(p1.
x(), p1.
y()) < atan2(p2.
x(), p2.
y());
682 if (p1.
x() != p2.
x()) {
683 return p1.
x() < p2.
x();
685 return p1.
y() < p2.
y();
691 return (P1.
x() - P0.
x()) * (P2.
y() - P0.
y()) - (P2.
x() - P0.
x()) * (P1.
y() - P0.
y());
697 if ((size() > 0) && (v.size() > 0) && (back().distanceTo(v[0]) < sameThreshold)) {
698 copy(v.begin() + 1, v.end(), back_inserter(*
this));
700 copy(v.begin(), v.end(), back_inserter(*
this));
716 ret.push_back(begPos);
719 const_iterator i = begin();
721 while ((i + 1) != end()
723 seen + (*i).distanceTo(*(i + 1)) < beginOffset) {
724 seen += (*i).distanceTo(*(i + 1));
728 while ((i + 1) != end()
730 seen + (*i).distanceTo(*(i + 1)) < endOffset) {
733 seen += (*i).distanceTo(*(i + 1));
738 if (ret.size() == 1) {
739 ret.push_back(endPos);
759 ret.push_back(begPos);
762 const_iterator i = begin();
764 while ((i + 1) != end()
766 seen + (*i).distanceTo2D(*(i + 1)) < beginOffset) {
767 seen += (*i).distanceTo2D(*(i + 1));
771 while ((i + 1) != end()
773 seen + (*i).distanceTo2D(*(i + 1)) < endOffset) {
776 seen += (*i).distanceTo2D(*(i + 1));
781 if (ret.size() == 1) {
782 ret.push_back(endPos);
793 if (beginIndex < 0) {
794 beginIndex += (int)size();
797 assert(beginIndex < (
int)size());
798 assert(beginIndex + count <= (
int)size());
800 for (
int i = beginIndex; i < beginIndex + count; ++i) {
801 result.push_back((*
this)[i]);
812 return front().angleTo2D(back());
821 double minDist = std::numeric_limits<double>::max();
824 for (const_iterator i = begin(); i != end() - 1; i++) {
828 if (dist < minDist) {
829 nearestPos = pos + seen;
835 if (cornerDist < minDist) {
840 if (pos1 == (*(i - 1)).distanceTo2D(*i) && pos2 == 0.) {
842 minDist = cornerDist;
846 seen += (*i).distanceTo2D(*(i + 1));
857 double minDist = std::numeric_limits<double>::max();
860 for (const_iterator i = begin(); i != end() - 1; i++) {
864 if (dist < minDist) {
865 const double pos25D = pos * (*i).distanceTo(*(i + 1)) / (*i).distanceTo2D(*(i + 1));
866 nearestPos = pos25D + seen;
872 if (cornerDist < minDist) {
877 if (pos1 == (*(i - 1)).distanceTo2D(*i) && pos2 == 0.) {
879 minDist = cornerDist;
883 seen += (*i).distanceTo(*(i + 1));
901 double minDist = std::numeric_limits<double>::max();
902 double nearestPos = -1;
905 for (const_iterator i = begin(); i != end() - 1; i++) {
909 if (dist < minDist) {
910 nearestPos = pos + seen;
912 sign =
isLeft(*i, *(i + 1), p) >= 0 ? -1 : 1;
917 if (cornerDist < minDist) {
922 if (pos1 == (*(i - 1)).distanceTo2D(*i) && pos2 == 0.) {
924 minDist = cornerDist;
925 sign =
isLeft(*(i - 1), *i, p) >= 0 ? -1 : 1;
929 seen += (*i).distanceTo2D(*(i + 1));
931 if (nearestPos != -1) {
932 return Position(nearestPos, sign * minDist);
944 double minDist = std::numeric_limits<double>::max();
947 for (
int i = 0; i < (int)size(); i++) {
949 if (dist < minDist) {
963 double minDist = std::numeric_limits<double>::max();
964 int insertionIndex = 1;
965 for (
int i = 0; i < (int)size() - 1; i++) {
969 if (dist < minDist) {
970 insertionIndex = i + 1;
977 const double previousZ = (begin() + (insertionIndex - 1))->z();
978 const double nextZ = (begin() + insertionIndex)->z();
980 insert(begin() + insertionIndex,
Position(p.
x(), p.
y(), ((previousZ + nextZ) / 2.0)));
982 insert(begin() + insertionIndex, p);
984 return insertionIndex;
993 double minDist = std::numeric_limits<double>::max();
994 int removalIndex = 0;
995 for (
int i = 0; i < (int)size(); i++) {
997 if (dist < minDist) {
1002 erase(begin() + removalIndex);
1003 return removalIndex;
1009 std::vector<double> ret;
1010 if (other.size() == 0) {
1013 for (const_iterator i = other.begin(); i != other.end() - 1; i++) {
1015 copy(atSegment.begin(), atSegment.end(), back_inserter(ret));
1023 std::vector<double> ret;
1028 for (const_iterator i = begin(); i != end() - 1; i++) {
1032 if (
intersects(p1, p2, lp1, lp2, 0., &x, &y, &m)) {
1033 ret.push_back(
Position(x, y).distanceTo2D(p1) + pos);
1088 for (const_reverse_iterator i = rbegin(); i != rend(); i++) {
1098 return Position((beg.
y() - end.
y()) * scale, (end.
x() - beg.
x()) * scale);
1112 for (
int i = 0; i < static_cast<int>(size()); i++) {
1115 const Position& to = (*this)[i + 1];
1117 shape.push_back(from -
sideOffset(from, to, amount));
1119 }
else if (i == static_cast<int>(size()) - 1) {
1120 const Position& from = (*this)[i - 1];
1123 shape.push_back(to -
sideOffset(from, to, amount));
1126 const Position& from = (*this)[i - 1];
1128 const Position& to = (*this)[i + 1];
1131 const double extrapolateDev = fromMe[1].distanceTo2D(to);
1134 shape.push_back(me -
sideOffset(from, to, amount));
1139 shape.push_back(fromMe[1]);
1150 shape.push_back(meNew);
1153 shape.back().set(shape.back().x(), shape.back().y(), me.
z());
1168 if (size() != amount.size()) {
1170 +
") does not match number of points (" +
toString(size()) +
")");
1173 for (
int i = 0; i < static_cast<int>(size()); i++) {
1176 const Position& to = (*this)[i + 1];
1178 shape.push_back(from -
sideOffset(from, to, amount[i]));
1180 }
else if (i == static_cast<int>(size()) - 1) {
1181 const Position& from = (*this)[i - 1];
1184 shape.push_back(to -
sideOffset(from, to, amount[i]));
1187 const Position& from = (*this)[i - 1];
1189 const Position& to = (*this)[i + 1];
1192 const double extrapolateDev = fromMe[1].distanceTo2D(to);
1195 shape.push_back(me -
sideOffset(from, to, amount[i]));
1200 shape.push_back(fromMe[1]);
1211 shape.push_back(meNew);
1214 shape.back().set(shape.back().x(), shape.back().y(), me.
z());
1222 if ((pos + 1) < (
int)size()) {
1223 return (*
this)[pos].angleTo2D((*
this)[pos + 1]);
1232 if ((size() != 0) && ((*
this)[0] != back())) {
1233 push_back((*
this)[0]);
1240 std::vector<double> ret;
1242 for (i = begin(); i != end(); i++) {
1243 const double dist = s.
distance2D(*i, perpendicular);
1245 ret.push_back(dist);
1248 for (i = s.begin(); i != s.end(); i++) {
1249 const double dist =
distance2D(*i, perpendicular);
1251 ret.push_back(dist);
1261 return std::numeric_limits<double>::max();
1262 }
else if (size() == 1) {
1263 return front().distanceTo(p);
1304 if ((size() == 0) || !p.
almostSame(front())) {
1312 if (at == begin()) {
1314 }
else if (at == end()) {
1326 return (size() >= 2) && ((*this)[0] == back());
1333 for (
auto i = begin(); i != end(); i++) {
1346 iterator last = begin();
1347 for (iterator i = begin() + 1; i != end() && (!assertLength || size() > 2);) {
1348 if (last->almostSame(*i, minDist)) {
1349 if (i + 1 == end()) {
1367 return static_cast<vp>(*
this) == static_cast<vp>(v2);
1373 return static_cast<vp>(*
this) != static_cast<vp>(v2);
1379 WRITE_ERROR(
"Trying to substract PositionVectors of different lengths.");
1383 auto i2 = v2.begin();
1384 while (i1 != end()) {
1393 WRITE_ERROR(
"Trying to substract PositionVectors of different lengths.");
1397 auto i2 = v2.begin();
1398 while (i1 != end()) {
1409 for (const_iterator i = begin(); i != end() - 1; i++) {
1410 if ((*i).z() != (*(i + 1)).z()) {
1420 const double eps = std::numeric_limits<double>::epsilon();
1421 const double denominator = (p22.
y() - p21.
y()) * (p12.
x() - p11.
x()) - (p22.
x() - p21.
x()) * (p12.
y() - p11.
y());
1422 const double numera = (p22.
x() - p21.
x()) * (p11.
y() - p21.
y()) - (p22.
y() - p21.
y()) * (p11.
x() - p21.
x());
1423 const double numerb = (p12.
x() - p11.
x()) * (p11.
y() - p21.
y()) - (p12.
y() - p11.
y()) * (p11.
x() - p21.
x());
1425 if (fabs(numera) < eps && fabs(numerb) < eps && fabs(denominator) < eps) {
1431 if (p11.
x() != p12.
x()) {
1432 a1 = p11.
x() < p12.
x() ? p11.
x() : p12.
x();
1433 a2 = p11.
x() < p12.
x() ? p12.
x() : p11.
x();
1434 a3 = p21.
x() < p22.
x() ? p21.
x() : p22.
x();
1435 a4 = p21.
x() < p22.
x() ? p22.
x() : p21.
x();
1437 a1 = p11.
y() < p12.
y() ? p11.
y() : p12.
y();
1438 a2 = p11.
y() < p12.
y() ? p12.
y() : p11.
y();
1439 a3 = p21.
y() < p22.
y() ? p21.
y() : p22.
y();
1440 a4 = p21.
y() < p22.
y() ? p22.
y() : p21.
y();
1442 if (a1 <= a3 && a3 <= a2) {
1449 if (a3 <= a1 && a1 <= a4) {
1458 if (p11.
x() != p12.
x()) {
1459 *mu = (a - p11.
x()) / (p12.
x() - p11.
x());
1461 *y = p11.
y() + (*mu) * (p12.
y() - p11.
y());
1465 if (p12.
y() == p11.
y()) {
1468 *mu = (a - p11.
y()) / (p12.
y() - p11.
y());
1477 if (fabs(denominator) < eps) {
1481 double mua = numera / denominator;
1483 if (fabs(p12.
x() - p22.
x()) < eps && fabs(p12.
y() - p22.
y()) < eps) {
1486 const double offseta = withinDist / p11.
distanceTo2D(p12);
1487 const double offsetb = withinDist / p21.
distanceTo2D(p22);
1488 const double mub = numerb / denominator;
1489 if (mua < -offseta || mua > 1 + offseta || mub < -offsetb || mub > 1 + offsetb) {
1494 *x = p11.
x() + mua * (p12.
x() - p11.
x());
1495 *y = p11.
y() + mua * (p12.
y() - p11.
y());
1504 const double s = sin(angle);
1505 const double c = cos(angle);
1506 for (
int i = 0; i < (int)size(); i++) {
1507 const double x = (*this)[i].x();
1508 const double y = (*this)[i].y();
1509 const double z = (*this)[i].z();
1510 const double xnew = x * c - y * s;
1511 const double ynew = x * s + y * c;
1512 (*this)[i].set(xnew, ynew, z);
1520 bool changed =
true;
1521 while (changed && result.size() > 3) {
1523 for (
int i = 0; i < (int)result.size(); i++) {
1525 const Position& p2 = result[(i + 2) % result.size()];
1526 const int middleIndex = (i + 1) % result.size();
1527 const Position& p0 = result[middleIndex];
1529 const double triangleArea2 = fabs((p2.
y() - p1.
y()) * p0.
x() - (p2.
x() - p1.
x()) * p0.
y() + p2.
x() * p1.
y() - p2.
y() * p1.
x());
1533 result.erase(result.begin() + middleIndex);
1554 result.push_back(base);
1556 result.push_back(tmp[closestIndex]);
1557 }
else if (before) {
1559 if (closestIndex > 0) {
1560 result.push_back(tmp[closestIndex - 1]);
1562 result.push_back(tmp[1]);
1566 if (closestIndex < (
int)size() - 1) {
1567 result.push_back(tmp[closestIndex + 1]);
1569 result.push_back(tmp[-1]);
1574 result.
add(base * -1);
1587 const double z0 = (*this)[0].z();
1589 const double dz = (*this)[1].z() - z0;
1591 if (size() > 2 && dz != 0) {
1601 const double dz2 = result[iLast].z() - z0;
1603 for (
int i = 1; i < iLast; ++i) {
1604 seen += result[i].distanceTo2D(result[i - 1]);
1605 result[i].set(result[i].x(), result[i].y(), z0 + dz2 * seen / dist2);
1619 result[0].setz(zStart);
1620 result[-1].setz(zEnd);
1621 const double dz = zEnd - zStart;
1624 for (
int i = 1; i < (int)size() - 1; ++i) {
1625 seen += result[i].distanceTo2D(result[i - 1]);
1626 result[i].setz(zStart + dz * seen /
length);
1635 if (maxLength == 0) {
1643 for (
double pos = 0; pos <=
length; pos += maxLength) {
1652 if (index < 0 || index >= (
int)size()) {
1656 for (
int i = 1; i <= index; ++i) {
1657 seen += (*this)[i].distanceTo2D((*
this)[i - 1]);
1666 for (
int i = 1; i < (int)size(); ++i) {
1667 const Position& p1 = (*this)[i - 1];
1669 const double distZ = fabs(p1.
z() - p2.
z());
1672 maxJump =
MAX2(maxJump, distZ);
1674 result =
MAX2(result, distZ / dist2D);
1684 assert(size() < 33);
1685 static const double fac[33] = {
1686 1.0, 1.0, 2.0, 6.0, 24.0, 120.0, 720.0, 5040.0, 40320.0, 362880.0, 3628800.0, 39916800.0, 479001600.0,
1687 6227020800.0, 87178291200.0, 1307674368000.0, 20922789888000.0, 355687428096000.0, 6402373705728000.0,
1688 121645100408832000.0, 2432902008176640000.0, 51090942171709440000.0, 1124000727777607680000.0,
1689 25852016738884976640000.0, 620448401733239439360000.0, 15511210043330985984000000.0,
1690 403291461126605635584000000.0, 10888869450418352160768000000.0, 304888344611713860501504000000.0,
1691 8841761993739701954543616000000.0, 265252859812191058636308480000000.0,
1692 8222838654177922817725562880000000.0, 263130836933693530167218012160000000.0
1695 const int npts = (int)size();
1697 const double step = (double) 1.0 / (numPoints - 1);
1700 for (
int i1 = 0; i1 < numPoints; i1++) {
1701 if ((1.0 - t) < 5e-6) {
1704 double x = 0., y = 0., z = 0.;
1705 for (
int i = 0; i < npts; i++) {
1706 const double ti = (i == 0) ? 1.0 : pow(t, i);
1707 const double tni = (npts == i + 1) ? 1.0 : pow(1 - t, npts - i - 1);
1708 const double basis = fac[npts - 1] / (fac[i] * fac[npts - 1 - i]) * ti * tni;
1709 x += basis * at(i).
x();
1710 y += basis * at(i).y();
1711 z += basis * at(i).z();
1716 ret.push_back(current);