Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#include "tcurveutil.h"
Toshihiro Shimizu 890ddd
#include "tcurves.h"
Toshihiro Shimizu 890ddd
#include "tmathutil.h"
Toshihiro Shimizu 890ddd
#include "tbezier.h"
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//=============================================================================
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
/*
Campbell Barton a6cacc
This function returns a vector of
Campbell Barton a6cacc
pairs of double (DoublePair) which identifies the parameters
Campbell Barton a6cacc
of the points of intersection.
Toshihiro Shimizu 890ddd
Campbell Barton a6cacc
  The integer returned is the number of intersections which
Campbell Barton a6cacc
  have been identified (for two segments).
Shinya Kitaoka 120a6e
Campbell Barton a6cacc
    If the segments are parallel to the parameter it is set to -1.
Toshihiro Shimizu 890ddd
*/
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
int intersect(const TSegment &first, const TSegment &second,
Shinya Kitaoka 120a6e
              std::vector<doublepair> &intersections) {</doublepair>
Shinya Kitaoka 120a6e
  return intersect(first.getP0(), first.getP1(), second.getP0(), second.getP1(),
Shinya Kitaoka 120a6e
                   intersections);
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
int intersect(const TPointD &p1, const TPointD &p2, const TPointD &p3,
Shinya Kitaoka 120a6e
              const TPointD &p4, std::vector<doublepair> &intersections) {</doublepair>
Shinya Kitaoka 120a6e
  // This algorithm is presented in Graphics Geems III pag 199
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  static double Ax, Bx, Ay, By, Cx, Cy, d, f, e;
Shinya Kitaoka 120a6e
  static double x1lo, x1hi, y1lo, y1hi;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  Ax = p2.x - p1.x;
Shinya Kitaoka 120a6e
  Bx = p3.x - p4.x;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // test delle BBox
Shinya Kitaoka 120a6e
  if (Ax < 0.0) {
Shinya Kitaoka 120a6e
    x1lo = p2.x;
Shinya Kitaoka 120a6e
    x1hi = p1.x;
Shinya Kitaoka 120a6e
  } else {
Shinya Kitaoka 120a6e
    x1lo = p1.x;
Shinya Kitaoka 120a6e
    x1hi = p2.x;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  if (Bx > 0.0) {
Shinya Kitaoka 120a6e
    if (x1hi < p4.x || x1lo > p3.x) return 0;
Shinya Kitaoka 120a6e
  } else if (x1hi < p3.x || x1lo > p4.x)
Shinya Kitaoka 120a6e
    return 0;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  Ay = p2.y - p1.y;
Shinya Kitaoka 120a6e
  By = p3.y - p4.y;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  if (Ay < 0) {
Shinya Kitaoka 120a6e
    y1lo = p2.y;
Shinya Kitaoka 120a6e
    y1hi = p1.y;
Shinya Kitaoka 120a6e
  } else {
Shinya Kitaoka 120a6e
    y1lo = p1.y;
Shinya Kitaoka 120a6e
    y1hi = p2.y;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  if (By > 0) {
Shinya Kitaoka 120a6e
    if (y1hi < p4.y || y1lo > p3.y) return 0;
Shinya Kitaoka 120a6e
  } else if (y1hi < p3.y || y1lo > p4.y)
Shinya Kitaoka 120a6e
    return 0;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  Cx = p1.x - p3.x;
Shinya Kitaoka 120a6e
  Cy = p1.y - p3.y;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  d = By * Cx - Bx * Cy;
Shinya Kitaoka 120a6e
  f = Ay * Bx - Ax * By;
Shinya Kitaoka 120a6e
  e = Ax * Cy - Ay * Cx;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  if (f > 0) {
Shinya Kitaoka 120a6e
    if (d < 0) return 0;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    if (!areAlmostEqual(d, f))
Shinya Kitaoka 120a6e
      if (d > f) return 0;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    if (e < 0) return 0;
Shinya Kitaoka 120a6e
    if (!areAlmostEqual(e, f))
Shinya Kitaoka 120a6e
      if (e > f) return 0;
Shinya Kitaoka 120a6e
  } else if (f < 0) {
Shinya Kitaoka 120a6e
    if (d > 0) return 0;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    if (!areAlmostEqual(d, f))
Shinya Kitaoka 120a6e
      if (d < f) return 0;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    if (e > 0) return 0;
Shinya Kitaoka 120a6e
    if (!areAlmostEqual(e, f))
Shinya Kitaoka 120a6e
      if (e < f) return 0;
Shinya Kitaoka 120a6e
  } else {
Shinya Kitaoka 120a6e
    if (d < 0 || d > 1 || e < 0 || e > 1) return 0;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    if (p1 == p2 && p3 == p4) {
Shinya Kitaoka 120a6e
      intersections.push_back(DoublePair(0, 0));
Shinya Kitaoka 120a6e
      return 1;
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
Campbell Barton a6cacc
    // Check that the segments are not on the same line.
Shinya Kitaoka 120a6e
    if (!cross(p2 - p1, p4 - p1)) {
Campbell Barton a6cacc
      // Calculation of Barycentric combinations.
Shinya Kitaoka 120a6e
      double distp2p1 = norm2(p2 - p1);
Shinya Kitaoka 120a6e
      double distp3p4 = norm2(p3 - p4);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      double dist2_p3p1 = norm2(p3 - p1);
Shinya Kitaoka 120a6e
      double dist2_p4p1 = norm2(p4 - p1);
Shinya Kitaoka 120a6e
      double dist2_p3p2 = norm2(p3 - p2);
Shinya Kitaoka 120a6e
      double dist2_p4p2 = norm2(p4 - p2);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      int intersection = 0;
Shinya Kitaoka 120a6e
Campbell Barton a6cacc
      // Calculation of the first two solutions.
Shinya Kitaoka 120a6e
      double vol1;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      if (distp3p4) {
Shinya Kitaoka 120a6e
        distp3p4 = sqrt(distp3p4);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
        vol1 = (p1 - p3) * normalize(p4 - p3);
Shinya Kitaoka 120a6e
Campbell Barton a6cacc
        if (vol1 >= 0 && vol1 <= distp3p4)  // Barycentric combinations valid
Shinya Kitaoka 120a6e
        {
Shinya Kitaoka 120a6e
          intersections.push_back(DoublePair(0.0, vol1 / distp3p4));
Shinya Kitaoka 120a6e
          ++intersection;
Shinya Kitaoka 120a6e
        }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
        vol1 = (p2 - p3) * normalize(p4 - p3);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
        if (vol1 >= 0 && vol1 <= distp3p4) {
Shinya Kitaoka 120a6e
          intersections.push_back(DoublePair(1.0, vol1 / distp3p4));
Shinya Kitaoka 120a6e
          ++intersection;
Shinya Kitaoka 120a6e
        }
Shinya Kitaoka 120a6e
      }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      if (distp2p1) {
Shinya Kitaoka 120a6e
        distp2p1 = sqrt(distp2p1);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
        vol1 = (p3 - p1) * normalize(p2 - p1);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
        if (dist2_p3p2 && dist2_p3p1)
Shinya Kitaoka 120a6e
          if (vol1 >= 0 && vol1 <= distp2p1) {
Shinya Kitaoka 120a6e
            intersections.push_back(DoublePair(vol1 / distp2p1, 0.0));
Shinya Kitaoka 120a6e
            ++intersection;
Shinya Kitaoka 120a6e
          }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
        vol1 = (p4 - p1) * normalize(p2 - p1);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
        if (dist2_p4p2 && dist2_p4p1)
Shinya Kitaoka 120a6e
          if (vol1 >= 0 && vol1 <= distp2p1) {
Shinya Kitaoka 120a6e
            intersections.push_back(DoublePair(vol1 / distp2p1, 1.0));
Shinya Kitaoka 120a6e
            ++intersection;
Shinya Kitaoka 120a6e
          }
Shinya Kitaoka 120a6e
      }
Shinya Kitaoka 120a6e
      return intersection;
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
    return -1;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  double par_s = d / f;
Shinya Kitaoka 120a6e
  double par_t = e / f;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  intersections.push_back(DoublePair(par_s, par_t));
Shinya Kitaoka 120a6e
  return 1;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//------------------------------------------------------------------------------------------------------------
Shinya Kitaoka 120a6e
int intersectCloseControlPoints(const TQuadratic &c0, const TQuadratic &c1,
Shinya Kitaoka 120a6e
                                std::vector<doublepair> &intersections);</doublepair>
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
int intersect(const TQuadratic &c0, const TQuadratic &c1,
Shinya Kitaoka 120a6e
              std::vector<doublepair> &intersections, bool checksegments) {</doublepair>
Shinya Kitaoka 120a6e
  int ret;
Shinya Kitaoka 120a6e
Campbell Barton a6cacc
  // Works baddly, sometimes patch intersections...
Shinya Kitaoka 120a6e
  if (checksegments) {
Shinya Kitaoka 120a6e
    ret = intersectCloseControlPoints(c0, c1, intersections);
Shinya Kitaoka 120a6e
    if (ret != -2) return ret;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  double a = c0.getP0().x - 2 * c0.getP1().x + c0.getP2().x;
Shinya Kitaoka 120a6e
  double b = 2 * (c0.getP1().x - c0.getP0().x);
Shinya Kitaoka 120a6e
  double d = c0.getP0().y - 2 * c0.getP1().y + c0.getP2().y;
Shinya Kitaoka 120a6e
  double e = 2 * (c0.getP1().y - c0.getP0().y);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  double coeff = b * d - a * e;
Shinya Kitaoka 120a6e
  int i        = 0;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  if (areAlmostEqual(coeff, 0.0))  // c0 is a Segment, or a single point!!!
Shinya Kitaoka 120a6e
  {
Shinya Kitaoka 120a6e
    TSegment s = TSegment(c0.getP0(), c0.getP2());
Shinya Kitaoka 120a6e
    ret        = intersect(s, c1, intersections);
Shinya Kitaoka 120a6e
    if (a == 0 && d == 0)  // values of t in s coincide with values of t in c0
Shinya Kitaoka 120a6e
      return ret;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    for (i = intersections.size() - ret; i < (int)intersections.size(); i++) {
Shinya Kitaoka 120a6e
      intersections[i].first = c0.getT(s.getPoint(intersections[i].first));
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
    return ret;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  double c = c0.getP0().x;
Shinya Kitaoka 120a6e
  double f = c0.getP0().y;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  double g = c1.getP0().x - 2 * c1.getP1().x + c1.getP2().x;
Shinya Kitaoka 120a6e
  double h = 2 * (c1.getP1().x - c1.getP0().x);
Shinya Kitaoka 120a6e
  double k = c1.getP0().x;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  double m = c1.getP0().y - 2 * c1.getP1().y + c1.getP2().y;
Shinya Kitaoka 120a6e
  double p = 2 * (c1.getP1().y - c1.getP0().y);
Shinya Kitaoka 120a6e
  double q = c1.getP0().y;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  if (areAlmostEqual(h * m - g * p,
Shinya Kitaoka 120a6e
                     0.0))  // c1 is a Segment, or a single point!!!
Shinya Kitaoka 120a6e
  {
Shinya Kitaoka 120a6e
    TSegment s = TSegment(c1.getP0(), c1.getP2());
Shinya Kitaoka 120a6e
    ret        = intersect(c0, s, intersections);
Shinya Kitaoka 120a6e
    if (g == 0 && m == 0)  // values of t in s coincide with values of t in c0
Shinya Kitaoka 120a6e
      return ret;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    for (i = intersections.size() - ret; i < (int)intersections.size(); i++) {
Shinya Kitaoka 120a6e
      intersections[i].second = c1.getT(s.getPoint(intersections[i].second));
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
    return ret;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  double a2 = (g * d - a * m);
Shinya Kitaoka 120a6e
  double b2 = (h * d - a * p);
Shinya Kitaoka 120a6e
  double c2 = ((k - c) * d + (f - q) * a);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  coeff = 1.0 / coeff;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  double A   = (a * a + d * d) * coeff * coeff;
Shinya Kitaoka 120a6e
  double aux = A * c2 + (a * b + d * e) * coeff;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  std::vector<double> t;</double>
Shinya Kitaoka 120a6e
  std::vector<double> solutions;</double>
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  t.push_back(aux * c2 + a * c + d * f - k * a - d * q);
Shinya Kitaoka 120a6e
  aux += A * c2;
Shinya Kitaoka 120a6e
  t.push_back(aux * b2 - h * a - d * p);
Shinya Kitaoka 120a6e
  t.push_back(aux * a2 + A * b2 * b2 - g * a - d * m);
Shinya Kitaoka 120a6e
  t.push_back(2 * A * a2 * b2);
Shinya Kitaoka 120a6e
  t.push_back(A * a2 * a2);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  rootFinding(t, solutions);
Shinya Kitaoka 120a6e
  //  solutions.push_back(0.0); //per convenzione; un valore vale l'altro....
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  for (i = 0; i < (int)solutions.size(); i++) {
Shinya Kitaoka 120a6e
    if (solutions[i] < 0) {
Shinya Kitaoka 120a6e
      if (areAlmostEqual(solutions[i], 0, 1e-6))
Shinya Kitaoka 120a6e
        solutions[i] = 0;
Shinya Kitaoka 120a6e
      else
Shinya Kitaoka 120a6e
        continue;
Shinya Kitaoka 120a6e
    } else if (solutions[i] > 1) {
Shinya Kitaoka 120a6e
      if (areAlmostEqual(solutions[i], 1, 1e-6))
Shinya Kitaoka 120a6e
        solutions[i] = 1;
Shinya Kitaoka 120a6e
      else
Shinya Kitaoka 120a6e
        continue;
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    DoublePair tt;
Shinya Kitaoka 120a6e
    tt.second = solutions[i];
Shinya Kitaoka 120a6e
    tt.first  = coeff * (tt.second * (a2 * tt.second + b2) + c2);
Shinya Kitaoka 120a6e
    if (tt.first < 0) {
Shinya Kitaoka 120a6e
      if (areAlmostEqual(tt.first, 0, 1e-6))
Shinya Kitaoka 120a6e
        tt.first = 0;
Shinya Kitaoka 120a6e
      else
Shinya Kitaoka 120a6e
        continue;
Shinya Kitaoka 120a6e
    } else if (tt.first > 1) {
Shinya Kitaoka 120a6e
      if (areAlmostEqual(tt.first, 1, 1e-6))
Shinya Kitaoka 120a6e
        tt.first = 1;
Shinya Kitaoka 120a6e
      else
Shinya Kitaoka 120a6e
        continue;
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    intersections.push_back(tt);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    assert(areAlmostEqual(c0.getPoint(tt.first), c1.getPoint(tt.second), 1e-1));
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
  return intersections.size();
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//=============================================================================
Campbell Barton a6cacc
// This function checks whether the control point
Campbell Barton a6cacc
// p1 is very close to p0 or p2.
Campbell Barton a6cacc
// In this case, we are approximated to the quadratic p0-p2 segment.
shun-iwasawa 7cd1ff
// If p1 is near p0, the relationship between the original and the quadratic
shun-iwasawa 7cd1ff
// segment:
Campbell Barton a6cacc
//     tq = sqrt(ts),
Campbell Barton a6cacc
// If p1 is near p2, instead it's:
Campbell Barton a6cacc
//     tq = 1-sqrt(1-ts).
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
int intersectCloseControlPoints(const TQuadratic &c0, const TQuadratic &c1,
Shinya Kitaoka 120a6e
                                std::vector<doublepair> &intersections) {</doublepair>
Shinya Kitaoka 120a6e
  int ret = -2;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  double dist1          = tdistance2(c0.getP0(), c0.getP1());
Shinya Kitaoka 120a6e
  if (dist1 == 0) dist1 = 1e-20;
Shinya Kitaoka 120a6e
  double dist2          = tdistance2(c0.getP1(), c0.getP2());
Shinya Kitaoka 120a6e
  if (dist2 == 0) dist2 = 1e-20;
Shinya Kitaoka 120a6e
  double val0           = std::max(dist1, dist2) / std::min(dist1, dist2);
Shinya Kitaoka 120a6e
  double dist3          = tdistance2(c1.getP0(), c1.getP1());
Shinya Kitaoka 120a6e
  if (dist3 == 0) dist3 = 1e-20;
Shinya Kitaoka 120a6e
  double dist4          = tdistance2(c1.getP1(), c1.getP2());
Shinya Kitaoka 120a6e
  if (dist4 == 0) dist4 = 1e-20;
Shinya Kitaoka 120a6e
  double val1           = std::max(dist3, dist4) / std::min(dist3, dist4);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  if (val0 > 1000000 &&
Campbell Barton a6cacc
      val1 > 1000000)  // both c0 and c1 approximated by segments
Toshihiro Shimizu 890ddd
  {
Shinya Kitaoka 120a6e
    TSegment s0 = TSegment(c0.getP0(), c0.getP2());
Shinya Kitaoka 120a6e
    TSegment s1 = TSegment(c1.getP0(), c1.getP2());
Shinya Kitaoka 120a6e
    ret         = intersect(s0, s1, intersections);
Shinya Kitaoka 120a6e
    for (UINT i = intersections.size() - ret; i < (int)intersections.size();
Shinya Kitaoka 120a6e
         i++) {
Shinya Kitaoka 120a6e
      intersections[i].first = (dist1 < dist2)
Shinya Kitaoka 120a6e
                                   ? sqrt(intersections[i].first)
Shinya Kitaoka 120a6e
                                   : 1 - sqrt(1 - intersections[i].first);
Shinya Kitaoka 120a6e
      intersections[i].second = (dist3 < dist4)
Shinya Kitaoka 120a6e
                                    ? sqrt(intersections[i].second)
Shinya Kitaoka 120a6e
                                    : 1 - sqrt(1 - intersections[i].second);
Toshihiro Shimizu 890ddd
    }
Shinya Kitaoka 120a6e
    // return ret;
Campbell Barton a6cacc
  } else if (val0 > 1000000)  // c0 only approximated segment
Shinya Kitaoka 120a6e
  {
Shinya Kitaoka 120a6e
    TSegment s0 = TSegment(c0.getP0(), c0.getP2());
Shinya Kitaoka 120a6e
    ret         = intersect(s0, c1, intersections);
Shinya Kitaoka 120a6e
    for (UINT i = intersections.size() - ret; i < (int)intersections.size();
Shinya Kitaoka 120a6e
         i++)
Shinya Kitaoka 120a6e
      intersections[i].first = (dist1 < dist2)
Shinya Kitaoka 120a6e
                                   ? sqrt(intersections[i].first)
Shinya Kitaoka 120a6e
                                   : 1 - sqrt(1 - intersections[i].first);
Shinya Kitaoka 120a6e
    // return ret;
Campbell Barton a6cacc
  } else if (val1 > 1000000)  // only c1 approximated segment
Shinya Kitaoka 120a6e
  {
Shinya Kitaoka 120a6e
    TSegment s1 = TSegment(c1.getP0(), c1.getP2());
Shinya Kitaoka 120a6e
    ret         = intersect(c0, s1, intersections);
Shinya Kitaoka 120a6e
    for (UINT i = intersections.size() - ret; i < (int)intersections.size();
Shinya Kitaoka 120a6e
         i++)
Shinya Kitaoka 120a6e
      intersections[i].second = (dist3 < dist4)
Shinya Kitaoka 120a6e
                                    ? sqrt(intersections[i].second)
Shinya Kitaoka 120a6e
                                    : 1 - sqrt(1 - intersections[i].second);
Shinya Kitaoka 120a6e
    // return ret;
Toshihiro Shimizu 890ddd
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  /*
Shinya Kitaoka 120a6e
if (ret!=-2)
Shinya Kitaoka 120a6e
{
Shinya Kitaoka 120a6e
std::vector<doublepair> intersections1;</doublepair>
Shinya Kitaoka 120a6e
int ret1 = intersect(c0, c1, intersections1, false);
Shinya Kitaoka 120a6e
if (ret1>ret)
Shinya Kitaoka 120a6e
{
Shinya Kitaoka 120a6e
intersections = intersections1;
Shinya Kitaoka 120a6e
return ret1;
Shinya Kitaoka 120a6e
}
Shinya Kitaoka 120a6e
}
Toshihiro Shimizu 890ddd
*/
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  return ret;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//=============================================================================
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
int intersect(const TQuadratic &q, const TSegment &s,
Shinya Kitaoka 120a6e
              std::vector<doublepair> &intersections, bool firstIsQuad) {</doublepair>
Shinya Kitaoka 120a6e
  int solutionNumber = 0;
Shinya Kitaoka 120a6e
Campbell Barton a6cacc
  // Note the line `a*x+b*y+c = 0` we search for solutions
Shinya Kitaoka 120a6e
  //  di a*x(t)+b*y(t)+c=0 in [0,1]
Shinya Kitaoka 120a6e
  double a = s.getP0().y - s.getP1().y, b = s.getP1().x - s.getP0().x,
Shinya Kitaoka 120a6e
         c = -(a * s.getP0().x + b * s.getP0().y);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // se il segmento e' un punto
Shinya Kitaoka 120a6e
  if (0.0 == a && 0.0 == b) {
Shinya Kitaoka 120a6e
    double outParForQuad = q.getT(s.getP0());
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    if (areAlmostEqual(q.getPoint(outParForQuad), s.getP0())) {
Shinya Kitaoka 120a6e
      if (firstIsQuad)
Shinya Kitaoka 120a6e
        intersections.push_back(DoublePair(outParForQuad, 0));
Shinya Kitaoka 120a6e
      else
Shinya Kitaoka 120a6e
        intersections.push_back(DoublePair(0, outParForQuad));
Shinya Kitaoka 120a6e
      return 1;
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
    return 0;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  if (q.getP2() - q.getP1() ==
Campbell Barton a6cacc
      q.getP1() - q.getP0()) {  // the second is a segment....
Shinya Kitaoka 120a6e
    if (firstIsQuad)
Shinya Kitaoka 120a6e
      return intersect(TSegment(q.getP0(), q.getP2()), s, intersections);
Shinya Kitaoka 120a6e
    else
Shinya Kitaoka 120a6e
      return intersect(s, TSegment(q.getP0(), q.getP2()), intersections);
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  std::vector<tpointd> bez, pol;</tpointd>
Shinya Kitaoka 120a6e
  bez.push_back(q.getP0());
Shinya Kitaoka 120a6e
  bez.push_back(q.getP1());
Shinya Kitaoka 120a6e
  bez.push_back(q.getP2());
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  bezier2poly(bez, pol);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  std::vector<double> poly_1(3, 0), sol;</double>
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  poly_1[0] = a * pol[0].x + b * pol[0].y + c;
Shinya Kitaoka 120a6e
  poly_1[1] = a * pol[1].x + b * pol[1].y;
Shinya Kitaoka 120a6e
  poly_1[2] = a * pol[2].x + b * pol[2].y;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  if (!(rootFinding(poly_1, sol))) return 0;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  double segmentPar, solution;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  TPointD v10(s.getP1() - s.getP0());
Shinya Kitaoka 120a6e
  for (UINT i = 0; i < sol.size(); ++i) {
Shinya Kitaoka 120a6e
    solution = sol[i];
Shinya Kitaoka 120a6e
    if ((0.0 <= solution && solution <= 1.0) ||
Shinya Kitaoka 120a6e
        areAlmostEqual(solution, 0.0, 1e-6) ||
Shinya Kitaoka 120a6e
        areAlmostEqual(solution, 1.0, 1e-6)) {
Shinya Kitaoka 120a6e
      segmentPar = (q.getPoint(solution) - s.getP0()) * v10 / (v10 * v10);
Shinya Kitaoka 120a6e
      if ((0.0 <= segmentPar && segmentPar <= 1.0) ||
Shinya Kitaoka 120a6e
          areAlmostEqual(segmentPar, 0.0, 1e-6) ||
Shinya Kitaoka 120a6e
          areAlmostEqual(segmentPar, 1.0, 1e-6)) {
Shinya Kitaoka 120a6e
        TPointD p1 = q.getPoint(solution);
Shinya Kitaoka 120a6e
        TPointD p2 = s.getPoint(segmentPar);
Shinya Kitaoka 120a6e
        assert(areAlmostEqual(p1, p2, 1e-1));
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
        if (firstIsQuad)
Shinya Kitaoka 120a6e
          intersections.push_back(DoublePair(solution, segmentPar));
Shinya Kitaoka 120a6e
        else
Shinya Kitaoka 120a6e
          intersections.push_back(DoublePair(segmentPar, solution));
Shinya Kitaoka 120a6e
        solutionNumber++;
Shinya Kitaoka 120a6e
      }
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  return solutionNumber;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//=============================================================================
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
bool isCloseToSegment(const TPointD &point, const TSegment &segment,
Shinya Kitaoka 120a6e
                      double distance) {
Shinya Kitaoka 120a6e
  TPointD a      = segment.getP0();
Shinya Kitaoka 120a6e
  TPointD b      = segment.getP1();
MCCCS a0ce32
  double length2 = tdistance2(a, b);
MCCCS a0ce32
  if (length2 < tdistance2(a, point) || length2 < tdistance2(point, b))
Shinya Kitaoka 120a6e
    return false;
Shinya Kitaoka 120a6e
  if (a.x == b.x) return fabs(point.x - a.x) <= distance;
Shinya Kitaoka 120a6e
  if (a.y == b.y) return fabs(point.y - a.y) <= distance;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // y=mx+q
Shinya Kitaoka 120a6e
  double m = (a.y - b.y) / (a.x - b.x);
Shinya Kitaoka 120a6e
  double q = a.y - (m * a.x);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  double d2 = pow(fabs(point.y - (m * point.x) - q), 2) / (1 + (m * m));
Shinya Kitaoka 120a6e
  return d2 <= distance * distance;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//=============================================================================
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
double tdistance(const TSegment &segment, const TPointD &point) {
Shinya Kitaoka 120a6e
  TPointD v1 = segment.getP1() - segment.getP0();
Shinya Kitaoka 120a6e
  TPointD v2 = point - segment.getP0();
Shinya Kitaoka 120a6e
  TPointD v3 = point - segment.getP1();
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  if (v2 * v1 <= 0)
Shinya Kitaoka 120a6e
    return tdistance(point, segment.getP0());
Shinya Kitaoka 120a6e
  else if (v3 * v1 >= 0)
Shinya Kitaoka 120a6e
    return tdistance(point, segment.getP1());
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  return fabs(v2 * rotate90(normalize(v1)));
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//-----------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
/*
luz paz 266edb
This formula is derived from Graphic Gems pag. 600
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
  e = h^2 |a|/8
Shinya Kitaoka 120a6e
Toshihiro Shimizu 890ddd
    e = pixel size
Toshihiro Shimizu 890ddd
    h = step
luz paz 67b4e9
    a = acceleration of curve (for a quadratic is a constant value)
Toshihiro Shimizu 890ddd
*/
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
double computeStep(const TQuadratic &quad, double pixelSize) {
Shinya Kitaoka 120a6e
  double step = 2;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  TPointD A = quad.getP0() - 2.0 * quad.getP1() +
Shinya Kitaoka 120a6e
              quad.getP2();  // 2*A is the acceleration of the curve
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  double A_len = norm(A);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  /*
Shinya Kitaoka 120a6e
A_len is equal to 2*norm(a)
Shinya Kitaoka 120a6e
pixelSize will be 0.5*pixelSize
Shinya Kitaoka 120a6e
now h is equal to sqrt( 8 * 0.5 * pixelSize / (2*norm(a)) ) = sqrt(2) * sqrt(
Shinya Kitaoka 120a6e
pixelSize/A_len )
Shinya Kitaoka 120a6e
*/
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  if (A_len > 0) step = sqrt(2 * pixelSize / A_len);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  return step;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//-----------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
double computeStep(const TThickQuadratic &quad, double pixelSize) {
Shinya Kitaoka 120a6e
  TThickPoint cp0 = quad.getThickP0(), cp1 = quad.getThickP1(),
Shinya Kitaoka 120a6e
              cp2 = quad.getThickP2();
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  TQuadratic q1(TPointD(cp0.x, cp0.y), TPointD(cp1.x, cp1.y),
Shinya Kitaoka 120a6e
                TPointD(cp2.x, cp2.y)),
Shinya Kitaoka 120a6e
      q2(TPointD(cp0.y, cp0.thick), TPointD(cp1.y, cp1.thick),
Shinya Kitaoka 120a6e
         TPointD(cp2.y, cp2.thick)),
Shinya Kitaoka 120a6e
      q3(TPointD(cp0.x, cp0.thick), TPointD(cp1.x, cp1.thick),
Shinya Kitaoka 120a6e
         TPointD(cp2.x, cp2.thick));
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  return std::min({computeStep(q1, pixelSize), computeStep(q2, pixelSize),
Shinya Kitaoka 120a6e
                   computeStep(q3, pixelSize)});
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//=============================================================================
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
/*
Toshihiro Shimizu 890ddd
  Explanation: The length of a Bezier quadratic can be calculated explicitly.
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
  Let Q be the quadratic. The tricks to explicitly integrate | Q'(t) | are:
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
    - The integrand can be reformulated as:  | Q'(t) | = sqrt(at^2 + bt + c);
Toshihiro Shimizu 890ddd
    - Complete the square beneath the sqrt (add/subtract sq(b) / 4a)
Shinya Kitaoka 120a6e
      and perform a linear variable change. We reduce the integrand to:
Shinya Kitaoka 120a6e
  sqrt(kx^2 + k),
Toshihiro Shimizu 890ddd
      where k can be taken outside => sqrt(x^2 + 1)
Toshihiro Shimizu 890ddd
    - Use x = tan y. The integrand will yield sec^3 y.
Toshihiro Shimizu 890ddd
    - Integrate by parts. In short, the resulting primitive of sqrt(x^2 + 1) is:
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
        F(x) = ( x * sqrt(x^2 + 1) + log(x + sqrt(x^2 + 1)) ) / 2;
Toshihiro Shimizu 890ddd
*/
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
void TQuadraticLengthEvaluator::setQuad(const TQuadratic &quad) {
Shinya Kitaoka 120a6e
  const TPointD &p0 = quad.getP0();
Shinya Kitaoka 120a6e
  const TPointD &p1 = quad.getP1();
Shinya Kitaoka 120a6e
  const TPointD &p2 = quad.getP2();
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  TPointD speed0(2.0 * (p1 - p0));
Shinya Kitaoka 120a6e
  TPointD accel(2.0 * (p2 - p1) - speed0);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  double a = accel * accel;
Shinya Kitaoka 120a6e
  double b = 2.0 * accel * speed0;
Shinya Kitaoka 120a6e
  m_c      = speed0 * speed0;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  m_constantSpeed = isAlmostZero(a);  // => b isAlmostZero, too
Shinya Kitaoka 120a6e
  if (m_constantSpeed) {
Shinya Kitaoka 120a6e
    m_c = sqrt(m_c);
Shinya Kitaoka 120a6e
    return;
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  m_sqrt_a_div_2 = 0.5 * sqrt(a);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  m_noSpeed0 = isAlmostZero(m_c);  // => b isAlmostZero, too
Shinya Kitaoka 120a6e
  if (m_noSpeed0) return;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  m_tRef   = 0.5 * b / a;
Shinya Kitaoka 120a6e
  double d = m_c - 0.5 * b * m_tRef;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  m_squareIntegrand = (d < TConsts::epsilon);
Shinya Kitaoka 120a6e
  if (m_squareIntegrand) {
Shinya Kitaoka 120a6e
    m_f = (b > 0) ? -sq(m_tRef) : sq(m_tRef);
Shinya Kitaoka 120a6e
    return;
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  m_e = d / a;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  double sqrt_part = sqrt(sq(m_tRef) + m_e);
Shinya Kitaoka 120a6e
  double log_arg   = m_tRef + sqrt_part;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  m_squareIntegrand = (log_arg < TConsts::epsilon);
Shinya Kitaoka 120a6e
  if (m_squareIntegrand) {
Shinya Kitaoka 120a6e
    m_f = (b > 0) ? -sq(m_tRef) : sq(m_tRef);
Shinya Kitaoka 120a6e
    return;
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  m_primitive_0 = m_sqrt_a_div_2 * (m_tRef * sqrt_part + m_e * log(log_arg));
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//-----------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
double TQuadraticLengthEvaluator::getLengthAt(double t) const {
Shinya Kitaoka 120a6e
  if (m_constantSpeed) return m_c * t;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  if (m_noSpeed0) return m_sqrt_a_div_2 * sq(t);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  if (m_squareIntegrand) {
Shinya Kitaoka 120a6e
    double t_plus_tRef = t + m_tRef;
Shinya Kitaoka 120a6e
    return m_sqrt_a_div_2 *
Shinya Kitaoka 120a6e
           (m_f + ((t_plus_tRef > 0) ? sq(t_plus_tRef) : -sq(t_plus_tRef)));
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  double y         = t + m_tRef;
Shinya Kitaoka 120a6e
  double sqrt_part = sqrt(sq(y) + m_e);
Shinya Kitaoka 120a6e
  double log_arg =
Shinya Kitaoka 120a6e
      y + sqrt_part;  // NOTE: log_arg >= log_arg0 >= TConsts::epsilon
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  return m_sqrt_a_div_2 * (y * sqrt_part + m_e * log(log_arg)) - m_primitive_0;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//-----------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
//  End Of File
Toshihiro Shimizu 890ddd
//-----------------------------------------------------------------------------