rs_information.cpp

qcad2.05可用于windows和linux的源码

 */
RS_VectorSolutions RS_Information::getIntersectionLineArc(RS_Line* line,
        RS_Arc* arc) {

    RS_VectorSolutions ret;

    if (line==NULL || arc==NULL) {
        return ret;
    }

    double dist=0.0;
    RS_Vector nearest;
    nearest = line->getNearestPointOnEntity(arc->getCenter(), false, &dist);

    // special case: arc touches line (tangent):
    if (fabs(dist - arc->getRadius()) < 1.0e-4) {
        ret = RS_VectorSolutions(nearest);
        ret.setTangent(true);
        return ret;
    }

    RS_Vector p = line->getStartpoint();
    RS_Vector d = line->getEndpoint() - line->getStartpoint();
    if (d.magnitude()<1.0e-6) {
        return ret;
    }

    RS_Vector c = arc->getCenter();
    double r = arc->getRadius();
    RS_Vector delta = p - c;

    // root term:
    double term = RS_Math::pow(RS_Vector::dotP(d, delta), 2.0)
                  - RS_Math::pow(d.magnitude(), 2.0)
                  * (RS_Math::pow(delta.magnitude(), 2.0) - RS_Math::pow(r, 2.0));

    // no intersection:
    if (term<0.0) {
        RS_VectorSolutions s;
        ret = s;
    }

    // one or two intersections:
    else {
        double t1 = (- RS_Vector::dotP(d, delta) + sqrt(term))
                    / RS_Math::pow(d.magnitude(), 2.0);
        double t2;
        bool tangent = false;

        // only one intersection:
        if (fabs(term)<RS_TOLERANCE) {
            t2 = t1;
            tangent = true;
        }

        // two intersections
        else {
            t2 = (-RS_Vector::dotP(d, delta) - sqrt(term))
                 / RS_Math::pow(d.magnitude(), 2.0);
        }

        RS_Vector sol1;
        RS_Vector sol2(false);

        sol1 = p + d * t1;

        if (!tangent) {
            sol2 = p + d * t2;
        }

        ret = RS_VectorSolutions(sol1, sol2);
        ret.setTangent(tangent);
    }

    return ret;
}



/**
 * @return One or two intersection points between given entities.
 */
RS_VectorSolutions RS_Information::getIntersectionArcArc(RS_Arc* e1,
        RS_Arc* e2) {

    RS_VectorSolutions ret;

    if (e1==NULL || e2==NULL) {
        return ret;
    }

    RS_Vector c1 = e1->getCenter();
    RS_Vector c2 = e2->getCenter();

    double r1 = e1->getRadius();
    double r2 = e2->getRadius();

    RS_Vector u = c2 - c1;

    // concentric
    if (u.magnitude()<1.0e-6) {
        return ret;
    }

    RS_Vector v = RS_Vector(u.y, -u.x);

    double s, t1, t2, term;

    s = 1.0/2.0 * ((r1*r1 - r2*r2)/(RS_Math::pow(u.magnitude(), 2.0)) + 1.0);

    term = (r1*r1)/(RS_Math::pow(u.magnitude(), 2.0)) - s*s;

    // no intersection:
    if (term<0.0) {
        ret = RS_VectorSolutions();
    }

    // one or two intersections:
    else {
        t1 = sqrt(term);
        t2 = -sqrt(term);
        bool tangent = false;

        RS_Vector sol1 = c1 + u*s + v*t1;
        RS_Vector sol2 = c1 + u*s + v*t2;

        if (sol1.distanceTo(sol2)<1.0e-4) {
            sol2 = RS_Vector(false);
            ret = RS_VectorSolutions(sol1);
            tangent = true;
        } else {
            ret = RS_VectorSolutions(sol1, sol2);
        }

        ret.setTangent(tangent);
    }

    return ret;
}



/**
 * @return One or two intersection points between given entities.
 */
RS_VectorSolutions RS_Information::getIntersectionLineEllipse(RS_Line* line,
        RS_Ellipse* ellipse) {

    RS_VectorSolutions ret;

    if (line==NULL || ellipse==NULL) {
        return ret;
    }

    // rotate into normal position:
    double ang = ellipse->getAngle();

    double rx = ellipse->getMajorRadius();
    double ry = ellipse->getMinorRadius();
    RS_Vector center = ellipse->getCenter();
    RS_Vector a1 = line->getStartpoint().rotate(center, -ang);
    RS_Vector a2 = line->getEndpoint().rotate(center, -ang);
    RS_Vector origin = a1;
    RS_Vector dir = a2-a1;
    RS_Vector diff = origin - center;
    RS_Vector mDir = RS_Vector(dir.x/(rx*rx), dir.y/(ry*ry));
    RS_Vector mDiff = RS_Vector(diff.x/(rx*rx), diff.y/(ry*ry));

    double a = RS_Vector::dotP(dir, mDir);
    double b = RS_Vector::dotP(dir, mDiff);
    double c = RS_Vector::dotP(diff, mDiff) - 1.0;
    double d = b*b - a*c;

    if (d < 0) {
        RS_DEBUG->print("RS_Information::getIntersectionLineEllipse: outside 0");
    } else if ( d > 0 ) {
        double root = sqrt(d);
        double t_a = (-b - root) / a;
        double t_b = (-b + root) / a;

        /*if ( (t_a < 0 || 1 < t_a) && (t_b < 0 || 1 < t_b) ) {
            if ( (t_a < 0 && t_b < 0) || (t_a > 1 && t_b > 1) ) {
                RS_DEBUG->print("RS_Information::getIntersectionLineEllipse: outside 1");
            }
            else {
                RS_DEBUG->print("RS_Information::getIntersectionLineEllipse: inside 1");
            }
        } else {*/
            RS_DEBUG->print("RS_Information::getIntersectionLineEllipse: intersection 1");
            RS_Vector ret1(false);
            RS_Vector ret2(false);
            //if ( 0 <= t_a && t_a <= 1 ) { 
                //RS_DEBUG->print("RS_Information::getIntersectionLineEllipse: 0<=t_a<=1");
                ret1 = a1.lerp(a2, t_a);
                RS_DEBUG->print("RS_Information::getIntersectionLineEllipse: ret1: %f/%f", ret1.x, ret1.y);
            //}
            //if ( 0 <= t_b && t_b <= 1 ) {
                //RS_DEBUG->print("RS_Information::getIntersectionLineEllipse: 0<=t_b<=1");
                ret2 = a1.lerp(a2, t_b);
                RS_DEBUG->print("RS_Information::getIntersectionLineEllipse: ret2: %f/%f", ret2.x, ret2.y);
            //}
            if (ret1.valid && ret2.valid) {
                ret = RS_VectorSolutions(ret1, ret2);
            }
            else {
                if (ret1.valid) {
                    ret = RS_VectorSolutions(ret1);
                }
                if (ret2.valid) {
                    ret = RS_VectorSolutions(ret2);
                }
            }
        //}
    } else {
        double t = -b/a;
        if ( 0 <= t && t <= 1 ) {
            RS_DEBUG->print("RS_Information::getIntersectionLineEllipse: 0<=t<=1");
            RS_DEBUG->print("RS_Information::getIntersectionLineEllipse: intersection 2");
            ret = RS_VectorSolutions(a1.lerp(a2, t));
            RS_DEBUG->print("RS_Information::getIntersectionLineEllipse: ret1: %f/%f", ret.get(0).x, ret.get(0).y);
        } else {
            RS_DEBUG->print("RS_Information::getIntersectionLineEllipse: outside 2");
        }
    }

    ret.rotate(center, ang);
    return ret;



    /*
    RS_Arc* arc = new RS_Arc(NULL,
                             RS_ArcData(ellipse->getCenter(),
                                        ellipse->getMajorRadius(),
                                        ellipse->getAngle1(),
                                        ellipse->getAngle2(),
                                        false));
    RS_Line* other = (RS_Line*)line->clone();
    double angle = ellipse->getAngle();
    //double ratio = ellipse->getRatio();

    // rotate entities:
    other->rotate(ellipse->getCenter(), -angle);
    other->scale(ellipse->getCenter(), RS_Vector(1.0, 1.0/ellipse->getRatio()));

    ret = getIntersectionLineArc(other, arc);

    ret.scale(ellipse->getCenter(), RS_Vector(1.0, ellipse->getRatio()));
    ret.rotate(ellipse->getCenter(), angle);

    delete arc;
    delete other;

    return ret;
    */
}


/**
 * Checks if the given coordinate is inside the given contour.
 *
 * @param point Coordinate to check.
 * @param contour One or more entities which shape a contour.
 *         If the given contour is not closed, the result is undefined.
 *         The entities don't need to be in a specific order.
 * @param onContour Will be set to true if the given point it exactly
 *         on the contour.
 */
bool RS_Information::isPointInsideContour(const RS_Vector& point,
        RS_EntityContainer* contour, bool* onContour) {

    if (contour==NULL) {
        RS_DEBUG->print(RS_Debug::D_WARNING,
			"RS_Information::isPointInsideContour: contour is NULL");
        return false;
    }

    if (point.x < contour->getMin().x || point.x > contour->getMax().x ||
            point.y < contour->getMin().y || point.y > contour->getMax().y) {
        return false;
    }

    double width = contour->getSize().x+1.0;

    bool sure;
    int counter;
    int tries = 0;
    double rayAngle = 0.0;
    do {
        sure = true;

        // create ray:
        RS_Vector v;
        v.setPolar(width*10.0, rayAngle);
        RS_Line ray(NULL, RS_LineData(point, point+v));
        counter = 0;
        RS_VectorSolutions sol;

        if (onContour!=NULL) {
            *onContour = false;
        }

        for (RS_Entity* e = contour->firstEntity(RS2::ResolveAll);
                e!=NULL;
                e = contour->nextEntity(RS2::ResolveAll)) {

            // intersection(s) from ray with contour entity:
            sol = RS_Information::getIntersection(&ray, e, true);

            for (int i=0; i<=1; ++i) {
                RS_Vector p = sol.get(i);

                if (p.valid) {
                    // point is on the contour itself
                    if (p.distanceTo(point)<1.0e-5) {
                        if (onContour!=NULL) {
                            *onContour = true;
                        }
                    } else {
                        if (e->rtti()==RS2::EntityLine) {
                            RS_Line* line = (RS_Line*)e;

                            // ray goes through startpoint of line:
                            if (p.distanceTo(line->getStartpoint())<1.0e-4) {
                                if (RS_Math::correctAngle(line->getAngle1())<M_PI) {
                                    counter++;
                                    sure = false;
                                }
                            }

                            // ray goes through endpoint of line:
                            else if (p.distanceTo(line->getEndpoint())<1.0e-4) {
                                if (RS_Math::correctAngle(line->getAngle2())<M_PI) {
                                    counter++;
                                    sure = false;
                                }
                            }
                            // ray goes through the line:


                            else {
                                counter++;
                            }
                        } else if (e->rtti()==RS2::EntityArc) {
                            RS_Arc* arc = (RS_Arc*)e;

                            if (p.distanceTo(arc->getStartpoint())<1.0e-4) {
                                double dir = arc->getDirection1();
                                if ((dir<M_PI && dir>=1.0e-5) ||
                                        ((dir>2*M_PI-1.0e-5 || dir<1.0e-5) &&
                                         arc->getCenter().y>p.y)) {
                                    counter++;
                                    sure = false;
                                }
                            }
                            else if (p.distanceTo(arc->getEndpoint())<1.0e-4) {
                                double dir = arc->getDirection2();
                                if ((dir<M_PI && dir>=1.0e-5) ||
                                        ((dir>2*M_PI-1.0e-5 || dir<1.0e-5) &&
                                         arc->getCenter().y>p.y)) {
                                    counter++;
                                    sure = false;
                                }
                            } else {
                                counter++;
                            }
                        } else if (e->rtti()==RS2::EntityCircle) {
                            // tangent:
                            if (i==0 && sol.get(1).valid==false) {
                                if (!sol.isTangent()) {
                                    counter++;
                                } else {
                                    sure = false;
                                }
                            } else if (i==1 || sol.get(1).valid==true) {
                                counter++;
                            }
                        }
                    }
                }
            }
        }

        rayAngle+=0.02;
        tries++;
    }
    while (!sure && rayAngle<2*M_PI && tries<6);

    // remove double intersections:
    /*
       RS_PtrList<RS_Vector> is2;
       bool done;
    RS_Vector* av;
       do {
           done = true;
           double minDist = RS_MAXDOUBLE;
           double dist;
    	av = NULL;
           for (RS_Vector* v = is.first(); v!=NULL; v = is.next()) {
               dist = point.distanceTo(*v);
               if (dist<minDist) {
                   minDist = dist;
                   done = false;
    			av = v;
               }
           }

    	if (!done && av!=NULL) {
    		is2.append(*av);
    	}
       } while (!done);
    */

    return ((counter%2)==1);
}