432{
433 auto points_are_close = [](
const Point &a,
const Point &b,
double dist2) {
434 const double dx = double(a.x() - b.x()), dy = double(a.y() - b.y());
435 return dx * dx + dy * dy <= dist2;
436 };
437 auto distance_from_line2 = [](
const Point &pt,
const Point &ln1,
const Point &ln2) {
438 const double A = double(ln1.y() - ln2.y());
439 const double B = double(ln2.x() - ln1.x());
440 const double C = A * pt.x() + B * pt.y() - (A * ln1.x() + B * ln1.y());
441 return (C * C) / (A * A + B * B);
442 };
443 auto slopes_near_collinear = [&distance_from_line2](
const Point &pt1,
const Point &pt2,
const Point &pt3,
double dist2) {
444 if (std::abs(pt1.x() - pt2.x()) > std::abs(pt1.y() - pt2.y())) {
445 if ((pt1.x() > pt2.x()) == (pt1.x() < pt3.x()))
446 return distance_from_line2(pt1, pt2, pt3) < dist2;
447 if ((pt2.x() > pt1.x()) == (pt2.x() < pt3.x()))
448 return distance_from_line2(pt2, pt1, pt3) < dist2;
449 return distance_from_line2(pt3, pt1, pt2) < dist2;
450 }
451 if ((pt1.y() > pt2.y()) == (pt1.y() < pt3.y()))
452 return distance_from_line2(pt1, pt2, pt3) < dist2;
453 if ((pt2.y() > pt1.y()) == (pt2.y() < pt3.y()))
454 return distance_from_line2(pt2, pt1, pt3) < dist2;
455 return distance_from_line2(pt3, pt1, pt2) < dist2;
456 };
457
458 size_t size = points.size();
459 if (size == 0)
460 return;
461 std::vector<size_t> next(size), prev(size);
462 std::vector<char> done(size, 0);
463 for (size_t i = 0; i < size; ++i) {
464 next[i] = (i + 1) % size;
465 prev[next[i]] = i;
466 }
467 auto exclude = [&next, &prev, &done](size_t op) {
468 const size_t result = prev[op];
469 next[result] = next[op];
470 prev[next[op]] = result;
471 done[result] = 0;
472 return result;
473 };
475 size_t op = 0;
476 while (! done[op] && next[op] != prev[op]) {
477 if (points_are_close(points[op], points[prev[op]], dist2)) {
478 op = exclude(op);
479 -- size;
480 } else if (points_are_close(points[prev[op]], points[next[op]], dist2)) {
481 exclude(next[op]);
482 op = exclude(op);
483 size -= 2;
484 } else if (slopes_near_collinear(points[prev[op]], points[op], points[next[op]], dist2)) {
485 op = exclude(op);
486 -- size;
487 } else {
488 done[op] = 1;
489 op = next[op];
490 }
491 }
492 if (size < 3)
493 size = 0;
495 out.reserve(size);
496 for (size_t i = 0; i < size; ++i) {
497 out.emplace_back(points[op]);
498 op = next[op];
499 }
500 points = std::move(out);
501}
float distance(SpiralVase::SpiralPoint a, SpiralVase::SpiralPoint b)
Definition SpiralVase.cpp:19
std::vector< Point, PointsAllocator< Point > > Points
Definition Point.hpp:73
1.15.0