Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#include "tcenterlinevectP.h"
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//==========================================================================
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//*********************************
Toshihiro Shimizu 890ddd
//    Skeleton re-organization
Toshihiro Shimizu 890ddd
//*********************************
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//==========================================================================
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//----------------------------------------
Toshihiro Shimizu 890ddd
//    Skeleton re-organization Globals
Toshihiro Shimizu 890ddd
//----------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
namespace {
Toshihiro Shimizu 890ddd
VectorizerCoreGlobals *globals;
Toshihiro Shimizu 890ddd
std::vector<unsigned int=""> contourFamilyOfOrganized;</unsigned>
Toshihiro Shimizu 890ddd
JointSequenceGraph *currJSGraph;
Toshihiro Shimizu 890ddd
ContourFamily *currContourFamily;
Toshihiro Shimizu 890ddd
};
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//==========================================================================
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------
Toshihiro Shimizu 890ddd
//      Skeleton re-organization
Toshihiro Shimizu 890ddd
//--------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// EXPLANATION:  The raw skeleton data obtained from StraightSkeletonizer
Shinya Kitaoka 120a6e
// class need to be grouped in joints and sequences before proceding with
Shinya Kitaoka 120a6e
// conversion in quadratics - which works on single sequences.
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// NOTE: Due to maxHeight, we have to assume that a single SkeletonGraph can
Shinya Kitaoka 120a6e
// hold
Shinya Kitaoka 120a6e
// more connected graphs at once.
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// a) Isolate graph-like part of skeleton
Shinya Kitaoka 120a6e
// b) Retrieve remaining single sequences.
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
typedef std::map<uint, std::less<uint="" uint,="">> uintMap;</uint,>
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// void organizeGraphs(SkeletonList* skeleton)
Shinya Kitaoka 120a6e
void organizeGraphs(SkeletonList *skeleton, VectorizerCoreGlobals &g) {
Shinya Kitaoka 120a6e
  globals = &g;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  SkeletonList::iterator currGraphPtr;
Shinya Kitaoka 120a6e
  Sequence currSequence;
Shinya Kitaoka 120a6e
  uintMap jointsMap;
Shinya Kitaoka 120a6e
  UINT i, j;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  UINT counter = 0;  // We also count current graph number, to associate
Shinya Kitaoka 120a6e
  // organized graphs to their contour family
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  contourFamilyOfOrganized.clear();
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  for (currGraphPtr = skeleton->begin(); currGraphPtr != skeleton->end();
Shinya Kitaoka 120a6e
       ++currGraphPtr) {
Shinya Kitaoka 120a6e
    SkeletonGraph &currGraph   = **currGraphPtr;
Shinya Kitaoka 120a6e
    currSequence.m_graphHolder = &currGraph;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Separate single Points - can happen only when a single node gets stored
Shinya Kitaoka 120a6e
    // in a SkeletonGraph.
Shinya Kitaoka 120a6e
    if (currGraph.getNodesCount() == 1) {
Shinya Kitaoka 120a6e
      globals->singlePoints.push_back(*currGraph.getNode(0));
Shinya Kitaoka 120a6e
      ++counter;
Shinya Kitaoka 120a6e
      continue;
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Discriminate between graphs, two-endpoint single sequences, and circular
Shinya Kitaoka 120a6e
    // ones
Shinya Kitaoka 120a6e
    bool has1DegreePoint = 0;
Shinya Kitaoka 120a6e
    for (i = 0; i < currGraph.getNodesCount(); ++i)
Shinya Kitaoka 120a6e
      if (currGraph.getNode(i).degree() != 2)
Shinya Kitaoka 120a6e
        if (currGraph.getNode(i).degree() == 1)
Shinya Kitaoka 120a6e
          has1DegreePoint = 1;
Shinya Kitaoka 120a6e
        else
Shinya Kitaoka 120a6e
          goto _graph;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    if (has1DegreePoint)
Shinya Kitaoka 120a6e
      goto _two_endpoint;
Shinya Kitaoka 120a6e
    else
Shinya Kitaoka 120a6e
      goto _circulars;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  _two_endpoint : {
Shinya Kitaoka 120a6e
    // Find head
Shinya Kitaoka 120a6e
    for (i = 0; currGraph.getNode(i).degree() != 1; ++i)
Shinya Kitaoka 120a6e
      ;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    currSequence.m_head     = i;
Shinya Kitaoka 120a6e
    currSequence.m_headLink = 0;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Find tail
Shinya Kitaoka 120a6e
    for (++i;
Shinya Kitaoka 120a6e
         i < currGraph.getNodesCount() && currGraph.getNode(i).degree() == 2;
Shinya Kitaoka 120a6e
         ++i)
Shinya Kitaoka 120a6e
      ;
Shinya Kitaoka 120a6e
    currSequence.m_tail     = i;
Shinya Kitaoka 120a6e
    currSequence.m_tailLink = 0;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    globals->singleSequences.push_back(currSequence);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    ++counter;
Shinya Kitaoka 120a6e
    continue;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  _graph : {
Shinya Kitaoka 120a6e
    // Organize Graph-like part
Shinya Kitaoka 120a6e
    globals->organizedGraphs.push_back(JointSequenceGraph());
Shinya Kitaoka 120a6e
    JointSequenceGraph &JSGraph = globals->organizedGraphs.back();
Shinya Kitaoka 120a6e
    contourFamilyOfOrganized.push_back(counter);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    jointsMap.clear();
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Gather all sequence extremities
Shinya Kitaoka 120a6e
    for (i = 0; i < currGraph.getNodesCount(); ++i) {
Shinya Kitaoka 120a6e
      if (currGraph.getNode(i).degree() != 2) {
Shinya Kitaoka 120a6e
        j = JSGraph.newNode(i);
Shinya Kitaoka 120a6e
        // Using a map to keep one-to-one relation between j and i
Shinya Kitaoka 120a6e
        jointsMap.insert(uintMap::value_type(i, j));
Shinya Kitaoka 120a6e
      }
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Extract Sequences
Shinya Kitaoka 120a6e
    for (i = 0; i < JSGraph.getNodesCount(); ++i) {
Shinya Kitaoka 120a6e
      UINT joint = *JSGraph.getNode(i);
Shinya Kitaoka 120a6e
      for (j = 0; j < currGraph.getNode(joint).getLinksCount(); ++j) {
Shinya Kitaoka 120a6e
        currSequence.m_head     = joint;
Shinya Kitaoka 120a6e
        currSequence.m_headLink = j;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
        // Seek tail
Shinya Kitaoka 120a6e
        UINT oldNode  = joint,
Shinya Kitaoka 120a6e
             thisNode = currGraph.getNode(joint).getLink(j).getNext();
Shinya Kitaoka 120a6e
        while (currGraph.getNode(thisNode).degree() == 2) {
Shinya Kitaoka 120a6e
          currGraph.node(thisNode).setAttribute(
Shinya Kitaoka 120a6e
              ORGANIZEGRAPHS_SIGN);  // Sign thisNode as part of a JSGraph
Shinya Kitaoka 120a6e
          currSequence.advance(oldNode, thisNode);
Shinya Kitaoka 120a6e
        }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
        currSequence.m_tail = thisNode;
Shinya Kitaoka 120a6e
        currSequence.m_tailLink =
Shinya Kitaoka 120a6e
            currGraph.getNode(thisNode).linkOfNode(oldNode);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
        JSGraph.newLink(i, jointsMap.find(thisNode)->second, currSequence);
Shinya Kitaoka 120a6e
      }
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // NOTE: The following may seem uncommon - you must observe that, *WHEN
Shinya Kitaoka 120a6e
  // maxThickness
Shinya Kitaoka 120a6e
  //      more isolated sequence groups may arise in the SAME SkeletonGraph; so,
Shinya Kitaoka 120a6e
  //      an organized
Shinya Kitaoka 120a6e
  //      graph may contain different unconnected basic graph-structures.
Shinya Kitaoka 120a6e
  //      Further, remaining circular sequences may still exist. Therefore:
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Proceed with remaining circulars extraction
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  _circulars : {
Shinya Kitaoka 120a6e
    // Extract all circular sequences
Shinya Kitaoka 120a6e
    // Find a sequence point
Shinya Kitaoka 120a6e
    for (i = 0; i < currGraph.getNodesCount(); ++i) {
Shinya Kitaoka 120a6e
      if (!currGraph.getNode(i).hasAttribute(ORGANIZEGRAPHS_SIGN) &&
Shinya Kitaoka 120a6e
          currGraph.getNode(i).degree() == 2) {
Shinya Kitaoka 120a6e
        unsigned int curr = i, currLink = 0;
Shinya Kitaoka 120a6e
        currSequence.next(curr, currLink);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
        for (; curr != i; currSequence.next(curr, currLink))
Shinya Kitaoka 120a6e
          currGraph.node(curr).setAttribute(ORGANIZEGRAPHS_SIGN);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
        // Add sequence
Shinya Kitaoka 120a6e
        currSequence.m_head = currSequence.m_tail = i;
Shinya Kitaoka 120a6e
        currSequence.m_headLink                   = 0;
Shinya Kitaoka 120a6e
        currSequence.m_tailLink                   = 1;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
        globals->singleSequences.push_back(currSequence);
Shinya Kitaoka 120a6e
      }
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//==========================================================================
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//******************************
Toshihiro Shimizu 890ddd
//       Junction Recovery
Toshihiro Shimizu 890ddd
//******************************
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// EXPLANATION: Junction recovery attempts to reshape skeleton junctions when
Toshihiro Shimizu 890ddd
//  possible. The original polygons shape must not be exceedingly broken, and
Toshihiro Shimizu 890ddd
//  no visible shape alteration must found.
Shinya Kitaoka 120a6e
// WARNING: Currently not working together with
Shinya Kitaoka 120a6e
// globals->currConfig->m_maxThickness
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//------------------
Toshihiro Shimizu 890ddd
//    Globals
Toshihiro Shimizu 890ddd
//------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
namespace {
Toshihiro Shimizu 890ddd
const double roadsMaxSlope = 0.3;
Shinya Kitaoka 120a6e
const double shapeDistMul  = 1;
Shinya Kitaoka 120a6e
const double hDiffMul      = 0.3;
Shinya Kitaoka 120a6e
const double lineDistMul   = 1;
Shinya Kitaoka 120a6e
const double pullBackMul   = 0.2;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//-------------------------
Toshihiro Shimizu 890ddd
//    Roads Extraction
Toshihiro Shimizu 890ddd
//-------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// SMALL ISSUE: The following is currently done for both side
Shinya Kitaoka 120a6e
// of a sequence...
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
inline void findRoads(const Sequence &s) {
Shinya Kitaoka 120a6e
  unsigned int curr, currLink, next;
Shinya Kitaoka 120a6e
  unsigned int roadStart, roadStartLink;
Shinya Kitaoka 120a6e
  double d, hMax, length;
Shinya Kitaoka 120a6e
  bool lowSlope, roadOn = 0;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  curr     = s.m_head;
Shinya Kitaoka 120a6e
  currLink = s.m_headLink;
Shinya Kitaoka 120a6e
  for (; curr != s.m_tail; s.next(curr, currLink)) {
Shinya Kitaoka 120a6e
    next = s.m_graphHolder->getNode(curr).getLink(currLink).getNext();
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    d = planeDistance(*s.m_graphHolder->getNode(curr),
Shinya Kitaoka 120a6e
                      *s.m_graphHolder->getNode(next));
Shinya Kitaoka 120a6e
    lowSlope =
Shinya Kitaoka 120a6e
        fabs(s.m_graphHolder->getNode(curr).getLink(currLink)->getSlope()) <
Shinya Kitaoka 120a6e
                roadsMaxSlope
Shinya Kitaoka 120a6e
            ? 1
Shinya Kitaoka 120a6e
            : 0;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Entering event in a *possibile* road axis
Shinya Kitaoka 120a6e
    if (!roadOn && lowSlope) {
Shinya Kitaoka 120a6e
      length        = 0;
Shinya Kitaoka 120a6e
      hMax          = s.m_graphHolder->getNode(curr)->z;
Shinya Kitaoka 120a6e
      roadStart     = curr;
Shinya Kitaoka 120a6e
      roadStartLink = currLink;
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Exit event from a          """
Shinya Kitaoka 120a6e
    else if (roadOn && !lowSlope && (length > hMax))
Shinya Kitaoka 120a6e
      // Then sign ROAD the sequence from roadStart to curr.
Shinya Kitaoka 120a6e
      for (; roadStart != curr; s.next(roadStart, roadStartLink))
Shinya Kitaoka 120a6e
        s.m_graphHolder->node(roadStart)
Shinya Kitaoka 120a6e
            .link(roadStartLink)
Shinya Kitaoka 120a6e
            ->setAttribute(SkeletonArc::ROAD);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Now update vars
Shinya Kitaoka 120a6e
    if (lowSlope) {
Shinya Kitaoka 120a6e
      length += d;
Shinya Kitaoka 120a6e
      if (hMax < s.m_graphHolder->getNode(next)->z)
Shinya Kitaoka 120a6e
        hMax = s.m_graphHolder->getNode(next)->z;
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    roadOn = lowSlope;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // At sequence end, force an exit event
Shinya Kitaoka 120a6e
  if (roadOn && (length > hMax))
Shinya Kitaoka 120a6e
    for (; roadStart != curr; s.next(roadStart, roadStartLink))
Shinya Kitaoka 120a6e
      s.m_graphHolder->node(roadStart)
Shinya Kitaoka 120a6e
          .link(roadStartLink)
Shinya Kitaoka 120a6e
          ->setAttribute(SkeletonArc::ROAD);
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// Find the 'roads' of the current Graph.
Campbell Barton b3bd84
static void findRoads(const JointSequenceGraph &JSGraph) {
Shinya Kitaoka 120a6e
  unsigned int i, j;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // For all Sequence of currGraph, extract roads
Shinya Kitaoka 120a6e
  for (i = 0; i < JSGraph.getNodesCount(); ++i) {
Shinya Kitaoka 120a6e
    for (j = 0; j < JSGraph.getNode(i).getLinksCount(); ++j)
Shinya Kitaoka 120a6e
      // if(JSGraph.getNode(i).getLink(j)->isForward())
Shinya Kitaoka 120a6e
      findRoads(*JSGraph.getNode(i).getLink(j));
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//----------------------------------
Toshihiro Shimizu 890ddd
//    Junction Recovery Classes
Toshihiro Shimizu 890ddd
//----------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// Entering point of a Sequence inside a Junction Area
Shinya Kitaoka d1f6c4
class EnteringSequence final : public Sequence {
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  TPointD m_direction;  // In this case, we keep
Shinya Kitaoka 120a6e
  double m_height;      // separated (x,y) and z coords.
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  // Also store indices toward the next (outer) joint
Shinya Kitaoka 120a6e
  unsigned int m_initialJoint;
Shinya Kitaoka 120a6e
  unsigned int m_outerLink;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  EnteringSequence() {}
Shinya Kitaoka 120a6e
  EnteringSequence(const Sequence &s) : Sequence(s) {}
Toshihiro Shimizu 890ddd
};
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
class JunctionArea {
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  std::vector<enteringsequence> m_enteringSequences;</enteringsequence>
Shinya Kitaoka 120a6e
  std::vector<unsigned int=""> m_jointsAbsorbed;</unsigned>
Shinya Kitaoka 120a6e
  TPointD m_newJointPosition;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  JunctionArea() {}
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  // Initialize Junction Area
Shinya Kitaoka 120a6e
  void expandArea(unsigned int initial);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  // Calculate and evaluate area
Shinya Kitaoka 120a6e
  bool checkShape();
Shinya Kitaoka 120a6e
  bool solveJunctionPosition();
Shinya Kitaoka 120a6e
  bool makeHeights();
Shinya Kitaoka 120a6e
  bool calculateReconstruction();
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  // Substitute area over old configuration
Shinya Kitaoka 120a6e
  bool sequencesPullBack();
Shinya Kitaoka 120a6e
  void apply();
Toshihiro Shimizu 890ddd
};
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//----------------------------
Toshihiro Shimizu 890ddd
//    Expansion Procedure
Toshihiro Shimizu 890ddd
//----------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// Junction Area expansion procedure
Shinya Kitaoka 120a6e
inline void JunctionArea::expandArea(unsigned int initial) {
Shinya Kitaoka 120a6e
  unsigned int a;
Shinya Kitaoka 120a6e
  unsigned int curr, currLink;
Shinya Kitaoka 120a6e
  unsigned int i, iLink, iNext;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  m_jointsAbsorbed.push_back(initial);
Shinya Kitaoka 120a6e
  currJSGraph->node(initial).setAttribute(
Shinya Kitaoka 120a6e
      JointSequenceGraph::REACHED);  // Nodes absorbed gets signed
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  for (a = 0; a < m_jointsAbsorbed.size(); ++a) {
Shinya Kitaoka 120a6e
    // Extract a joint from vector
Shinya Kitaoka 120a6e
    curr = m_jointsAbsorbed[a];
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    for (currLink = 0; currLink < currJSGraph->getNode(curr).getLinksCount();
Shinya Kitaoka 120a6e
         ++currLink) {
Shinya Kitaoka 120a6e
      Sequence &s = *currJSGraph->node(curr).link(currLink);
Shinya Kitaoka 120a6e
      if (s.m_graphHolder->getNode(s.m_head)
Shinya Kitaoka 120a6e
              .getLink(s.m_headLink)
Shinya Kitaoka 120a6e
              .getAccess()) {
Shinya Kitaoka 120a6e
        // Expand into all nearby sequences, until a ROAD is found
Shinya Kitaoka 120a6e
        i     = s.m_head;
Shinya Kitaoka 120a6e
        iLink = s.m_headLink;
Shinya Kitaoka 120a6e
        for (; i != s.m_tail &&
Shinya Kitaoka 120a6e
               !s.m_graphHolder->getNode(i).getLink(iLink)->hasAttribute(
Shinya Kitaoka 120a6e
                   SkeletonArc::ROAD);
Shinya Kitaoka 120a6e
             s.next(i, iLink))
Shinya Kitaoka 120a6e
          ;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
        // If the sequence has been completely run, include next joint in the
Shinya Kitaoka 120a6e
        // expansion procedure AND sign it as 'REACHED'
Shinya Kitaoka 120a6e
        if (i == s.m_tail) {
Shinya Kitaoka 120a6e
          iNext = currJSGraph->getNode(curr).getLink(currLink).getNext();
Shinya Kitaoka 120a6e
          if (!currJSGraph->node(iNext).hasAttribute(
Shinya Kitaoka 120a6e
                  JointSequenceGraph::REACHED)) {
Shinya Kitaoka 120a6e
            currJSGraph->node(iNext).setAttribute(JointSequenceGraph::REACHED);
Shinya Kitaoka 120a6e
            m_jointsAbsorbed.push_back(iNext);
Shinya Kitaoka 120a6e
          }
Shinya Kitaoka 120a6e
          // Negate access to this sequence
Shinya Kitaoka 120a6e
          s.m_graphHolder->node(s.m_tail).link(s.m_tailLink).setAccess(0);
Shinya Kitaoka 120a6e
          s.m_graphHolder->node(s.m_head).link(s.m_headLink).setAccess(0);
Shinya Kitaoka 120a6e
        } else {
Shinya Kitaoka 120a6e
          // Initialize and copy the entering sequence found
Shinya Kitaoka 120a6e
          m_enteringSequences.push_back(EnteringSequence(s));
Shinya Kitaoka 120a6e
          m_enteringSequences.back().m_head     = i;
Shinya Kitaoka 120a6e
          m_enteringSequences.back().m_headLink = iLink;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
          // Initialize entering directions
Shinya Kitaoka 120a6e
          iNext = s.m_graphHolder->getNode(i).getLink(iLink).getNext();
Shinya Kitaoka 120a6e
          m_enteringSequences.back().m_direction = planeProjection(
Shinya Kitaoka 120a6e
              *s.m_graphHolder->getNode(i) - *s.m_graphHolder->getNode(iNext));
Shinya Kitaoka 120a6e
          m_enteringSequences.back().m_direction =
Shinya Kitaoka 120a6e
              m_enteringSequences.back().m_direction *
Shinya Kitaoka 120a6e
              (1 / norm(m_enteringSequences.back().m_direction));
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
          // Initialize entering height / slope
Shinya Kitaoka 120a6e
          m_enteringSequences.back().m_height = s.m_graphHolder->getNode(i)->z;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
          // Also store pointer to link toward the joint at the end of sequence
Shinya Kitaoka 120a6e
          m_enteringSequences.back().m_initialJoint = curr;
Shinya Kitaoka 120a6e
          m_enteringSequences.back().m_outerLink    = currLink;
Shinya Kitaoka 120a6e
        }
Shinya Kitaoka 120a6e
      }
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//-----------------------
Toshihiro Shimizu 890ddd
//    Area Shape Test
Toshihiro Shimizu 890ddd
//-----------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
inline bool JunctionArea::checkShape() {
Shinya Kitaoka 120a6e
  std::vector<enteringsequence>::iterator a, b;</enteringsequence>
Shinya Kitaoka 120a6e
  unsigned int node, contour, first, last, n;
Shinya Kitaoka 120a6e
  TPointD A, A1, B, B1, P, P1;
Shinya Kitaoka 120a6e
  bool result = 1;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // First, sign all outgoing arcs' m_leftGeneratingNode as end of
Shinya Kitaoka 120a6e
  // control procedure
Shinya Kitaoka 120a6e
  for (a = m_enteringSequences.begin(); a != m_enteringSequences.end(); ++a) {
Shinya Kitaoka 120a6e
    node = a->m_graphHolder->getNode(a->m_head)
Shinya Kitaoka 120a6e
               .getLink(a->m_headLink)
Shinya Kitaoka 120a6e
               ->getLeftGenerator();
Shinya Kitaoka 120a6e
    contour = a->m_graphHolder->getNode(a->m_head)
Shinya Kitaoka 120a6e
                  .getLink(a->m_headLink)
Shinya Kitaoka 120a6e
                  ->getLeftContour();
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    (*currContourFamily)[contour][node].setAttribute(ContourNode::JR_RESERVED);
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Now, check shape
Shinya Kitaoka 120a6e
  for (a = m_enteringSequences.begin(), b = m_enteringSequences.end() - 1;
Shinya Kitaoka 120a6e
       a != m_enteringSequences.end(); b = a, ++a) {
Shinya Kitaoka 120a6e
    // Initialize contour check
Shinya Kitaoka 120a6e
    first = a->m_graphHolder->getNode(a->m_head)
Shinya Kitaoka 120a6e
                .getLink(a->m_headLink)
Shinya Kitaoka 120a6e
                ->getRightGenerator();
Shinya Kitaoka 120a6e
    // last= b->m_graphHolder->getNode(b->m_head).getLink(b->m_headLink)
Shinya Kitaoka 120a6e
    //  ->getLeftGenerator();
Shinya Kitaoka 120a6e
    contour = a->m_graphHolder->getNode(a->m_head)
Shinya Kitaoka 120a6e
                  .getLink(a->m_headLink)
Shinya Kitaoka 120a6e
                  ->getRightContour();
Shinya Kitaoka 120a6e
    n = (*currContourFamily)[contour].size();
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Better this effective way to find the last
Shinya Kitaoka 120a6e
    unsigned int numChecked = 0;
Shinya Kitaoka 120a6e
    for (last = first; !(*currContourFamily)[contour][last].hasAttribute(
Shinya Kitaoka 120a6e
                           ContourNode::JR_RESERVED) &&
Shinya Kitaoka 120a6e
                       numChecked < n;
Shinya Kitaoka 120a6e
         last = (last + 1) % n, ++numChecked)
Shinya Kitaoka 120a6e
      ;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Security check
Shinya Kitaoka 120a6e
    if (numChecked == n) return 0;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    A  = planeProjection((*currContourFamily)[contour][first].m_position);
Shinya Kitaoka 120a6e
    A1 = planeProjection(
Shinya Kitaoka 120a6e
        (*currContourFamily)[contour][(first + 1) % n].m_position);
Shinya Kitaoka 120a6e
    B  = planeProjection((*currContourFamily)[contour][last].m_position);
Shinya Kitaoka 120a6e
    B1 = planeProjection(
Shinya Kitaoka 120a6e
        (*currContourFamily)[contour][(last + 1) % n].m_position);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    for (node = first; !(*currContourFamily)[contour][node].hasAttribute(
Shinya Kitaoka 120a6e
             ContourNode::JR_RESERVED);
Shinya Kitaoka 120a6e
         node = (node + 1) % n) {
Shinya Kitaoka 120a6e
      P  = planeProjection((*currContourFamily)[contour][node].m_position);
Shinya Kitaoka 120a6e
      P1 = planeProjection(
Shinya Kitaoka 120a6e
          (*currContourFamily)[contour][(node + 1) % n].m_position);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      // EXPLANATION:
Shinya Kitaoka 120a6e
      // Segment P-P1  must be included in fat lines passing for A-A1 or B-B1
Shinya Kitaoka 120a6e
      result &=
Shinya Kitaoka 120a6e
          (fabs(cross(P - A, normalize(A1 - A))) < a->m_height * shapeDistMul &&
Shinya Kitaoka 120a6e
           fabs(cross(P1 - A, normalize(A1 - A))) < a->m_height * shapeDistMul)
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
          ||
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
          (fabs(cross(P - B, normalize(B1 - B))) < b->m_height * shapeDistMul &&
Shinya Kitaoka 120a6e
           fabs(cross(P1 - B, normalize(B1 - B))) < b->m_height * shapeDistMul);
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Finally, restore nodes attributes
Shinya Kitaoka 120a6e
  for (a = m_enteringSequences.begin(); a != m_enteringSequences.end(); ++a) {
Shinya Kitaoka 120a6e
    node = a->m_graphHolder->getNode(a->m_head)
Shinya Kitaoka 120a6e
               .getLink(a->m_headLink)
Shinya Kitaoka 120a6e
               ->getLeftGenerator();
Shinya Kitaoka 120a6e
    contour = a->m_graphHolder->getNode(a->m_head)
Shinya Kitaoka 120a6e
                  .getLink(a->m_headLink)
Shinya Kitaoka 120a6e
                  ->getLeftContour();
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    (*currContourFamily)[contour][node].clearAttribute(
Shinya Kitaoka 120a6e
        ContourNode::JR_RESERVED);
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  return result;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------
Toshihiro Shimizu 890ddd
//    Solve new junction position problem
Toshihiro Shimizu 890ddd
//--------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
inline bool JunctionArea::solveJunctionPosition() {
Shinya Kitaoka 120a6e
  std::vector<enteringsequence>::iterator a;</enteringsequence>
Shinya Kitaoka 120a6e
  double Sx2 = 0, Sy2 = 0, Sxy = 0;
Shinya Kitaoka 120a6e
  TPointD P, v, b;
Shinya Kitaoka 120a6e
  double h;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Build preliminary sums for the linear system
Shinya Kitaoka 120a6e
  for (a = m_enteringSequences.begin(); a != m_enteringSequences.end(); ++a) {
Shinya Kitaoka 120a6e
    h = a->m_height;
Shinya Kitaoka 120a6e
    v = a->m_direction;
Shinya Kitaoka 120a6e
    P = planeProjection(*a->m_graphHolder->getNode(a->m_head));
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Height-weighted problem
Shinya Kitaoka 120a6e
    Sx2 += sq(v.x) * h;
Shinya Kitaoka 120a6e
    Sy2 += sq(v.y) * h;
Shinya Kitaoka 120a6e
    Sxy += v.x * v.y * h;
Shinya Kitaoka 120a6e
    b.x += h * (sq(v.y) * P.x - (v.x * v.y * P.y));
Shinya Kitaoka 120a6e
    b.y += h * (sq(v.x) * P.y - (v.x * v.y * P.x));
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // First check problem determinant
Shinya Kitaoka 120a6e
  double det = Sx2 * Sy2 - sq(Sxy);
Shinya Kitaoka 120a6e
  if (fabs(det) < 0.1) return 0;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Now construct linear system
Shinya Kitaoka 120a6e
  TAffine M(Sx2 / det, Sxy / det, 0, Sxy / det, Sy2 / det, 0);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  m_newJointPosition = M * b;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Finally, check if J is too far from the line extensions of the entering
Shinya Kitaoka 120a6e
  // sequences
Shinya Kitaoka 120a6e
  for (a = m_enteringSequences.begin(); a != m_enteringSequences.end(); ++a) {
Shinya Kitaoka 120a6e
    P = planeProjection(*a->m_graphHolder->getNode(a->m_head));
Shinya Kitaoka 120a6e
    if (tdistance(m_newJointPosition, a->m_direction, P) >
Shinya Kitaoka 120a6e
        a->m_height * lineDistMul)
Shinya Kitaoka 120a6e
      return 0;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  return 1;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//---------------------------------------
Toshihiro Shimizu 890ddd
//    Calculate optimal joint heights
Toshihiro Shimizu 890ddd
//---------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// Globals
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
namespace {
Toshihiro Shimizu 890ddd
const std::vector<enteringsequence> *currEnterings;</enteringsequence>
Toshihiro Shimizu 890ddd
const std::vector<unsigned int=""> *heightIndicesPtr;</unsigned>
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
std::vector<double> *optHeights;</double>
Toshihiro Shimizu 890ddd
double optMeanError;
Toshihiro Shimizu 890ddd
double hMax;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
inline bool checkCircles(std::vector<double> &heights) {</double>
Shinya Kitaoka 120a6e
  unsigned int i, j;
Shinya Kitaoka 120a6e
  double cos, sin, frac;
Shinya Kitaoka 120a6e
  TPointD vi, vj;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  // Execute test on angle-consecutive EnteringSequences couples
Shinya Kitaoka 120a6e
  for (j = 0, i = currEnterings->size() - 1; j < currEnterings->size();
Shinya Kitaoka 120a6e
       i = j, ++j) {
Shinya Kitaoka 120a6e
    vi = (*currEnterings)[i].m_direction;
Shinya Kitaoka 120a6e
    vj = (*currEnterings)[j].m_direction;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    sin = cross(vi, vj);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    if (heights[i] == heights[j]) goto test_against_max_height;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    frac = heights[i] / heights[j];
Shinya Kitaoka 120a6e
    if (sin < 0) return 0;
Shinya Kitaoka 120a6e
    cos = vi * vj;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    if (cos < 0 && (frac < -cos || frac > (-1 / cos))) return 0;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  test_against_max_height:
Shinya Kitaoka 120a6e
    // Reusing cos
Shinya Kitaoka 120a6e
    cos = (sin < 0.1)
Shinya Kitaoka 120a6e
              ? std::max(heights[i], heights[j])
Shinya Kitaoka 120a6e
              : norm((vi * (heights[j] / sin)) + (vj * (heights[i] / sin)));
Shinya Kitaoka 120a6e
    if (cos < hMax) return 0;
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  return 1;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
inline void tryConfiguration(const std::vector<unsigned int=""> &bounds) {</unsigned>
Shinya Kitaoka 120a6e
  std::vector<double> currHeights(currEnterings->size());</double>
Shinya Kitaoka 120a6e
  double mean, currMeanError = 0;
Shinya Kitaoka 120a6e
  unsigned int i, j, first, end;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  for (i = 0, first = 0; i <= bounds.size(); first = end, ++i) {
Shinya Kitaoka 120a6e
    end = i < bounds.size() ? end = bounds[i] + 1 : currEnterings->size();
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Calculate mean from first (included) to end (not included)
Shinya Kitaoka 120a6e
    for (j = first, mean = 0; j < end; ++j)
Shinya Kitaoka 120a6e
      mean += (*currEnterings)[(*heightIndicesPtr)[j]].m_height;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    mean /= end - first;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Check if the distance from extremities to mean is tolerable
Shinya Kitaoka 120a6e
    if (std::max((*currEnterings)[(*heightIndicesPtr)[end - 1]].m_height - mean,
Shinya Kitaoka 120a6e
                 mean - (*currEnterings)[(*heightIndicesPtr)[first]].m_height) >
Shinya Kitaoka 120a6e
        hDiffMul * mean)
Shinya Kitaoka 120a6e
      return;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Calculate squared error to mean
Shinya Kitaoka 120a6e
    for (j = first; j < end; ++j)
Shinya Kitaoka 120a6e
      currMeanError +=
Shinya Kitaoka 120a6e
          sq((*currEnterings)[(*heightIndicesPtr)[j]].m_height - mean);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Set calculated currHeights
Shinya Kitaoka 120a6e
    for (j = first; j < end; ++j) currHeights[(*heightIndicesPtr)[j]] = mean;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Update current maximum height
Shinya Kitaoka 120a6e
  hMax = mean;  // Global
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // If this configuration could be better than current, launch circle test
Shinya Kitaoka 120a6e
  if (optHeights->empty() || currMeanError < optMeanError) {
Shinya Kitaoka 120a6e
    if (checkCircles(currHeights)) {
Shinya Kitaoka 120a6e
      (*optHeights) = currHeights;
Shinya Kitaoka 120a6e
      optMeanError  = currMeanError;
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
class hLess {
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  std::vector<enteringsequence> &m_entSequences;</enteringsequence>
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  hLess(std::vector<enteringsequence> &v) : m_entSequences(v) {}</enteringsequence>
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  inline bool operator()(unsigned int a, unsigned int b) {
Shinya Kitaoka 120a6e
    return m_entSequences[a].m_height < m_entSequences[b].m_height;
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
};
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// EXPLANATION: We build intervals on which height means are done.
Shinya Kitaoka 120a6e
// Their right Interval Bounds are supposed INCLUDED.
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// Example: heights[]= {1, 2, 3, 4}; rightIntervalBounds[]={0, 2};
Toshihiro Shimizu 890ddd
//  =>  do height means on: {1}, {2,3}, {4}. (*)
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// After means are calculated, a test on the obtained configuration is
Shinya Kitaoka 120a6e
// performed. Among those configurations which pass the test, the one
Shinya Kitaoka 120a6e
// with rightIntervalBounds.size()->min and, on same sizes,
Shinya Kitaoka 120a6e
// currMeanError->min is the 'best' configuration possible.
Shinya Kitaoka 120a6e
// If no height configuration pass the test, reconstruction fails.
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//(*) NOTE: The right Interval Bounds will never include index n-1, which
Shinya Kitaoka 120a6e
// interferes with push_backs.
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
inline bool JunctionArea::makeHeights() {
Shinya Kitaoka 120a6e
  std::vector<unsigned int=""> heightOrderedIndices;</unsigned>
Shinya Kitaoka 120a6e
  std::vector<unsigned int=""> rightIntervalBounds;</unsigned>
Shinya Kitaoka 120a6e
  std::vector<double> optimalHeights;</double>
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  unsigned int i, n, m;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Sort entering sequences' indices for increasing height/thickness
Shinya Kitaoka 120a6e
  heightOrderedIndices.resize(m_enteringSequences.size());
Shinya Kitaoka 120a6e
  for (i = 0; i < m_enteringSequences.size(); ++i) heightOrderedIndices[i] = i;
Shinya Kitaoka 120a6e
  sort(heightOrderedIndices.begin(), heightOrderedIndices.end(),
Shinya Kitaoka 120a6e
       hLess(m_enteringSequences));
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Initialize globals/references
Shinya Kitaoka 120a6e
  currEnterings    = &m_enteringSequences;
Shinya Kitaoka 120a6e
  heightIndicesPtr = &heightOrderedIndices;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  optMeanError = 0;
Shinya Kitaoka 120a6e
  optHeights   = &optimalHeights;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Now build height-mean configurations and launch their tests
Shinya Kitaoka 120a6e
  n = m_enteringSequences.size();
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // The m=0 case is done first, apart
Shinya Kitaoka 120a6e
  rightIntervalBounds.resize(0);
Shinya Kitaoka 120a6e
  tryConfiguration(rightIntervalBounds);
Shinya Kitaoka 120a6e
  for (m = 1; m < n && optimalHeights.empty(); ++m) {
Shinya Kitaoka 120a6e
    // Initialize bounds
Shinya Kitaoka 120a6e
    rightIntervalBounds.resize(1);
Shinya Kitaoka 120a6e
    rightIntervalBounds[0] = 0;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    while (!rightIntervalBounds.empty()) {
Shinya Kitaoka 120a6e
      // Fill bounds if necessary
Shinya Kitaoka 120a6e
      while (rightIntervalBounds.size() < m)
Shinya Kitaoka 120a6e
        rightIntervalBounds.push_back(rightIntervalBounds.back() + 1);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      tryConfiguration(rightIntervalBounds);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      //'Advance' configuration: increment last index and pop those
Shinya Kitaoka 120a6e
      // exceeding valid size. If bounds gets empty, done all configs
Shinya Kitaoka 120a6e
      // with m+1 intervals.
Shinya Kitaoka 120a6e
      while ((
Shinya Kitaoka 120a6e
          ++rightIntervalBounds.back(),
Shinya Kitaoka 120a6e
          rightIntervalBounds.back() < n - 1 - (m - rightIntervalBounds.size())
Shinya Kitaoka 120a6e
              ? 0
Shinya Kitaoka 120a6e
              : (rightIntervalBounds.pop_back(), !rightIntervalBounds.empty())))
Shinya Kitaoka 120a6e
        ;
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  if (!optimalHeights.empty()) {
Shinya Kitaoka 120a6e
    for (i = 0; i < n; ++i) m_enteringSequences[i].m_height = optimalHeights[i];
Shinya Kitaoka 120a6e
    return 1;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  return 0;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//==========================================================================
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//------------------------------
Toshihiro Shimizu 890ddd
//    Area Calculation Main
Toshihiro Shimizu 890ddd
//------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
class EntSequenceLess {
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  EntSequenceLess() {}
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  inline bool operator()(const EnteringSequence &a, const EnteringSequence &b) {
Shinya Kitaoka 120a6e
    // m_direction is normalized, therefore:
Shinya Kitaoka 120a6e
    return a.m_direction.y >= 0
Shinya Kitaoka 120a6e
               ? b.m_direction.y >= 0 ? a.m_direction.x > b.m_direction.x : 1
Shinya Kitaoka 120a6e
               : b.m_direction.y < 0 ? a.m_direction.x < b.m_direction.x : 0;
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
};
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
bool JunctionArea::calculateReconstruction() {
Shinya Kitaoka 120a6e
  unsigned int i;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  if (m_enteringSequences.size() == 0) return 0;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  // Apply preliminary tests for this Junction Area
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  // a) Check if endpoints got absorbed by the expansion process
Shinya Kitaoka 120a6e
  for (i = 0; i < m_jointsAbsorbed.size(); ++i)
Shinya Kitaoka 120a6e
    if (currJSGraph->getNode(m_jointsAbsorbed[i]).degree() == 1) return 0;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  // b) Check if the contours shape resembles that of a crossing
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  sort(m_enteringSequences.begin(), m_enteringSequences.end(),
Shinya Kitaoka 120a6e
       EntSequenceLess());
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  if (!checkShape()) return 0;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  // c) Build the new junction Point plane position
Shinya Kitaoka 120a6e
  if (!solveJunctionPosition()) return 0;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  // d) Build joint optimal heights (each for entering sequence...)
Shinya Kitaoka 120a6e
  if (!makeHeights()) return 0;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  return 1;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//==========================================================================
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//---------------------------
Toshihiro Shimizu 890ddd
//    Sequences Pull Back
Toshihiro Shimizu 890ddd
//---------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// EXPLANATION: We have to insure that connecting entering sequences to the
Shinya Kitaoka 120a6e
// new junction point happens *smoothly*. In order to do this, wh withdraw
Shinya Kitaoka 120a6e
// entering sequences along the enterin road, until the angle given by the
Shinya Kitaoka 120a6e
// connecting line and the entering direction is small.
Shinya Kitaoka 120a6e
// However, sequence pull back can be done only under some constraints:
Toshihiro Shimizu 890ddd
//  * we have to remain inside a road axis
Toshihiro Shimizu 890ddd
//  * ........................ a given fat line around the entering direction
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
inline bool JunctionArea::sequencesPullBack() {
Shinya Kitaoka 120a6e
  std::vector<enteringsequence>::iterator a;</enteringsequence>
Shinya Kitaoka 120a6e
  double alongLinePosition, distanceFromLine;
Shinya Kitaoka 120a6e
  unsigned int i, iLink, tail;
Shinya Kitaoka 120a6e
  TPointD P;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  for (a = m_enteringSequences.begin(); a != m_enteringSequences.end(); ++a) {
Shinya Kitaoka 120a6e
    i     = a->m_head;
Shinya Kitaoka 120a6e
    iLink = a->m_headLink;
Shinya Kitaoka 120a6e
    // NOTE: updated tails are stored this way, *DONT* look in a->m_tail
Shinya Kitaoka 120a6e
    // because these typically store old infos
Shinya Kitaoka 120a6e
    tail =
Shinya Kitaoka 120a6e
        currJSGraph->getNode(a->m_initialJoint).getLink(a->m_outerLink)->m_tail;
Shinya Kitaoka 120a6e
    P = planeProjection(*a->m_graphHolder->getNode(a->m_head));
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    while (i != tail) {
Shinya Kitaoka 120a6e
      alongLinePosition = a->m_direction * (m_newJointPosition - P);
Shinya Kitaoka 120a6e
      distanceFromLine  = tdistance(m_newJointPosition, a->m_direction, P);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
      if (alongLinePosition >= 0 &&
Shinya Kitaoka 120a6e
          (distanceFromLine / alongLinePosition) <= 0.5)
Shinya Kitaoka 120a6e
        goto found_pull_back;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
      // We then take the next arc and check it
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
      if (!a->m_graphHolder->getNode(i).getLink(iLink)->hasAttribute(
Shinya Kitaoka 120a6e
              SkeletonArc::ROAD))
Shinya Kitaoka 120a6e
        return 0;  // Pull back failed
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
      a->next(i, iLink);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
      P = planeProjection(*a->m_graphHolder->getNode(i));
Shinya Kitaoka 120a6e
      if (tdistance(P, a->m_direction, m_newJointPosition) >
Shinya Kitaoka 120a6e
          std::max(pullBackMul * a->m_height, 1.0))
Shinya Kitaoka 120a6e
        return 0;  // Pull back failed
Shinya Kitaoka 120a6e
    }
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    // Now checking opposite sequence extremity
Shinya Kitaoka 120a6e
    if (alongLinePosition < 0 || (distanceFromLine / alongLinePosition) > 0.5)
Shinya Kitaoka 120a6e
      return 0;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  found_pull_back:
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    a->m_head     = i;
Shinya Kitaoka 120a6e
    a->m_headLink = iLink;
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  return 1;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//----------------------------------------------
Toshihiro Shimizu 890ddd
//    Substitute new junction configuration
Toshihiro Shimizu 890ddd
//----------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
void JunctionArea::apply() {
Shinya Kitaoka 120a6e
  std::vector<enteringsequence>::iterator a;</enteringsequence>
Shinya Kitaoka 120a6e
  unsigned int newJoint, newSkeletonNode;
Shinya Kitaoka 120a6e
  unsigned int head, headLink, tail, tailLink;
Shinya Kitaoka 120a6e
  unsigned int outerJoint, outerLink;
Shinya Kitaoka 120a6e
  unsigned int i, next, nextLink;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // First, check if Entering Sequences pullback is possible
Shinya Kitaoka 120a6e
  if (!sequencesPullBack()) return;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Then, we can substitute the old configuration
Shinya Kitaoka 120a6e
  // First, sign as 'ELIMINATED' all absorbed joints
Shinya Kitaoka 120a6e
  for (i = 0; i < m_jointsAbsorbed.size(); ++i)
Shinya Kitaoka 120a6e
    currJSGraph->node(m_jointsAbsorbed[i])
Shinya Kitaoka 120a6e
        .setAttribute(JointSequenceGraph::ELIMINATED);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  newJoint = currJSGraph->newNode();
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  for (a = m_enteringSequences.begin(); a != m_enteringSequences.end(); ++a) {
Shinya Kitaoka 120a6e
    // Initialize infos
Shinya Kitaoka 120a6e
    newSkeletonNode =
Shinya Kitaoka 120a6e
        a->m_graphHolder->newNode(T3DPointD(m_newJointPosition, a->m_height));
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Retrieve sequence infos to substitute
Shinya Kitaoka 120a6e
    // NOTE: We update *tail* infos in currJSGraph sequences after each "apply"
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    const JointSequenceGraph::Link &tempLink =
Shinya Kitaoka 120a6e
        currJSGraph->getNode(a->m_initialJoint).getLink(a->m_outerLink);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    head     = tempLink->m_head;
Shinya Kitaoka 120a6e
    headLink = tempLink->m_headLink;
Shinya Kitaoka 120a6e
    tail     = tempLink->m_tail;
Shinya Kitaoka 120a6e
    tailLink = tempLink->m_tailLink;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    outerJoint = tempLink.getNext();
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Find outerLink - from outerJoint to a->m_initialJoint
Shinya Kitaoka 120a6e
    for (i = 0;
Shinya Kitaoka 120a6e
         (currJSGraph->getNode(outerJoint).getLink(i)->m_tail != head) ||
Shinya Kitaoka 120a6e
         (currJSGraph->getNode(outerJoint).getLink(i)->m_tailLink != headLink);
Shinya Kitaoka 120a6e
         ++i)
Shinya Kitaoka 120a6e
      ;
Shinya Kitaoka 120a6e
    outerLink = i;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Now, provide skeleton linkages
Shinya Kitaoka 120a6e
    // NOTE: Discriminate between the following cases
Shinya Kitaoka 120a6e
    // a) m_head->degree == 2
Shinya Kitaoka 120a6e
    // b) m_head == m_tail
Shinya Kitaoka 120a6e
    // c) m_head == original m_head - or, (m_head!=m_tail && m_head->deg>2)
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    if (a->m_graphHolder->getNode(a->m_head).degree() == 2) {
Shinya Kitaoka 120a6e
      a->m_graphHolder->newLink(newSkeletonNode, a->m_head);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      a->m_graphHolder->node(a->m_head)
Shinya Kitaoka 120a6e
          .link(!a->m_headLink)
Shinya Kitaoka 120a6e
          .setNext(newSkeletonNode);
Shinya Kitaoka 120a6e
      a->m_graphHolder->node(a->m_head)
Shinya Kitaoka 120a6e
          .link(!a->m_headLink)
Shinya Kitaoka 120a6e
          ->setAttribute(SkeletonArc::ROAD);
Shinya Kitaoka 120a6e
      // Better clear road attribute or set it?
Shinya Kitaoka 120a6e
    } else if (a->m_head == tail) {
Shinya Kitaoka 120a6e
      a->m_graphHolder->newLink(newSkeletonNode, tail);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      a->m_graphHolder->node(tail).link(tailLink).setNext(newSkeletonNode);
Shinya Kitaoka 120a6e
      a->m_graphHolder->node(tail).link(tailLink)->setAttribute(
Shinya Kitaoka 120a6e
          SkeletonArc::ROAD);
Shinya Kitaoka 120a6e
    } else  //(a->m_head == head)
Shinya Kitaoka 120a6e
    {
Shinya Kitaoka 120a6e
      // In this case, better introduce further a new substitute of head
Shinya Kitaoka 120a6e
      unsigned int newHead = a->m_graphHolder->newNode(
Shinya Kitaoka 120a6e
          T3DPointD(*a->m_graphHolder->getNode(a->m_head)));
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      a->m_graphHolder->newLink(newSkeletonNode, newHead);
Shinya Kitaoka 120a6e
      a->m_graphHolder->newLink(newHead, newSkeletonNode);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      // Link newHead on the other side
Shinya Kitaoka 120a6e
      next     = a->m_graphHolder->getNode(head).getLink(headLink).getNext();
Shinya Kitaoka 120a6e
      nextLink = a->m_graphHolder->getNode(next).linkOfNode(head);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      a->m_graphHolder->newLink(newHead, next);
Shinya Kitaoka 120a6e
      a->m_graphHolder->node(next).link(nextLink).setNext(newHead);
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Finally, update joint linkings and sequence tails.
Shinya Kitaoka 120a6e
    Sequence newSequence;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    newSequence.m_graphHolder = a->m_graphHolder;
Shinya Kitaoka 120a6e
    newSequence.m_head        = newSkeletonNode;
Shinya Kitaoka 120a6e
    newSequence.m_headLink    = 0;
Shinya Kitaoka 120a6e
    newSequence.m_tail        = tail;
Shinya Kitaoka 120a6e
    newSequence.m_tailLink    = tailLink;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    currJSGraph->node(outerJoint).link(outerLink).setNext(newJoint);
Shinya Kitaoka 120a6e
    currJSGraph->node(outerJoint).link(outerLink)->m_tail     = newSkeletonNode;
Shinya Kitaoka 120a6e
    currJSGraph->node(outerJoint).link(outerLink)->m_tailLink = 0;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    currJSGraph->newLink(newJoint, outerJoint, newSequence);
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//-------------------------------
Toshihiro Shimizu 890ddd
//    Junction Recovery Main
Toshihiro Shimizu 890ddd
//-------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// EXPLANATION: Junction Recovery attempts reconstruction of badly-behaved
Shinya Kitaoka 120a6e
// crossings in the raw skeleton of the image.
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
// void inline junctionRecovery(Contours* polygons)
Shinya Kitaoka 120a6e
void junctionRecovery(Contours *polygons, VectorizerCoreGlobals &g) {
Shinya Kitaoka 120a6e
  globals = &g;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  unsigned int i, j;
Shinya Kitaoka 120a6e
  std::vector<junctionarea> junctionAreasList;</junctionarea>
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // For all joints not processed by the Recoverer, launch a new junction
Shinya Kitaoka 120a6e
  // area reconstruction
Shinya Kitaoka 120a6e
  for (i = 0; i < globals->organizedGraphs.size(); ++i) {
Shinya Kitaoka 120a6e
    currJSGraph       = &globals->organizedGraphs[i];
Shinya Kitaoka 120a6e
    currContourFamily = &(*polygons)[contourFamilyOfOrganized[i]];
Shinya Kitaoka 120a6e
    junctionAreasList.clear();
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // First, graph roads are found and signed on the skeleton
Shinya Kitaoka 120a6e
    findRoads(*currJSGraph);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Then, junction areas are identified and reconstructions are calculated
Shinya Kitaoka 120a6e
    for (j = 0; j < currJSGraph->getNodesCount(); ++j)
Shinya Kitaoka 120a6e
      if (!currJSGraph->getNode(j).hasAttribute(JointSequenceGraph::REACHED)) {
Shinya Kitaoka 120a6e
        junctionAreasList.push_back(JunctionArea());
Shinya Kitaoka 120a6e
        junctionAreasList.back().expandArea(j);
Shinya Kitaoka 120a6e
        if (!junctionAreasList.back().calculateReconstruction())
Shinya Kitaoka 120a6e
          junctionAreasList.pop_back();
Shinya Kitaoka 120a6e
      }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Finally, reconstructions are substituted inside the skeleton
Shinya Kitaoka 120a6e
    for (j = 0; j < junctionAreasList.size(); ++j) junctionAreasList[j].apply();
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
}