GmMultiPolyIntersectionSorterTerse.cpp

Go to the documentation of this file.

//------------------------------------------------------------------------------
//------------------------------------------------------------------------------

//----- Included files ---------------------------------------------------------

// 1. Precompiled header

// 2. My header
#include <xmsgrid/geometry/GmMultiPolyIntersectionSorterTerse.h>

// 3. Standard Library Headers
#include <cfloat>

// 4. External Library Headers
#include <xmscore/math/math.h>                             // EQ_EPS
#include <xmscore/misc/XmError.h>                          // XM_*
#include <xmscore/misc/xmstype.h>                          // XM_NONE
#include <xmscore/stl/set.h>                               // Set*
#include <xmscore/stl/vector.h>                            // Vec*
#include <xmsgrid/geometry/GmMultiPolyIntersectorData.h> // GmMultiPolyIntersectorData
#include <xmsgrid/geometry/geoms.h> // gmComputeCentroid, gmTurn

// 5. Shared Headers

// 6. Non-shared Headers

//----- Forward declarations ---------------------------------------------------

//----- External globals -------------------------------------------------------

//----- Namespace declaration --------------------------------------------------

namespace xms {
//----- Constants / Enumerations -----------------------------------------------

//----- Classes / Structs ------------------------------------------------------

namespace { // unnamed namespace
} // unnamed namespace

//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
void GmMultiPolyIntersectionSorterTerse::Sort(
    GmMultiPolyIntersectorData &a_data, std::vector<int> &polyids,
    std::vector<double> &tvalues, std::vector<Pt3d> &a_pts, double a_tol)
{
  m_d = &a_data;
  m_tol = a_tol;

  RemoveCornerTouches();
  RemoveDuplicateEdges();
  SwapAdjacents();
  IntersectionsToPolyIdsAndTValues(polyids, tvalues, a_pts);
  FixArrays(polyids, tvalues, a_pts);
} // GmMultiPolyIntersectionSorterTerse::Sort
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
void GmMultiPolyIntersectionSorterTerse::FixTValueAtDuplicateXy()
{
  XM_ENSURE_TRUE_VOID_NO_ASSERT(m_d->m_ixs.size() > 1);

  // Loop through
  for (size_t i = 1; i < m_d->m_ixs.size() - 1; ++i)
  {
    if (gmEqualPointsXY(m_d->m_ixs[i].m_pt, m_d->m_ixs[i - 1].m_pt, gmXyTol()))
    {
      m_d->m_ixs[i].m_t =  m_d->m_ixs[i - 1].m_t;
    }
  }

  // Try to get 1.0 t-values as far down as possible.
  for (size_t i = m_d->m_ixs.size() - 2; i > 0; --i)
  {
    if (gmEqualPointsXY(m_d->m_ixs[i].m_pt, m_d->m_ixs[i + 1].m_pt, gmXyTol()))
    {
      m_d->m_ixs[i].m_t =  m_d->m_ixs[i + 1].m_t;
    }
    else
    {
      break;
    }
  }
} // GmMultiPolyIntersectionSorterTerse::FixTValueAtDuplicateXy
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
void GmMultiPolyIntersectionSorterTerse::RemoveCornerTouches()
{
  XM_ENSURE_TRUE_VOID_NO_ASSERT(m_d->m_ixs.size() > 1);

  // Change the t-values so that duplicate points in XY have the same t-value.
  VecDbl oldTValues;
  oldTValues.reserve(m_d->m_ixs.size());
  for (size_t i = 0; i < m_d->m_ixs.size(); ++i)
  {
    oldTValues.push_back(m_d->m_ixs[i].m_t);
  }
  FixTValueAtDuplicateXy();

  VecInt tChange;
  FindWhereTValuesChange(tChange);

  VecInt toRemove;

  // Loop through tChanges
  for (size_t i = 0; i < tChange.size() - 1; ++i)
  {
    if (tChange[i + 1] - tChange[i] > 1)
    {
      VecInt inNeither;
      FindPreviousNextNeither(tChange, (int)i, nullptr, nullptr, &inNeither);

      if ((i > 0 && i + 2 < tChange.size()) || inNeither.size() > 1 ||
          (i == 0 && tChange[1] - tChange[0] > 1))
      {
        toRemove.insert(toRemove.end(), inNeither.begin(), inNeither.end());
      }
    }
  }

  AddMissingEndpointIds(tChange);

  // Reset the t-values
  for (size_t i = 0; i < m_d->m_ixs.size(); ++i)
  {
    m_d->m_ixs[i].m_t = oldTValues[i];
  }

  // Remove them, working backwards
  for (size_t i = toRemove.size(); i-- > 0;)
  {
    m_d->m_ixs.erase(m_d->m_ixs.begin() + toRemove[i]);
  }
} // GmMultiPolyIntersectionSorterTerse::RemoveCornerTouches
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
void GmMultiPolyIntersectionSorterTerse::RemoveDuplicateEdges() {
  XM_ENSURE_TRUE_VOID_NO_ASSERT(m_d->m_ixs.size() > 1);

  VecInt tChange;
  FindWhereTValuesChange(tChange);

  VecInt toRemove;

  // Loop through tChanges
  for (size_t i = 0; i < tChange.size() - 1; ++i) {
    if (tChange[i + 1] - tChange[i] > 1) {
      VecInt inNext;
      // Get intersections in this tvalue group that also appear in next group.
      // These are the first points of the edges.
      FindPreviousNextNeither(tChange, (int)i, nullptr, &inNext, nullptr);

      if (inNext.size() > 1) {
        // Get intersections in next tvalue group that match those in current.
        // These are the last points of the edges.
        VecInt inPrev;
        FindPreviousNextNeither(tChange, (int)i + 1, &inPrev, nullptr, nullptr);
        // XM_ASSERT(inPrev.size() == inNext.size());
        // Not sure why the assert above was put in. Even when it asserts,
        // we still seem to get good results in the end.

        // Keep only the polygons that are on the right of the line
        bool found = false; // Should be just 2 so stop if we find one
        for (size_t j = 0; j < inNext.size() && !found; ++j) {
          // Find the other end of this edge
          int edgeBeg = inNext[j]; // index into m_d->m_ixs of beginning of edge
          int edgeEnd = XM_NONE;   // index into m_d->m_ixs of end of edge
          for (size_t k = 0; k < inPrev.size() && edgeEnd == XM_NONE; ++k) {
            if (m_d->m_ixs[inPrev[k]].m_i == m_d->m_ixs[edgeBeg].m_i)
              edgeEnd = inPrev[k];
          }
          XM_ASSERT(edgeEnd != XM_NONE);

          int polyIdx = m_d->m_ixs[edgeBeg].m_i - 1;
          // Create the poly as a vector of Pt3ds for gmComputeCentroid
          VecPt3d poly;
          for (size_t k = 0; k < m_d->m_polys[polyIdx].size(); ++k) {
            poly.push_back(m_d->m_points[m_d->m_polys[polyIdx][k]]);
          }
          Pt3d centroid = gmComputeCentroid(poly);
          Turn_enum turn = gmTurn(m_d->m_ixs[edgeBeg].m_pt,
                                  m_d->m_ixs[edgeEnd].m_pt, centroid);
          if (turn != TURN_RIGHT) {
            toRemove.push_back(edgeBeg);
            toRemove.push_back(edgeEnd);
            found = true;
          }
        }
      }
    }
  }

  // Remove them, working backwards
  std::sort(toRemove.begin(), toRemove.end());
  for (size_t i = toRemove.size(); i-- > 0;) {
    m_d->m_ixs.erase(m_d->m_ixs.begin() + toRemove[i]);
  }
} // GmMultiPolyIntersectionSorterTerse::RemoveDuplicateEdges
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
void GmMultiPolyIntersectionSorterTerse::SwapAdjacents() {
  XM_ENSURE_TRUE_VOID_NO_ASSERT(m_d->m_ixs.size() > 1);

  // 2 intersections
  if (m_d->m_ixs.size() == 2) {
    if ((!m_d->m_polys1.empty() &&
         m_d->m_polys1.find(m_d->m_ixs[0].m_i) == m_d->m_polys1.end()) ||
        (!m_d->m_polys2.empty() &&
         m_d->m_polys2.find(m_d->m_ixs[1].m_i) == m_d->m_polys2.end())) {
      Swap(0, 1);
    }
    return;
  }

  // 3 or more intersections
  int i = 1;
  // Do first one outside of loop
  if (EQ_EPS(m_d->m_ixs[1].m_t, m_d->m_ixs[0].m_t, FLT_EPSILON) &&
      (m_d->m_ixs[0].m_i == m_d->m_ixs[2].m_i ||
       (m_d->m_ixs.size() > 3 && m_d->m_ixs[0].m_i == m_d->m_ixs[3].m_i))) {
    Swap(0, 1);
    ++i;
  }

  for (; i < (int)m_d->m_ixs.size(); ++i) {
    if (EQ_EPS(m_d->m_ixs[i].m_t, m_d->m_ixs[i - 1].m_t, FLT_EPSILON)) {
      // look back
      if (i - 2 >= 0 && m_d->m_ixs[i].m_i == m_d->m_ixs[i - 2].m_i) {
        Swap(i, i - 1);
      }
    }
  }
} // GmMultiPolyIntersectionSorterTerse::SwapAdjacents
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
void GmMultiPolyIntersectionSorterTerse::AddMissingEndpointIds(const VecInt& a_tChange)
{
  XM_ENSURE_TRUE_NO_ASSERT(a_tChange.size() >= 2);
  XM_ENSURE_TRUE_NO_ASSERT(!m_d->m_ixs.empty());

  // make sure all starting point polygons are included
  if (m_d->m_ixs[0].m_t == 0.0)
  {
    int begin = a_tChange[0];
    int end = a_tChange[1];
    for (int i = begin; i < end; ++i)
    {
      m_d->m_polys1.insert(m_d->m_ixs[i].m_i);
    }
  }

  // make sure all ending point polygons are included
  if (m_d->m_ixs.back().m_t == 1.0)
  {
    int begin = a_tChange[a_tChange.size() - 2];
    int end = a_tChange.back();
    for (int i = begin; i < end; ++i)
    {
      m_d->m_polys2.insert(m_d->m_ixs[i].m_i);
    }
  }
} // GmMultiPolyIntersectionSorterTerse::AddMissingEndpointIds
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
void GmMultiPolyIntersectionSorterTerse::IntersectionsToPolyIdsAndTValuesFor2(
    VecInt &polyids, VecDbl &tvalues, std::vector<Pt3d> &a_pts) const {
  if (m_d->m_ixs.size() == 2) {
    if (EQ_EPS(m_d->m_ixs[0].m_t, m_d->m_ixs[1].m_t, FLT_EPSILON)) {
      if (!m_d->m_polys1.empty() && !m_d->m_polys2.empty() &&
          m_d->m_polys1 != m_d->m_polys2) {
        // test2InIn. Combine 2 into 1 getting entrance into second poly
        if (m_d->m_polys1.find(m_d->m_ixs[0].m_i) != m_d->m_polys1.end()) {
          AddToPolyIdsAndTValues(m_d->m_ixs[1], polyids, tvalues, a_pts);
        } else {
          AddToPolyIdsAndTValues(m_d->m_ixs[0], polyids, tvalues, a_pts);
        }
      } else {
        AddToPolyIdsAndTValues(m_d->m_ixs[0], polyids, tvalues, a_pts);
        AddToPolyIdsAndTValues(m_d->m_ixs[1], polyids, tvalues, a_pts);
      }
    } else {
      AddToPolyIdsAndTValues(m_d->m_ixs[0], polyids, tvalues, a_pts);
      AddToPolyIdsAndTValues(m_d->m_ixs[1], polyids, tvalues, a_pts);
    }
    return;
  }
} // GmMultiPolyIntersectionSorterTerse::IntersectionsToPolyIdsAndTValuesFor2
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
void GmMultiPolyIntersectionSorterTerse::
    IntersectionsToPolyIdsAndTValuesFor3OrMore(VecInt &polyids, VecDbl &tvalues,
                                               std::vector<Pt3d> &a_pts) const {
  XM_ENSURE_TRUE_VOID_NO_ASSERT(m_d->m_ixs.size() > 1);

  // Mark where we have a change in t values
  VecInt tChange;
  FindWhereTValuesChange(tChange);

  SetInt setIds, setIdsPrev; // ids we're adding now, & that we added previously
  // Loop through tChanges
  for (int i = 0; i < (int)tChange.size() - 1; ++i) {
    if (tChange[i + 1] - tChange[i] > 1) {
      VecInt inPrev, inNext, inNeither;
      FindPreviousNextNeither(tChange, i, &inPrev, &inNext, &inNeither);

      if (i == 0) {
        // If we don't have any in "inNeither", use next as inNeither.
        if (inPrev.empty() && inNeither.empty())
          inNeither = inNext;

        // Take the ones that are not found
        for (size_t j = 0; j < inNeither.size(); ++j) {
          setIds.insert(m_d->m_ixs[inNeither[j]].m_i);
          AddToPolyIdsAndTValues(m_d->m_ixs[inNeither[j]], polyids, tvalues,
                                 a_pts);
        }
      } else {
        // Take the ones that were found in the previous group, that were
        // not added previously
        for (size_t j = 0; j < inPrev.size(); ++j) {
          if (setIdsPrev.find(m_d->m_ixs[inPrev[j]].m_i) == setIdsPrev.end()) {
            setIds.insert(m_d->m_ixs[inPrev[j]].m_i);
            AddToPolyIdsAndTValues(m_d->m_ixs[inPrev[j]], polyids, tvalues,
                                   a_pts);
          }
        }

        if (setIds.empty()) {
          // Since we haven't added any yet, add those from next that weren't
          // added previously
          for (size_t j = 0; j < inNext.size(); ++j) {
            if (setIdsPrev.find(m_d->m_ixs[inNext[j]].m_i) ==
                setIdsPrev.end()) {
              setIds.insert(m_d->m_ixs[inNext[j]].m_i);
              AddToPolyIdsAndTValues(m_d->m_ixs[inNext[j]], polyids, tvalues,
                                     a_pts);
            }
          }
        }

        // Then take the ones that were not found
        for (size_t j = 0; j < inNeither.size(); ++j) {
          setIds.insert(m_d->m_ixs[inNeither[j]].m_i);
          AddToPolyIdsAndTValues(m_d->m_ixs[inNeither[j]], polyids, tvalues,
                                 a_pts);
        }

        if (setIds.empty()) {
          // Since we haven't added any yet, add those from previous group
          for (size_t j = 0; j < inPrev.size(); ++j) {
            setIds.insert(m_d->m_ixs[inPrev[j]].m_i);
            AddToPolyIdsAndTValues(m_d->m_ixs[inPrev[j]], polyids, tvalues,
                                   a_pts);
          }
        }
      }
    } else {
      setIds.insert(m_d->m_ixs[tChange[i]].m_i);
      AddToPolyIdsAndTValues(m_d->m_ixs[tChange[i]], polyids, tvalues, a_pts);
    }

    setIdsPrev = setIds;
    setIds.clear();
  }

} // IntersectionsToPolyIdsAndTValuesFor3OrMore
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
void GmMultiPolyIntersectionSorterTerse::IntersectionsToPolyIdsAndTValues(
    VecInt &polyids, VecDbl &tvalues, std::vector<Pt3d> &a_pts) const {
  polyids.clear();
  tvalues.clear();
  a_pts.clear();

  XM_ENSURE_TRUE_VOID_NO_ASSERT(!m_d->m_ixs.empty());

  // 1 intersection
  if (m_d->m_ixs.size() == 1) {
    polyids.push_back(m_d->m_ixs[0].m_i);
    tvalues.push_back(m_d->m_ixs[0].m_t);
    a_pts.push_back(m_d->m_ixs[0].m_pt);
    return;
  }

  // 2 intersections
  if (m_d->m_ixs.size() == 2) {
    IntersectionsToPolyIdsAndTValuesFor2(polyids, tvalues, a_pts);
    return;
  }

  // 3 or more intersections
  IntersectionsToPolyIdsAndTValuesFor3OrMore(polyids, tvalues, a_pts);

} // GmMultiPolyIntersectionSorterTerse::IntersectionsToPolyIdsAndTValues
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
void GmMultiPolyIntersectionSorterTerse::FixArrays(VecInt &polyids,
                                                   VecDbl &tvalues,
                                                   VecPt3d &a_pts) const {
  XM_ENSURE_TRUE_VOID_NO_ASSERT(!polyids.empty());

  // Make sure we have at least two values - an entrance and exit
  if (polyids.size() == 1) {
    // Only one intersection. Add an exit that is the same
    polyids.push_back(polyids.back());
    tvalues.push_back(tvalues.back());
    a_pts.push_back(a_pts.back());
  }

  // If crossing a vertex, make sure we have an exit
  if (m_d->m_polys2.empty() && polyids.back() != polyids[polyids.size() - 2]) {
    polyids.push_back(polyids.back());
    tvalues.push_back(tvalues.back());
    a_pts.push_back(a_pts.back());
  }

  // Make sure we always end with -1
  if (polyids.size() > 1) {
    polyids.back() = -1;
  }

  // If we leave and reenter, set exit to -1
  for (size_t i = 1; i < polyids.size(); ++i) {
    if (polyids[i] == polyids[i - 1]) {
      polyids[i] = -1;
    }
  }

} // GmMultiPolyIntersectionSorterTerse::FixArrays
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
void GmMultiPolyIntersectionSorterTerse::AddToPolyIdsAndTValues(
    const ix &a_ix, VecInt &polyids, VecDbl &tvalues,
    std::vector<Pt3d> &a_pts) const {
  polyids.push_back(a_ix.m_i);
  tvalues.push_back(a_ix.m_t);
  a_pts.push_back(a_ix.m_pt);
} // GmMultiPolyIntersectionSorterTerse::AddToPolyIdsAndTValues
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
void GmMultiPolyIntersectionSorterTerse::FindPreviousNextNeither(
    const VecInt &tChange, const int idx, VecInt *inPrev, VecInt *inNext,
    VecInt *inNeither) const {
  if (inPrev)
    inPrev->clear();
  if (inNext)
    inNext->clear();
  if (inNeither)
    inNeither->clear();
  for (int j = tChange[idx]; j < tChange[idx + 1]; ++j) {
    // Corners at the start of the list of intersections appear the same
    // as edges so we can't remove them because we don't have a previous
    // set of tvalues to look at.
    bool foundPrev = false;
    if (idx > 0) {
      for (int k = tChange[idx - 1]; k < tChange[idx] && !foundPrev; ++k) {
        if (m_d->m_ixs[j].m_i == m_d->m_ixs[k].m_i) {
          foundPrev = true;
        }
      }
    }

    // Corners at the end of the list of intersections appear the same
    // as edges so we can't remove them because we don't have a inNext set
    // of tvalues to look at.
    bool foundNext = false;
    if (!foundPrev && idx + 2 < (int)tChange.size()) {
      for (int k = tChange[idx + 1]; k < (int)tChange[idx + 2] && !foundNext;
           ++k) {
        if (m_d->m_ixs[j].m_i == m_d->m_ixs[k].m_i) {
          foundNext = true;
        }
      }
    }

    if (foundPrev) {
      if (inPrev)
        inPrev->push_back(j);
    } else if (foundNext) {
      if (inNext)
        inNext->push_back(j);
    } else {
      if (inNeither)
        inNeither->push_back(j);
    }
  }
} // GmMultiPolyIntersectionSorterTerse::FindPreviousNextNeither
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
void GmMultiPolyIntersectionSorterTerse::Swap(int a, int b) {
  ix temp = m_d->m_ixs[a];
  m_d->m_ixs[a] = m_d->m_ixs[b];
  m_d->m_ixs[b] = temp;
} // GmMultiPolyIntersectionSorterTerse::Swap
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
void GmMultiPolyIntersectionSorterTerse::FindWhereTValuesChange(
    VecInt &tChange) const {
  tChange.assign(1, 0);
  for (size_t i = 1; i < m_d->m_ixs.size(); ++i) {
    if (!EQ_TOL(m_d->m_ixs[i].m_t, m_d->m_ixs[i - 1].m_t, m_tol)) {
      tChange.push_back((int)i);
    }
  }
  tChange.push_back((int)m_d->m_ixs.size()); // for convenience
} // GmMultiPolyIntersectionSorterTerse::FindWhereTValuesChange

} // namespace xms