Polygon.cpp

#include "Polygon.h"
 
#include <glm/glm.hpp>
#include <glm/gtc/epsilon.hpp> 
 
#include <algorithm>
#include <iterator>
 
namespace Cogs::Geometry {
  enum Location {
    Inside   = -1,
    Outside  = 1
  };
 
  struct Vertex {
    using   List                = std::vector<Vertex>;
    static  constexpr uint32_t  None = 0xFFFFFFFF;
 
            glm::vec3           position;
            bool                intersectionPoint;
 
            Vertex(const glm::vec3& vec, bool intersection = false) : position(vec), intersectionPoint(intersection)
            {
            }
 
            operator glm::vec3() const {
              return position;
            }
  };
 
  bool veryClose(const glm::vec3& lhs, const glm::vec3& rhs) {
    static constexpr glm::vec3  cEpsilon(0.01f, 0.01f, 0.01f);
 
    return glm::all(glm::epsilonEqual(lhs, rhs, cEpsilon));
  }
 
  void removeDuplicates(Vertex::List& vertices) {
    Vertex  prev = vertices.back();
 
    for (uint32_t idx = 0; idx < vertices.size(); ) {
      Vertex  current = vertices[idx];
 
      if (veryClose(prev.position, current.position)) {
        if (current.intersectionPoint) {
          if (idx) {
            vertices.erase(vertices.begin() + (idx - 1));
          }
          else {
            vertices.pop_back();
            ++idx;
          }
          prev = current;
        }
        else {
          vertices.erase(vertices.begin() + idx);
        }
      }
      else {
        prev = current;
        ++idx;
      }
    }
  }
 
  int calcLineSide(const glm::vec3& start, const glm::vec3& end, const glm::vec3& point) {
    float d = ((end.x - start.x) * (point.y - start.y)) - ((end.y - start.y) * (point.x - start.x));
 
    if (d < 0.0f) {
      return -1;
    }
    else if (d > 0.0f) {
      return 1;
    }
    return 0;
  }
 
  uint32_t findMatchingVertex(const glm::vec3& vertex, const Vertex::List& vertices) {
    for (auto i = vertices.begin(), e = vertices.end(); i != e; ++i) {
      if (i->position == vertex) {
        return static_cast<uint32_t>(i - vertices.begin());
      }
    }
    return Vertex::None;
  }
 
  Location getVertexLocation(const Vertex& vertex, const Vertex::List& vertices) {
    glm::vec3 vEnd(vertex.position.x + 1000000.0f, vertex.position.y, 0.0f);
    glm::vec3 start = vertices.back();
    glm::vec3 intersectionpoint;
    int       intersectioncount = 0;
 
    for (auto i = vertices.begin(), e = vertices.end(); i != e; ++i) {
      glm::vec3 end = *i;
 
      if ((vertex.position != start) && (vertex.position != end)) {
        if (start.y > end.y) {
          if ((vertex.position.y >= end.y) && (vertex.position.y < start.y)) {
            intersectioncount += Cogs::Geometry::calcLineLineIntersectionPoint(vertex.position, vEnd, start, end, intersectionpoint);
          }
        }
        else if (start.y < end.y) {
          if ((vertex.position.y >= start.y) && (vertex.position.y < end.y)) {
            intersectioncount += Cogs::Geometry::calcLineLineIntersectionPoint(vertex.position, vEnd, start, end, intersectionpoint);
          }
        }
      }
      start = end;
    }
    return (intersectioncount & 1) ? Location::Inside : Location::Outside;
  }
 
  Location findDivergenceForwards(const Vertex::List& mine, const Vertex::List& theirs, uint32_t myIdx, uint32_t theirIdx, uint32_t& myNextIdx, uint32_t& theirNextIdx) {
    uint32_t  myPointCount = static_cast<uint32_t>(mine.size());
    uint32_t  theirPointCount = static_cast<uint32_t>(theirs.size());
    glm::vec3 myPrevious;
    glm::vec3 myCurrent = mine[myIdx].position;
 
    if (mine[(myIdx + 1) % myPointCount].position == theirs[(theirIdx + 1) % theirPointCount].position) {
      do {
        myPrevious = myCurrent;
 
        myNextIdx = myIdx;
        theirNextIdx = theirIdx;
        myIdx = (myIdx + 1) % myPointCount;
        theirIdx = (theirIdx + 1) % theirPointCount;
 
        myCurrent = mine[myIdx];
      }
      while (myCurrent == theirs[theirIdx].position);
    }
    else if (mine[(myIdx + 1) % myPointCount].position == theirs[std::min(theirIdx - 1, theirPointCount - 1)].position) {
      do {
        myPrevious = myCurrent;
 
        myNextIdx = myIdx;
        theirNextIdx = theirIdx;
        myIdx = (myIdx + 1) % myPointCount;
        theirIdx = std::min(theirIdx - 1, theirPointCount - 1);
 
        myCurrent = mine[myIdx];
      }
      while (myCurrent == theirs[theirIdx].position);
    }
    else {
      myNextIdx = myIdx;
      theirNextIdx = theirIdx;
      myPrevious = myCurrent;
      myCurrent = mine[(myIdx + 1) % myPointCount].position;
    }
 
    float     shortestDist = std::numeric_limits< float >::max();
    glm::vec3 closestPoint;
    glm::vec3 theirPrevious = theirs.back().position;
    glm::vec3 intersectionPoint;
 
    for (theirIdx = 0; theirIdx < theirPointCount; ++theirIdx) {
      glm::vec3 theirCurrent = theirs[theirIdx].position;
 
      if (Cogs::Geometry::calcLineLineIntersectionPoint(myPrevious, myCurrent, theirPrevious, theirCurrent, intersectionPoint)) {
        if ((intersectionPoint != myPrevious) && (intersectionPoint != myCurrent)) {
          float dist = glm::distance(myPrevious, intersectionPoint);
 
          if (dist < shortestDist) {
            shortestDist = dist;
            closestPoint = intersectionPoint;
          }
        }
      }
      theirPrevious = theirCurrent;
    }
 
    glm::vec3 testPoint;
 
    if (shortestDist < std::numeric_limits< float >::max()) {
      testPoint = glm::normalize(closestPoint - myCurrent) * (shortestDist * 0.5f);
    }
    else {
      testPoint = (myCurrent + myPrevious) * 0.5f;
    }
    return getVertexLocation(testPoint, theirs);
  }
 
  bool generateIntersectionPoints(Vertex::List& mine, Vertex::List& theirs) {
    removeDuplicates(mine);
 
    // Adjust the position of any points of theirs that are close to ours...
    for (auto mi = mine.begin(), me = mine.end(); mi != me; ++mi) {
      for (auto ti = theirs.begin(), te = theirs.end(); ti != te; ++ti) {
        if (veryClose(*mi, *ti)) {
          *ti = *mi;
        }
      }
    }
 
    removeDuplicates(theirs);
 
    glm::vec3 myPrevious = mine.back().position;
 
    // Generate new points for any intersections between the two polygons...
    for (uint32_t myIdx = 0, myPointCount = static_cast<uint32_t>(mine.size()); myIdx < myPointCount; ) {
      glm::vec3 myCurrent = mine[myIdx].position;
      glm::vec3 intersectionPoint;
      float     shortestDist = std::numeric_limits< float >::max();
      glm::vec3 closestPoint;
      uint32_t  theirBestIdx = Vertex::None;
      glm::vec3 theirPrevious = theirs.back().position;
      glm::vec3 theirCurrent;
 
      for (uint32_t theirIdx = 0, theirPointCount = static_cast<uint32_t>(theirs.size()); theirIdx < theirPointCount; ++theirIdx) {
        theirCurrent = theirs[theirIdx].position;
 
        if (Cogs::Geometry::calcLineLineIntersectionPoint(myPrevious, myCurrent, theirPrevious, theirCurrent, intersectionPoint)) {
          if ((findMatchingVertex(intersectionPoint, mine) == Vertex::None) || (findMatchingVertex(intersectionPoint, theirs) == Vertex::None)) {
            float dist = glm::distance(myPrevious, intersectionPoint);
 
            if (dist < shortestDist) {
              shortestDist = dist;
              closestPoint = intersectionPoint;
              theirBestIdx = theirIdx;
            }
          }
        }
        theirPrevious = theirCurrent;
      }
      if (theirBestIdx != Vertex::None) {
        uint32_t  match = findMatchingVertex(closestPoint, theirs);
 
        if (match == Vertex::None) {
          theirs.insert(theirs.begin() + theirBestIdx, Vertex(closestPoint, true));
        }
        else {
          theirs[match] = Vertex(closestPoint, true);
        }
 
        match = findMatchingVertex(closestPoint, mine);
        if (match == Vertex::None) {
          mine.insert(mine.begin() + myIdx, Vertex(closestPoint, true));
          myPointCount++;
          myIdx++;
          myPrevious = closestPoint;
          continue;
        }
        else {
          mine[match] = Vertex(closestPoint, true);
        }
      }
      myIdx++;
      myPrevious = myCurrent;
    }
 
    // Remove any duplicates that are now present in our vertices, and
    // clear all intersectionPoint flags from generated points...
    removeDuplicates(mine);
    for (auto mi = mine.begin(), me = mine.end(); mi != me; ++mi) {
      mi->intersectionPoint = false;
    }
 
    // And do the same for their vertices...
    removeDuplicates(theirs);
    for (auto ti = theirs.begin(), te = theirs.end(); ti != te; ++ti) {
      ti->intersectionPoint = false;
    }
 
    uint32_t  myIdx = 0;
    uint32_t  myPointCount = static_cast<uint32_t>(mine.size());
    int       generated = 0;
 
    // Find one of my vertices that is outside the other polygon...
    while ((getVertexLocation(mine[myIdx], theirs) != Location::Outside) || (findMatchingVertex(mine[myIdx], theirs) != Vertex::None)) {
      myIdx = ++myIdx % myPointCount;
 
      if (myIdx == 0) {
        // We've walked through all our vertices and couldn't find
        // one that is completely outside the other polygon.
        return false;
      }
    }
 
    uint32_t  myLastIdx = myIdx;
 
    // This outer loop should only deal with vertices that are outside the other
    // polygon.  When we encounter a vertex that is present on both polygons and
    // our path immediately or eventually enters the other polygon, we will enter
    // the inner loop until we exit the polygon again.
    for (myIdx = ++myIdx % myPointCount; myIdx != myLastIdx; ) {
      uint32_t  theirIdx = findMatchingVertex(mine[myIdx], theirs);
 
      if (theirIdx != Vertex::None) {
        uint32_t  myNextIdx;
        uint32_t  theirNextIdx;
        Location  location = findDivergenceForwards(mine, theirs, myIdx, theirIdx, myNextIdx, theirNextIdx);
 
        if ((myIdx != myNextIdx) || (location == Location::Inside)) {
          if (mine[myIdx].intersectionPoint) {
            return generated;
          }
          mine[myIdx].intersectionPoint = true;
          theirs[theirIdx].intersectionPoint = true;
          generated++;
 
          if (location == Location::Outside) {
            mine[myNextIdx].intersectionPoint = true;
            theirs[theirNextIdx].intersectionPoint = true;
            myIdx = (myNextIdx + 1) % myPointCount;
            generated++;
          }
          else {
            // Now we will loop through our vertices that are inside the other polygon until we break out...
            for (myIdx = (myNextIdx + 1) % myPointCount; ; ) {
              theirIdx = findMatchingVertex(mine[myIdx], theirs);
 
              if (theirIdx != Vertex::None) {
                if (findDivergenceForwards(mine, theirs, myIdx, theirIdx, myNextIdx, theirNextIdx) == Location::Outside) {
                  mine[myNextIdx].intersectionPoint = true;
                  theirs[theirNextIdx].intersectionPoint = true;
                  myIdx = (myNextIdx + 1) % myPointCount;
                  generated++;
                  break;
                }
                myIdx = (myNextIdx + 1) % myPointCount;
              }
              else {
                myIdx = ++myIdx % myPointCount;
              }
            }
          }
        }
        else {
          myIdx = ++myIdx % myPointCount;
        }
      }
      else {
        myIdx = ++myIdx % myPointCount;
      }
    }
    assert(!(generated & 1));
    return generated;
  }
 
  bool findClosestVertices(const Vertex::List& mine, const Vertex::List& theirs, uint32_t& myPoint, uint32_t& theirPoint) {
    float     closestDistance = std::numeric_limits< float >::max();
    uint32_t  theirSize = static_cast<uint32_t>(theirs.size());
 
    myPoint = Vertex::None;
    theirPoint = Vertex::None;
 
    for (uint32_t myIdx = 0, mySize = static_cast<uint32_t>(mine.size()); myIdx < mySize; ++myIdx) {
      glm::vec3 p1 = mine[myIdx].position;
 
      for (uint32_t theirIdx = 0; theirIdx < theirSize; ++theirIdx) {
        float dist = Cogs::Geometry::distanceSqr(p1, theirs[theirIdx].position);
 
        if (dist < closestDistance) {
          myPoint = myIdx;
          theirPoint = theirIdx;
          closestDistance = dist;
        }
      }
    }
    return (myPoint != Vertex::None) && (theirPoint != Vertex::None);
  }
 
  uint32_t findNextIntersection(const Vertex::List& vertices, uint32_t startIdx, bool wrap = true) {
    uint32_t  vertexCount = static_cast<uint32_t>(vertices.size());
    uint32_t  idx = startIdx;
 
    for (uint32_t counter = wrap ? vertexCount : (vertexCount - startIdx - 1); --counter; ) {
      idx = (idx + 1) % vertexCount;
 
      if (vertices[idx].intersectionPoint) {
        assert(idx != startIdx);
        return idx;
      }
    }
    return Vertex::None;
  }
}
 
Cogs::Geometry::Polygon::Polygon(const PointList& initialPoints) {
  setPoints(initialPoints);
}
 
void Cogs::Geometry::Polygon::setPoints(const PointList& pointList) {
  points = pointList;
 
  if (!isClockwise(points)) {
    std::reverse(points.begin(), points.end());
  }
}
 
void Cogs::Geometry::Polygon::addPoint(const glm::vec3& point) {
  points.push_back(point);
}
 
void Cogs::Geometry::Polygon::fixUp() {
  if (!isClockwise(points)) {
    std::reverse(points.begin(), points.end());
  }
 
  glm::vec3 prev = points.back();
  glm::vec3 intersectionPoint;
 
  for (uint32_t outerStartIdx = static_cast<uint32_t>(points.size() - 1), outerEndIdx = 0; outerEndIdx < (points.size() - 1); ) {
    for (uint32_t innerStartIdx = outerEndIdx + 1, innerEndIdx = innerStartIdx + 1; innerEndIdx < (points.size() - 1); ) {
      if (Cogs::Geometry::calcLineLineIntersectionPoint(points[outerStartIdx], points[outerEndIdx], points[innerStartIdx], points[innerEndIdx], intersectionPoint)) {
        points.insert(points.begin() + innerEndIdx++, intersectionPoint);
        points.insert(points.begin() + outerEndIdx, intersectionPoint);
 
        float     inner = calcSignedArea(points.begin() + outerEndIdx, points.begin() + innerEndIdx + 1);
        float     outer = 0.0f;
 
        prev = points[outerEndIdx - 1];
 
        for (uint32_t idx = innerEndIdx; idx != outerEndIdx; idx = (idx + 1) % points.size()) {
          glm::vec3 current = points[idx];
 
          outer += (prev.x * current.y) - (current.x * prev.y);
          prev = current;
        }
        if (inner <= 0.0f) {
          if (outer <= 0.0f) {
            // Both parts are clockwise...  One is inside the other, so we can delete the smaller.
            if (std::fabs(inner) < std::fabs(outer)) {
              points.erase(points.begin() + outerEndIdx, points.begin() + innerEndIdx);
            }
            else {
              points.erase(points.begin() + innerEndIdx, points.end());
              points.erase(points.begin(), points.begin() + outerEndIdx);
            }
          }
          else {
            // The outer part is winding counter clockwise.  We will reverse it and carry on.
            assert(false);
          }
        }
        else if (outer < 0.0f) {
          // The inner part is counter clockwise.  We will reverse it and carry on.
          std::reverse(points.begin() + outerEndIdx, points.begin() + innerEndIdx);
        }
        else {
          assert(false);  // Both sections are counter-clockwise.
        }
        break;
      }
      else {
        innerStartIdx = innerEndIdx++;
        innerEndIdx %= points.size();
      }
    }
    outerStartIdx = outerEndIdx++;
    outerEndIdx %= points.size();
  }
}
 
void Cogs::Geometry::Polygon::clearPoints() {
  points.clear();
}
 
Cogs::Geometry::Polygon::List Cogs::Geometry::Polygon::add(const Polygon& /*polygon*/) const {
  // TODO.  :)
  assert(false);
  return {};
}
 
Cogs::Geometry::Polygon::List Cogs::Geometry::Polygon::subtract(const Polygon& polygon) const {
  if ((points.size() > 2) && ( polygon.points.size() > 2)) {
    Vertex::List  mine;
    Vertex::List  theirs;
    List          outputs;
 
    std::copy(points.begin(), points.end(), std::back_inserter(mine));
    std::copy(polygon.points.begin(), polygon.points.end(), std::back_inserter(theirs));
 
    if (generateIntersectionPoints(mine, theirs)) {
      uint32_t  myStartIdx = mine.front().intersectionPoint ? 0 : findNextIntersection(mine, 0);
      uint32_t  myEndIdx;
      //bool      removedSection = false;
 
      // At this point we have created any additional vertices for all intersection
      // points between the two polygons, and marked any others that existed at
      // intersection points accordingly.
 
      // This first loop attempts to cut out any sections where the polygon to be subtracted
      // intersects this polygon, but does not cut it in two. We do this by finding the next
      // intersection on this polygon after the vertex at index myStartIdx (which is an
      // intersection itself).  We then find the matching vertices on the other polygon
      // (theirStartIdx and theirEndIdx).  Using those four vertices we try to detect that
      // they are orientated the way we expect them to be (the vertex following myStartIdx
      // should be inside them, or the vertex following theirStartIdx should be inside us)
      // and if so, we replace the vertices between myStartIdx and myEndIdx with the vertices
      // from theirEndIdx to theirStartIdx.
      while (myStartIdx != Vertex::None) {
        myEndIdx = findNextIntersection(mine, myStartIdx);
 
        uint32_t  theirStartIdx = findMatchingVertex(mine[myEndIdx], theirs);
        uint32_t  theirEndIdx = findMatchingVertex(mine[myStartIdx], theirs);
 
        if (findNextIntersection(theirs, theirStartIdx) == theirEndIdx) {
          uint32_t  myNextIdx = (myStartIdx + 1) % mine.size();
          uint32_t  theirNextIdx = (theirStartIdx + 1) % theirs.size();
          bool      removable = false;
 
          if (myNextIdx == myEndIdx) {
            if (getVertexLocation(theirs[theirNextIdx].position, mine) == Location::Inside) {
              removable = true;
            }
          }
          else {
            if (getVertexLocation(mine[myNextIdx].position, theirs) == Location::Inside) {
              removable = true;
            }
          }
          if (removable) {
            assert(mine[myStartIdx].intersectionPoint);
            assert(mine[myEndIdx].intersectionPoint);
            mine[myStartIdx].intersectionPoint = false;
            mine[myEndIdx].intersectionPoint = false;
 
            if (myNextIdx < myEndIdx) {
              mine.erase(mine.begin() + myNextIdx, mine.begin() + myEndIdx);
            }
            else if (myNextIdx > myEndIdx) {
              mine.erase(mine.begin() + myNextIdx, mine.end());
              mine.erase(mine.begin(), mine.begin() + myEndIdx);
              myNextIdx = static_cast<uint32_t>(mine.size());
            }
 
            auto  d = mine.begin() + myNextIdx;
 
            if (theirNextIdx < theirEndIdx) {
              for (auto i = theirs.begin() + theirNextIdx, e = theirs.begin() + theirEndIdx; i != e; ++i) {
                assert(!i->intersectionPoint);
                d = mine.insert(d, *i);
              }
            }
            else if (theirNextIdx > theirEndIdx) {
              for (auto i = theirs.begin() + theirNextIdx, e = theirs.end(); i != e; ++i) {
                assert(!i->intersectionPoint);
                d = mine.insert(d, *i);
              }
              for (auto i = theirs.begin(), e = theirs.begin() + theirEndIdx; i != e; ++i) {
                assert(!i->intersectionPoint);
                d = mine.insert(d, *i);
              }
            }
 
            assert(theirs[theirStartIdx].intersectionPoint);
            assert(theirs[theirEndIdx].intersectionPoint);
            theirs[theirStartIdx].intersectionPoint = false;
            theirs[theirEndIdx].intersectionPoint = false;
            //removedSection = true;
          }
        }
        myStartIdx = findNextIntersection(mine, myStartIdx, false);
      }
 
      // Any remaining intersections should cut what remains of this polygon into
      // two or more pieces.
 
      myStartIdx = mine.front().intersectionPoint ? 0 : findNextIntersection(mine, 0);
 
      while (myStartIdx != Vertex::None) {
        myEndIdx = findNextIntersection(mine, myStartIdx);
 
        uint32_t  myNextIdx = (myStartIdx + 1) % mine.size();
        uint32_t  theirStartIdx = findMatchingVertex(mine[myStartIdx].position, theirs);
        uint32_t  theirEndIdx = findMatchingVertex(mine[myEndIdx].position, theirs);
        uint32_t  theirNextIdx = (theirStartIdx + 1) % theirs.size();
 
        if (findNextIntersection(theirs, theirStartIdx) == theirEndIdx) {
          bool  extractable = false;
 
          if (myNextIdx == myEndIdx) {
            if (getVertexLocation(theirs[theirNextIdx].position, mine) == Location::Inside) {
              extractable = true;
            }
          }
          else {
            if (getVertexLocation(mine[myNextIdx].position, theirs) == Location::Outside) {
              extractable = true;
            }
          }
          if (extractable) {
            Polygon& dest = outputs.emplace_back();
 
            if (myEndIdx < myStartIdx) {
              dest.points.insert(dest.points.end(), mine.begin() + myStartIdx, mine.end());
              dest.points.insert(dest.points.end(), mine.begin(), mine.begin() + myEndIdx + 1);
            }
            else {
              dest.points.insert(dest.points.end(), mine.begin() + myStartIdx, mine.begin() + myEndIdx + 1);
            }
 
            if (theirStartIdx < theirEndIdx) {
              std::reverse_copy(theirs.begin() + theirStartIdx + 1, theirs.begin() + theirEndIdx, std::back_inserter(dest.points));
            }
            else {
              std::reverse_copy(theirs.begin(), theirs.begin() + theirEndIdx, std::back_inserter(dest.points));
              std::reverse_copy(theirs.begin() + theirStartIdx + 1, theirs.end(), std::back_inserter(dest.points));
            }
            assert(mine[myStartIdx].intersectionPoint);
            assert(mine[myEndIdx].intersectionPoint);
            mine[myStartIdx].intersectionPoint = false;
            mine[myEndIdx].intersectionPoint = false;
 
            assert(theirs[theirStartIdx].intersectionPoint);
            assert(theirs[theirEndIdx].intersectionPoint);
            theirs[theirStartIdx].intersectionPoint = false;
            theirs[theirEndIdx].intersectionPoint = false;
 
            myEndIdx = findNextIntersection(mine, myEndIdx);
 
            if (myEndIdx != Vertex::None) {
              assert(myEndIdx != myStartIdx);
 
              uint32_t  theirFollowUpIdx = findMatchingVertex(mine[myEndIdx].position, theirs);
              uint32_t  theirPreviousIdx = findNextIntersection(theirs, theirFollowUpIdx);
 
              if (findNextIntersection(theirs, theirPreviousIdx) == theirFollowUpIdx) {
                myStartIdx = findMatchingVertex(theirs[theirPreviousIdx].position, mine);
                myNextIdx = (myStartIdx + 1) % mine.size();
 
                assert(mine[myStartIdx].intersectionPoint);
                assert(mine[myEndIdx].intersectionPoint);
                mine[myStartIdx].intersectionPoint = false;
                mine[myEndIdx].intersectionPoint = false;
 
                if (myNextIdx < myEndIdx) {
                  mine.erase(mine.begin() + myNextIdx, mine.begin() + myEndIdx);
                }
                else if (myNextIdx > myEndIdx) {
                  mine.erase(mine.begin() + myNextIdx, mine.end());
                  mine.erase(mine.begin(), mine.begin() + myEndIdx);
                }
 
                theirNextIdx = (theirFollowUpIdx + 1) % theirs.size();
 
                auto  d = mine.begin() + myNextIdx;
 
                if (theirNextIdx <= theirPreviousIdx) {
                  for (auto i = theirs.begin() + theirNextIdx, e = theirs.begin() + theirPreviousIdx; i != e; ++i) {
                    assert(!i->intersectionPoint);
                    d = mine.insert(d, *i);
                  }
                }
                else {
                  for (auto i = theirs.begin() + theirNextIdx, e = theirs.end(); i != e; ++i) {
                    assert(!i->intersectionPoint);
                    d = mine.insert(d, *i);
                  }
                  for (auto i = theirs.begin(), e = theirs.begin() + theirPreviousIdx; i != e; ++i) {
                    assert(!i->intersectionPoint);
                    d = mine.insert(d, *i);
                  }
                }
                assert(theirs[theirFollowUpIdx].intersectionPoint);
                assert(theirs[theirPreviousIdx].intersectionPoint);
                theirs[theirFollowUpIdx].intersectionPoint = false;
                theirs[theirPreviousIdx].intersectionPoint = false;
              }
            }
          }
        }
        myStartIdx = findNextIntersection(mine, myStartIdx);
      }
      // No more intersections could be found.  Insert whatever remains
      // in 'mine' into the output as a new polygon.
      Polygon&  dest = outputs.emplace_back();
 
      dest.points.insert(dest.points.end(), mine.begin(), mine.end());
    }
    else if (isPointInside(polygon.points[0])) {
      // The given polygon is completely enclosed within this one.
      // We will create a new polygon with a hole in the middle.
      uint32_t  myIdx;
      uint32_t  theirIdx;
      Polygon&  dest = outputs.emplace_back();
 
      findClosestVertices(mine, theirs, myIdx, theirIdx);
 
      dest.points.insert(dest.points.end(), mine.begin(), mine.begin() + myIdx + 1);
      std::reverse_copy(theirs.begin(), theirs.begin() + theirIdx + 1, std::back_inserter(dest.points));
      std::reverse_copy(theirs.begin() + theirIdx, theirs.end(), std::back_inserter(dest.points));
      dest.points.insert(dest.points.end(), mine.begin() + myIdx, mine.end());
    }
    else if (!polygon.isPointInside(points[0])) {
      // The other polygon does not intersect this one in anyway.
      // Return a copy of ourself unchanged.
      return {*this};
    }
    return outputs;
  }
  return {*this};
}
 
bool Cogs::Geometry::Polygon::isClockwise(const PointList& pointList) {
  return calcSignedArea(pointList.begin(), pointList.end()) < 0.0f;
}
 
bool Cogs::Geometry::Polygon::isPointInside(const glm::vec3& p, const PointList& pointList) {
  if (pointList.size() > 2) {
    glm::vec3 pEnd = p + glm::vec3(1000000.0f, 0.0, 0.0f);
    glm::vec3 start = pointList.back();
    glm::vec3 intersectionpoint;
    int       intersectioncount = 0;
 
    for (auto i = pointList.begin(), e = pointList.end(); i != e; ++i) {
      glm::vec3 end = *i;
 
      if (start.y > end.y) {
        if ((p.y >= end.y) && (p.y <= start.y)) {
          intersectioncount += calcLineLineIntersectionPoint(p, pEnd, start, end, intersectionpoint);
        }
      }
      else if (start.y < end.y) {
        if ((p.y >= start.y) && (p.y <= end.y)) {
          intersectioncount += calcLineLineIntersectionPoint(p, pEnd, start, end, intersectionpoint);
        }
      }
      start = end;
    }
    if (intersectioncount & 1) {
      return true;
    }
  }
  return false;
}
 
float Cogs::Geometry::Polygon::calcSignedArea(const PointList::const_iterator& start, const PointList::const_iterator& end) {
  float area = 0.0f;
 
  if ((end - start) > 2) {
    glm::vec3 prev = *(end - 1);
 
    for (auto i = start; i != end; ++i) {
      glm::vec3 current = *i;
 
      area += (prev.x * current.y) - (current.x * prev.y);
      prev = current;
    }
  }
  return area * 0.5f;
}