Shape.cpp File Reference

Go to the source code of this file.

Functions
bool	directedEulerian (Shape const *s)
	A directed graph is Eulerian iff every vertex has equal indegree and outdegree.
double	distance (Shape const *s, Geom::Point const &p)
bool	distanceLessThanOrEqual (Shape const *s, Geom::Point const &p, double const max_l2)
	Returns true iff the L2 distance from thePt to this shape is <= max_l2.

---

Function Documentation

bool directedEulerian

(

Shape const *

s

)

A directed graph is Eulerian iff every vertex has equal indegree and outdegree.

http://mathworld.wolfram.com/EulerianGraph.html

Parameters:

s

Directed shape.

Returns:

true if s is Eulerian.

Definition at line 2174 of file Shape.cpp.

References Shape::getPoint(), Barcode::Code39Ext::i, and Shape::numberOfPoints().

Referenced by Shape::Booleen(), Shape::ConvertToShape(), and Shape::Reoriente().

{
    for (int i = 0; i < s->numberOfPoints(); i++) {
        if (s->getPoint(i).dI != s->getPoint(i).dO) {
            return false;
        }
    }

    return true;
}

double distance	(	Shape const *	s,
		Geom::Point const &	p
	)

Parameters:

	s	Shape.
	p	Point.

Returns:

Minimum distance from p to any of the points or edges of s.

Definition at line 2193 of file Shape.cpp.

References NR::cross(), NR::d, Geom::dot(), addnodes::e, Shape::getEdge(), Shape::getPoint(), Shape::hasPoints(), Barcode::Code39Ext::i, Shape::numberOfEdges(), Shape::numberOfPoints(), pathalongpath::offset(), Geom::sqrt(), and voronoi::x.

{
    if ( s->hasPoints() == false) {
        return 0.0;
    }

    /* Find the minimum distance from p to one of the points on s.
    ** Computing the dot product of the difference vector gives
    ** us the distance squared; we can leave the square root
    ** until the end.
    */
    double bdot = Geom::dot(p - s->getPoint(0).x, p - s->getPoint(0).x);

    for (int i = 0; i < s->numberOfPoints(); i++) {
        Geom::Point const offset( p - s->getPoint(i).x );
        double ndot = Geom::dot(offset, offset);
        if ( ndot < bdot ) {
            bdot = ndot;
        }
    }

    for (int i = 0; i < s->numberOfEdges(); i++) {
        if ( s->getEdge(i).st >= 0 && s->getEdge(i).en >= 0 ) {
            /* The edge has start and end points */
            Geom::Point const st(s->getPoint(s->getEdge(i).st).x); // edge start
            Geom::Point const en(s->getPoint(s->getEdge(i).en).x); // edge end

            Geom::Point const d(p - st);       // vector between p and edge start
            Geom::Point const e(en - st);      // vector of the edge
            double const el = Geom::dot(e, e); // edge length

            /* Update bdot if appropriate */
            if ( el > 0.001 ) {
                double const npr = Geom::dot(d, e);
                if ( npr > 0 && npr < el ) {
                    double const nl = fabs( NR::cross(d, e) );
                    double ndot = nl * nl / el;
                    if ( ndot < bdot ) {
                        bdot = ndot;
                    }
                }
            }
        }
    }
    
    return sqrt(bdot);
}

bool distanceLessThanOrEqual	(	Shape const *	s,
		Geom::Point const &	p,
		double const	max_l2
	)

Returns true iff the L2 distance from thePt to this shape is <= max_l2.

Distance = the min of distance to its points and distance to its edges. Points without edges are considered, which is maybe unwanted...

This is largely similar to distance().

Parameters:

	s	Shape.
	p	Point.
	max_l2	L2 distance.

Definition at line 2255 of file Shape.cpp.

References NR::cross(), NR::d, Geom::dot(), addnodes::e, Shape::getEdge(), Shape::getPoint(), Shape::hasPoints(), Barcode::Code39Ext::i, NR::L1(), Geom::L2(), Shape::numberOfEdges(), Shape::numberOfPoints(), pathalongpath::offset(), and voronoi::x.

{
    if ( s->hasPoints() == false ) {
        return false;
    }
    
    /* TODO: Consider using bbox to return early, perhaps conditional on nbPt or nbAr. */
    
    /* TODO: Efficiency: In one test case (scribbling with the freehand tool to create a small number of long
    ** path elements), changing from a Distance method to a DistanceLE method reduced this
    ** function's CPU time from about 21% of total inkscape CPU time to 14-15% of total inkscape
    ** CPU time, due to allowing early termination.  I don't know how much the L1 test helps, it
    ** may well be a case of premature optimization.  Consider testing dot(offset, offset)
    ** instead.
    */
  
    double const max_l1 = max_l2 * M_SQRT2;
    for (int i = 0; i < s->numberOfPoints(); i++) {
        Geom::Point const offset( p - s->getPoint(i).x );
        double const l1 = NR::L1(offset);
        if ( (l1 <= max_l2) || ((l1 <= max_l1) && (Geom::L2(offset) <= max_l2)) ) {
            return true;
        }
    }
    
    for (int i = 0; i < s->numberOfEdges(); i++) {
        if ( s->getEdge(i).st >= 0 && s->getEdge(i).en >= 0 ) {
            Geom::Point const st(s->getPoint(s->getEdge(i).st).x);
            Geom::Point const en(s->getPoint(s->getEdge(i).en).x);
            Geom::Point const d(p - st);
            Geom::Point const e(en - st);
            double const el = Geom::L2(e);
            if ( el > 0.001 ) {
                Geom::Point const e_unit(e / el);
                double const npr = Geom::dot(d, e_unit);
                if ( npr > 0 && npr < el ) {
                    double const nl = fabs(NR::cross(d, e_unit));
                    if ( nl <= max_l2 ) {
                        return true;
                    }
                }
            }
        }
    }
    
    return false;
}