Initial bring-back of line to line intersection detection.

[architektonas] / src / line.cpp

// line.cpp: Line object
//
// Part of the Architektonas Project
// (C) 2011 Underground Software
// See the README and GPLv3 files for licensing and warranty information
//
// JLH = James Hammons <jlhamm@acm.org>
//
// WHO  WHEN        WHAT
// ---  ----------  ------------------------------------------------------------
// JLH  03/22/2011  Created this file
// JLH  04/11/2011  Fixed attached dimensions to stay at correct length when
//                  "Fixed Length" button is down
// JLH  04/27/2011  Fixed attached dimension to stay a correct length when
//                  "Fixed Length" button is *not* down ;-)
// JLH  05/29/2011  Added (some) mouseover hints
//

#include "line.h"

#include <QtGui>
#include "container.h"
#include "dimension.h"
#include "geometry.h"
#include "mathconstants.h"
#include "painter.h"


Line::Line(Vector p1, Vector p2, Object * p/*= NULL*/): Object(p1, p),
        /*type(OTLine),*/ endpoint(p2),
        draggingLine(false), draggingHandle1(false), draggingHandle2(false), //needUpdate(false),
        length(Vector::Magnitude(p2, p1)), angle(Vector(endpoint - position).Unit()),
        hitPoint1(false), hitPoint2(false), hitLine(false)
{
        type = OTLine;
}


Line::~Line()
{
// Taking care of connections should be done by the Container, as we don't know
// anything about any other object connected to this one.
#if 0
        // If there are any attached Dimensions, we must set the attachment points
        // to NULL since they will no longer be valid.
        if (attachedDimension)
        {
                attachedDimension->SetPoint1(NULL);
                attachedDimension->SetPoint2(NULL);
        }
        // IT WOULD BE NICE to have any object points attached to this line automagically
        // connect to this dimension object at this point, instead of just becoming
        // detached.
#endif
//actually not true, we know the object pointer and parameter!
//actuall, the Object base class does this for us...!
#if 0
        std::vector<Connection>::iterator i;

        for(i=connected.begin(); i!=connected.end(); i++)
        {
                (*i).object->Disconnect(this, (*i).t);
        }
#endif
}


/*virtual*/ void Line::Draw(Painter * painter)
{
        painter->SetPen(QPen(Qt::red, 2.0, Qt::DotLine));

        if ((state == OSSelected) || ((state == OSInactive) && hitPoint1))
                painter->DrawHandle(position);

        if ((state == OSSelected) || ((state == OSInactive) && hitPoint2))
                painter->DrawHandle(endpoint);

        if ((state == OSInactive) && !hitLine)
                painter->SetPen(QPen(Qt::black, 1.0, Qt::SolidLine));

        if (Object::fixedLength && (draggingHandle1 || draggingHandle2))
        {
                Vector point1 = (draggingHandle1 ? endpoint : position);
                Vector point2 = (draggingHandle1 ? position : endpoint);

                Vector current(point2 - point1);
                Vector v = current.Unit() * length;
                Vector v2 = point1 + v;
                painter->DrawLine(point1, v2);

                if (current.Magnitude() > length)
                {
                        painter->SetPen(QPen(QColor(128, 0, 0), 1.0, Qt::DashLine));
                        painter->DrawLine(v2, point2);
                }
        }
        else
                painter->DrawLine(position, endpoint);

        // If we're dragging an endpoint, draw an information panel showing both
        // the length and angle being set.
        if (draggingHandle1 || draggingHandle2)
        {
                double absAngle = (Vector(endpoint - position).Angle()) * RADIANS_TO_DEGREES;
                double absLength = Vector(position - endpoint).Magnitude();

                QString text = QObject::tr("Length: %1 in.\n") + QChar(0x2221) + QObject::tr(": %2");
                text = text.arg(absLength).arg(absAngle);
                painter->DrawInformativeText(text);
        }
}

/*virtual*/ Vector Line::Center(void)
{
        // Technically, this is the midpoint but who are we to quibble? :-)
        Vector v((position.x - endpoint.x) / 2.0, (position.y - endpoint.y) / 2.0);
        return endpoint + v;
}

/*virtual*/ bool Line::Collided(Vector point)
{
/*
what we can do here is set ignoreClicks to true to keep other objects that are
selected from deselecting themselves. Will that fuck up something else? Not sure
yet... :-/
Actually, this is done here to keep tools from selecting stuff inadvertantly...
*/
        // We can assume this, since this is a mouse down event here.
        objectWasDragged = false;
        bool hit = HitTest(point);

        // Someone told us to fuck off, so we'll fuck off. :-)
        if (ignoreClicks)
                return hit;

        // Now that we've done our hit testing on the non-snapped point, snap it if
        // necessary...
        if (snapToGrid)
                point = SnapPointToGrid(point);

        if (snapPointIsValid)
                point = snapPoint;

// this is shite. this should be checked for in the Container, not here!
#warning "!!! This should be checked for in Container, not here !!!"
        // If we're part of a non-top-level container, send this signal to it
        if (parent->type == OTContainer && !((Container *)parent)->isTopLevelContainer
                && (hitLine || hitPoint1 || hitPoint2))
        {
                parent->state = OSSelected;
                return true;
        }

        if (state == OSInactive)
        {
//How to translate this into pixels from Document space???
//Maybe we need to pass a scaling factor in here from the caller? That would
//make sense, as the caller knows about the zoom factor and all that good kinda
//crap
//I think what's needed is an Object class variable/method that can be changed
//by the TLC and called in derived classes to properly scale the location to
//the current zoom level. That *should* work.

// ALSO: Need to code a global (read: Object class) variable that tells use
//       whether a modifier key was pressed in addition to the mouse click, so
//       we can do stuff like, say, hold down CTRL and be able to do multiple
//       selecting of objects (in that case, we would keep the Object state
//       from changing).
                if (hitPoint1)
                {
                        oldState = state;
                        state = OSSelected;
                        oldPoint = position;
                        draggingHandle1 = true;
                        return true;
                }
                else if (hitPoint2)
                {
                        oldState = state;
                        state = OSSelected;
                        oldPoint = endpoint;
                        draggingHandle2 = true;
                        return true;
                }
                else if (hitLine)
                {
                        oldState = state;
                        state = OSSelected;
                        oldPoint = point;
                        draggingLine = true;
                        return true;
                }
        }
        else if (state == OSSelected)
        {
                if (hitLine)
                {
                        oldState = state;
//                      state = OSInactive;
                        oldPoint = point;
                        draggingLine = true;

                        // Toggle selected state if CTRL held
                        if (qApp->keyboardModifiers() == Qt::ControlModifier)
                                state = OSInactive;

                        return true;
                }
        }

        // If CTRL is held, then we bypass the "turn off" code. Still didn't hit
        // *this* object though. :-)
        if (qApp->keyboardModifiers() == Qt::ControlModifier)
                return false;

        // If we got here, we clicked on nothing, so set the object to inactive.
        // (Once we can read key modifiers, we can override this to allow multiple selection.)
        state = OSInactive;
        return false;
}


/*virtual*/ bool Line::PointerMoved(Vector point)
{
        if (selectionInProgress)
        {
                // Check for whether or not the rect contains this line
                if (selection.contains(position.x, position.y)
                        && selection.contains(endpoint.x, endpoint.y))
                        state = OSSelected;
                else
                        state = OSInactive;

                return false;
        }

        // Hit test tells us what we hit (if anything) through boolean variables.
        SaveHitState();
        bool hovered = HitTest(point);
        needUpdate = HitStateChanged();

        if (snapToGrid)
                point = SnapPointToGrid(point);

        if (snapPointIsValid)
                point = snapPoint;

        objectWasDragged = (draggingLine | draggingHandle1 | draggingHandle2);

        if (objectWasDragged)
        {
                Vector delta = point - oldPoint;

                if (draggingHandle1 || draggingLine)
                        position += delta;

                if (draggingHandle2 || draggingLine)
                        endpoint += delta;

                oldPoint = point;
                needUpdate = true;

//doesn't work          QMainWindow::statusBar()->setText("You are manipulating a line");

                // Tell connected objects to move themselves...
                if (draggingLine)
                {
                        std::vector<Connection>::iterator i;

                        for(i=connected.begin(); i!=connected.end(); i++)
                        {
                                if ((*i).object->type == OTLine)
                                        ((Line *)((*i).object))->MovePointAtParameter((*i).t, delta);
                                else if ((*i).object->type == OTDimension)
                                        ((Dimension *)((*i).object))->MovePointAtParameter((*i).t, delta);
                        }
                }
        }

/*
We can't count on any coupling between the dimension object and us, so how do we do this???
Also, there may be more than one Dimension object connected to a single endpoint!

Ugly ways to do it:
 - Keep track of the state of the connected dimension
 - Pass the Dimension the point that's being changed and the delta

More elegant ways:
 - Pass the point in a notification function (how?)
 - Pass the point as a reference to the class instance object (&endpoint). This
   way, the line doesn't have to care about keeping track of Dimensions
   connected to it. But still have to care about other connected entities
   (other Lines, Circles, Arcs, Splines, Texts, etc). I think I'd be OK with
   this. Since the Dimension has a pointer to our object, all we have to do is
   update our coordinates and the Dimension object will adjust itself on the
   next repaint. Problem solved, and we don't have to know anything about how
   many Dimensions are connected to us, or where! \o/
   The question then becomes, how do we do this kind of coupling???

We need to know about connected entities so that we can have them either move
in expected ways or constrain the movement of this Line object. This is how we
will be a cut above all other CAD software currently out there: the GUI will
try to do the right thing, most of the time. :-)
*/
        if (needUpdate)
        {
// should only do this if "Fixed Length" is set... !!! FIX !!! [DONE]
                Vector point1 = (draggingHandle1 ? endpoint : position);
                Vector point2 = (draggingHandle1 ? position : endpoint);

                if (Object::fixedAngle)
                {
                        // Here we calculate the component of the current vector along the fixed angle.
                        // A_compB = (A . Bu) * Bu
                        double magnitudeAlongB = Vector::Dot(Vector(point2 - point1), angle);
/*
Actually, this isn't quite right. What we want to do is look for the intersection along either
the horizontal line or vertical line that intersects from the current mouse position.
*/

                        if (draggingHandle1)
                                position = endpoint + (angle * magnitudeAlongB);

                        if (draggingHandle2)
                                endpoint = position + (angle * magnitudeAlongB);
                }
//              else
//                      v2 = point2;

//If we tell the dimension to flip sides, this is no longer a valid
//assumption. !!! FIX !!!
//Ideally, we should just send the point that's changing to the Dimension object
//and have it figure out which point needs to move... Or is it???
// Ideally, we shouldn't have to fuck around with this shit. We need to fix the rendering code
// so that we don't have to wait until the dragging is done to correct the position of the
// point in question, but we'd need another variable tho.
#if 0
                if (dimPoint1)
                        dimPoint1->SetPoint1(draggingHandle1 ? v2 : position);
                
                if (dimPoint2)
                        dimPoint2->SetPoint2(draggingHandle2 ? v2 : endpoint);
#endif
        }

        return hovered;
}


/*virtual*/ void Line::PointerReleased(void)
{
        if (draggingHandle1 || draggingHandle2)
        {
                // Set the length (in case the global state was set to fixed (or not))
                if (Object::fixedLength)
                {
                        if (draggingHandle1)    // startpoint
                        {
                                Vector v = Vector(position - endpoint).Unit() * length;
                                position = endpoint + v;
                        }
                        else                                    // endpoint
                        {
                                Vector v = Vector(endpoint - position).Unit() * length;
                                endpoint = position + v;
                        }
                }
                else
                {
                        // Otherwise, we calculate the new length, just in case on the next
                        // move it turns out to have a fixed length. :-)
                        length = Vector(endpoint - position).Magnitude();
                }

                if (!Object::fixedAngle)
                {
                        // Calculate the new angle, just in case on the next move it turns
                        // out to be fixed. :-)
                        angle = Vector(endpoint - position).Unit();
                }
        }

        draggingLine = false;
        draggingHandle1 = false;
        draggingHandle2 = false;

        if (objectWasDragged)
                state = oldState;
}


/*virtual*/ bool Line::HitTest(Point point)
{
        hitPoint1 = hitPoint2 = hitLine = false;
        Vector lineSegment = endpoint - position;
        Vector v1 = point - position;
        Vector v2 = point - endpoint;
        Vector v3 = point - Center();   // Midpoint, for snapping...
        double t = Geometry::ParameterOfLineAndPoint(position, endpoint, point);
        double distance;

        // Geometric interpretation of "distance = ?Det?(ls, v1) / |ls|":
        // If the segment endpoints are s and e, and the point is p, then the test
        // for the perpendicular intercepting the segment is equivalent to insisting
        // that the two dot products {s-e}.{s-p} and {e-s}.{e-p} are both non-negative.
        // Perpendicular distance from the point to the segment is computed by first
        // computing the area of the triangle the three points form, then dividing by
        // the length of the segment.  Distances are done just by the Pythagorean
        // theorem. Twice the area of the triangle formed by three points is the
        // determinant of the following matrix:
        //
        // sx sy 1       0  0  1       0  0  0
        // ex ey 1  ==>  ex ey 1  ==>  ex ey 0
        // px py 1       px py 1       px py 0
        //
        // By translating the start point to the origin, and subtracting row 1 from
        // all other rows, we end up with the matrix on the right which greatly
        // simplifies the calculation of the determinant.

        if (t < 0.0)
                distance = v1.Magnitude();
        else if (t > 1.0)
                distance = v2.Magnitude();
        else
                // distance = ?Det?(ls, v1) / |ls|
                distance = fabs((lineSegment.x * v1.y - v1.x * lineSegment.y)
                        / lineSegment.Magnitude());

        if ((v1.Magnitude() * Painter::zoom) < 8.0)
        {
                hitPoint1 = true;
                snapPoint = position;
                snapPointIsValid = true;
        }
        else if ((v2.Magnitude() * Painter::zoom) < 8.0)
        {
                hitPoint2 = true;
                snapPoint = endpoint;
                snapPointIsValid = true;
        }
        else if ((distance * Painter::zoom) < 5.0)
                hitLine = true;

        // Not a manipulation point, but a snapping point:
        if ((v3.Magnitude() * Painter::zoom) < 8.0)
        {
                snapPoint = Center();
                snapPointIsValid = true;
        }

        return (hitPoint1 || hitPoint2 || hitLine ? true : false);
}


// Check to see if the point passed in coincides with any we have. If so, return a
// pointer to it; otherwise, return NULL.
/*virtual*/ Vector * Line::GetPointAt(Vector v)
{
        if (v == position)
                return &position;
        else if (v == endpoint)
                return &endpoint;

        return 0;
}


/*virtual*/ void Line::Enumerate(FILE * file)
{
        fprintf(file, "LINE %i (%lf,%lf) (%lf,%lf)\n", layer, position.x, position.y, endpoint.x, endpoint.y);
}


/*virtual*/ Object * Line::Copy(void)
{
#warning "!!! This doesn't take care of attached Dimensions !!!"
/*
This is a real problem. While having a pointer in the Dimension to this line's points
is fast & easy, it creates a huge problem when trying to replicate an object like this.

Maybe a way to fix that then, is to have reference numbers instead of pointers. That
way, if you copy them, ... you might still have problems. Because you can't be sure if
a copy will be persistant or not, you then *definitely* do not want them to have the
same reference number.
*/
        return new Line(position, endpoint, parent);
}


/*virtual*/ Vector Line::GetPointAtParameter(double parameter)
{
// Is there any real reason to clamp this to the endpoints?
// (hey, whaddya know? this was masking a bug!)
#if 0
        if (parameter <= 0)
                return position;
        else if (parameter >= 1.0)
                return endpoint;
#endif

        // The parameter is a percentage of the length of the vector, so all we
        // have to do is scale the vector by it to find the point.
        return position + (Vector(position, endpoint) * parameter);
}


/*virtual*/ void Line::MovePointAtParameter(double parameter, Vector v)
{
        if (parameter == 0)
                position += v;
        else if (parameter == 1.0)
                endpoint += v;
        else
                {} // Not sure how to handle this case :-P
}


/*virtual*/ QRectF Line::Extents(void)
{
        QRectF rect(QPointF(position.x, position.y), QPointF(endpoint.x, endpoint.y));
        return rect.normalized();
}


/*virtual*/ void Line::Translate(Vector amount)
{
        position += amount;
        endpoint += amount;
}


/*virtual*/ void Line::Rotate(Point point, double angle)
{
        Point l1 = Geometry::RotatePointAroundPoint(position, point, angle);
        Point l2 = Geometry::RotatePointAroundPoint(endpoint, point, angle);
        position = l1;
        endpoint = l2;
}


/*virtual*/ void Line::Scale(Point point, double amount)
{
}


/*virtual*/ void Line::Mirror(Point p1, Point p2)
{
        Point l1 = Geometry::MirrorPointAroundLine(position, p1, p2);
        Point l2 = Geometry::MirrorPointAroundLine(endpoint, p1, p2);
        position = l1;
        endpoint = l2;
}


/*virtual*/ void Line::Save(void)
{
        Object::Save();
        oldEndpoint = endpoint;
}


/*virtual*/ void Line::Restore(void)
{
        Object::Restore();
        endpoint = oldEndpoint;
}


void Line::SetDimensionOnLine(Dimension * dimension/*= NULL*/)
{
        // If they don't pass one in, create it for the caller.
        // But ONLY if this line has a parent container!
        // This is really bad to do here, it should be done in the parent container, always!
#warning "!!! Parent container should be creating Dimension object !!!"
        if ((dimension == NULL) && (parent != NULL))
        {
//printf("Line::SetDimensionOnLine(): Creating new dimension...\n");
                dimension = new Dimension(position, endpoint, DTLinear, parent);
//              dimension = new Dimension(Connection(this, 0), Connection(this, 1.0), DTLinear, this);

                // THIS IS SERIOUS!!! WITHOUT A PARENT, THIS OBJECT IS IN LIMBO!!!
//              if (parent)
//{
//printf("Line::SetDimensionOnLine(): Adding to parent...\n");
                parent->Add(dimension);
//}
        }

        dimension->Connect(this, 0);
        dimension->Connect(this, 1.0);

        // Make sure the Dimension is connected to us...
        Connect(dimension, 0);
        Connect(dimension, 1.0);

        dimension->position = position;
        dimension->endpoint = endpoint;
}


Object * Line::FindAttachedDimension(void)
{
        // Is there anything connected to this line? If not, return NULL
        if (connected.size() < 2)
                return NULL;

        // Otherwise, we have to search our objects to see if there's a likely
        // candidate. In this case, we're looking for a pointer to the same object
        // with a parameter of 0 and 1 respectively. This is O((n^2)/2).
        for(uint i=0; i<connected.size(); i++)
        {
                for(uint j=i+1; j<connected.size(); j++)
                {
//printf("Line: connected[i]=%X, connected[j]=%X, connected[i].t=%lf, connected[j].t=%lf\n", connected[i].object, connected[j].object, connected[i].t, connected[j].t);
                        if ((connected[i].object == connected[j].object)
                                && ((connected[i].t == 0 && connected[j].t == 1.0)
                                || (connected[i].t == 1.0 && connected[j].t == 0)))
                                return connected[i].object;
                }
        }

        // Didn't find anything, so return NULL
        return NULL;
}


void Line::SaveHitState(void)
{
        oldHitPoint1 = hitPoint1;
        oldHitPoint2 = hitPoint2;
        oldHitLine = hitLine;
}


bool Line::HitStateChanged(void)
{
        if ((hitPoint1 != oldHitPoint1) || (hitPoint2 != oldHitPoint2) || (hitLine != oldHitLine))
                return true;

        return false;
}


/*
Intersection of two lines:

Find where the lines with equations r = i + j + t (3i - j) and r = -i + s (j) intersect.

When they intersect, we can set the equations equal to one another:

i + j + t (3i - j) = -i + s (j)

Equating coefficients:
1 + 3t = -1 and 1 - t = s
So t = -2/3 and s = 5/3

The position vector of the intersection point is therefore given by putting t = -2/3 or s = 5/3 into one of the above equations. This gives -i +5j/3 .


so, let's say we have two lines, l1 and l2. Points are v0(p0x, p0y), v1(p1x, p1y) for l1
and v2(p2x, p2y), v3(p3x, p3y) for l2.

d1 = v1 - v0, d2 = v3 - v2

Our parametric equations for the line then are:

r1 = v0 + t(d1)
r2 = v2 + s(d2)

Set r1 = r2, thus we have:

v0 + t(d1) = v2 + s(d2)

Taking coefficients, we have:

p0x + t(d1x) = p2x + s(d2x)
p0y + t(d1y) = p2y + s(d2y)

rearranging we get:

t(d1x) - s(d2x) = p2x - p0x
t(d1y) - s(d2y) = p2y - p0y

Determinant D is ad - bc where the matrix looks like:

a b
c d

so D = (d1x)(d2y) - (d2x)(d1y)
if D = 0, the lines are parallel.
Dx = (p2x - p0x)(d2y) - (d2x)(p2y - p0y)
Dy = (d1x)(p2y - p0y) - (p2x - p0x)(d1y)
t = Dx/D, s = Dy/D

We only need to calculate t, as we can then multiply it by d1 to get the intersection point.

---------------------------------------------------------------------------------------------------

The first and most preferred method for intersection calculation is the perp-product calculation. There are two vectors, v1 and v2. Create a third vector vector between the starting points of these vectors, and calculate the perp product of v2 and the two other vectors. These two scalars have to be divided to get the mulitplication ratio of v1 to reach intersection point. So:

v1 ( bx1 , by1 );
v2 ( bx2 , by2 );
v3 ( bx3 , by3 );

Perp product is equal with dot product of normal of first vector and the second vector, so we need normals:

n1 ( -by1 , bx1 );
n3 ( -by3 , bx3 );

Dot products:

dp1 = n3 . v2 = -by3 * bx2 + bx3 * by2;
dp2 = n1 . v2 = -by1 * bx2 + bx1 * by2;

ratio = dp1 / dp2;
crossing vector = v1 * ratio;

And that's it.

-----------------------------------

So... to code this, let's say we have two Lines: l1 & l2.

Vector v1 = l1.endpoint - l1.position;
Vector v2 = l2.endpoint - l2.position;
Vector v3 = v2 - v1;

Vector normal1(-v1.y, v1.x);
Vector normal3(-v3.y, v3.x);

double dotProduct1 = v2.Dot(normal1);
double dotProduct2 = v2.Dot(normal3);

if (dotProduct2 == 0)
        return ParallelLines;
else
{
        // I think we'd still have to add the intersection to the position point to get the intersection...
        Point intersection = v1 * (dotProduct1 / dotProduct2);
        return intersection;
}
*/