examples/hull.cpp

 
#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <utility>
#include <vector>
#include "Board.h"
#include "board/Tools.h"
using namespace LibBoard;
 
bool isSeparing(Point & a, Point & b, const std::vector<Point> & points)
{
  int sign = 0;
  Point v1 = b - a;
  for (Point p : points) {
    if (p != a && p != b) {
      Point v2 = p - a;
      double wp = v1.x * v2.y - v1.y * v2.x;
      if (std::abs(wp) < 1e-8) {
        if ((a - p) * (b - p) < 0.0) {
          // a, p and b are aligned (in that order)
          return true;
        }
      }
      if ((sign > 0 && wp < 0.0) || (sign < 0 && wp > 0.0)) {
        return true;
      }
      sign = (wp > 0.0) ? 1 : -1;
    }
  }
  if (sign == -1) {
    std::swap(a, b);
  }
  return false;
}
 
int main(int, char *[])
{
  Board board;
 
  Style::setDefaultLineWidth(0.5);
  Style::setDefaultPenColor(Color::Blue);
  Style::setDefaultFillColor(Color::Null);
 
  std::vector<Point> points;
  int n = 25;
  while (n--) {
    points.push_back(Point(4 * (Tools::boardRand() % 50), 4 * (Tools::boardRand() % 50)));
  }
 
  typedef std::pair<Point, Point> Segment;
  std::vector<Segment> segments;
 
  // Compute the set of separating segments
  for (size_t a = 0; a < points.size(); ++a) {
    for (size_t b = a + 1; b < points.size(); ++b) {
      Point pa = points[a];
      Point pb = points[b];
      if (!isSeparing(pa, pb, points)) {
        segments.push_back(Segment(pa, pb));
        // board << Line(pa, pb, Color::Red, 0.1);
      }
    }
  }
 
  // Build a polyline using the set of segments
  Segment segment = segments.front();
  std::vector<Point> polyline;
  const Point stop = segment.first;
  do {
    polyline.push_back(segment.first);
    for (const Segment & s : segments) {
      if (s.first == segment.second) {
        segment = s;
        break;
      }
    }
  } while (segment.first != stop);
 
  board << Polyline(polyline, Path::ClosedPath, Color::Cyan, Color("#a0a0c0"), 0.5);
 
  for (Point p : points) {
    board << Dot(p.x, p.y, Color::Blue, 1.0);
  }
 
  board.saveSVG("hull.svg");
}