You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
307 lines
9.0 KiB
307 lines
9.0 KiB
/***************************************************************************
|
|
*
|
|
* Copyright (C) 2005 Elad Lahav (elad_lahav@users.sourceforge.net)
|
|
*
|
|
* Redistribution and use in source and binary forms, with or without
|
|
* modification, are permitted provided that the following conditions
|
|
* are met:
|
|
*
|
|
* 1. Redistributions of source code must retain the above copyright
|
|
* notice, this list of conditions and the following disclaimer.
|
|
* 2. Redistributions in binary form must reproduce the above copyright
|
|
* notice, this list of conditions and the following disclaimer in the
|
|
* documentation and/or other materials provided with the distribution.
|
|
*
|
|
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
|
|
* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
|
|
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
|
|
* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
|
|
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
|
|
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
|
|
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
|
|
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
|
|
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
|
|
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
|
*
|
|
***************************************************************************/
|
|
|
|
#include <math.h>
|
|
#include <stdlib.h>
|
|
#include <tqpainter.h>
|
|
#include "graphedge.h"
|
|
#include "graphnode.h"
|
|
|
|
int GraphEdge::RTTI = 1002;
|
|
|
|
// Some definitions required by the ConvexHull class
|
|
typedef int (*CompFunc)(const void*, const void*);
|
|
#define ISLEFT(P0, P1, P2) \
|
|
(P1.x() - P0.x()) * (P2.y() - P0.y()) - \
|
|
(P2.x() - P0.x()) * (P1.y() - P0.y())
|
|
#define FARTHEST(P0, P1, P2) \
|
|
((P1.x() - P0.x()) * (P1.x() - P0.x()) - \
|
|
(P1.y() - P0.y()) * (P1.y() - P0.y())) - \
|
|
((P2.x() - P0.x()) * (P2.x() - P0.x()) - \
|
|
(P2.y() - P0.y()) * (P2.y() - P0.y()))
|
|
|
|
|
|
/**
|
|
* An array of TQPoint objects that can compute the convex hull surrounding all
|
|
* points in the array.
|
|
* @author Elad Lahav
|
|
*/
|
|
class ConvexHull : public TQPointArray
|
|
{
|
|
public:
|
|
/**
|
|
* Class constructor.
|
|
*/
|
|
ConvexHull() : TQPointArray() {}
|
|
|
|
/**
|
|
* Computes the convex hull of the points stored in the array, using
|
|
* Graham's scan.
|
|
* @param arrHull Holds the coordinates of the convex hull, upon return
|
|
*/
|
|
void compute(TQPointArray& arrHull) {
|
|
uint i, nPivot, nTop;
|
|
|
|
// Find the pivot point
|
|
nPivot = 0;
|
|
for (i = 1; i < size(); i++) {
|
|
if ((*this)[i].y() < (*this)[nPivot].y()) {
|
|
nPivot = i;
|
|
}
|
|
else if ((*this)[i].y() == (*this)[nPivot].y() &&
|
|
(*this)[i].x() < (*this)[nPivot].x()) {
|
|
nPivot = i;
|
|
}
|
|
}
|
|
|
|
// Sort points in radial order, relative to the pivot
|
|
s_ptPivot = (*this)[nPivot];
|
|
(*this)[nPivot] = (*this)[0];
|
|
(*this)[0] = s_ptPivot;
|
|
qsort(&(*this).data()[1], (*this).size() - 1, sizeof(TQPoint),
|
|
(CompFunc)compRadial);
|
|
|
|
// Initialise Graham's scan algorithm
|
|
arrHull.resize(size() + 1);
|
|
arrHull[0] = (*this)[0];
|
|
arrHull[1] = (*this)[1];
|
|
nTop = 1;
|
|
|
|
// Compute the convex hull
|
|
for (i = 2; i < size();) {
|
|
// TODO: According to the algorithm, the condition should be >0
|
|
// for pushing the point into the stack. For some reason, it works
|
|
// only with <0. Why?
|
|
if (ISLEFT(arrHull[nTop - 1], arrHull[nTop], (*this)[i]) < 0) {
|
|
arrHull[++nTop] = (*this)[i];
|
|
i++;
|
|
}
|
|
else {
|
|
nTop--;
|
|
}
|
|
}
|
|
|
|
// Close the hull
|
|
arrHull[++nTop] = (*this)[0];
|
|
arrHull.truncate(nTop + 1);
|
|
}
|
|
|
|
private:
|
|
/** The current pivot point, required by compRadial. */
|
|
static TQPoint s_ptPivot;
|
|
|
|
/**
|
|
* Compares two points based on their angle relative to the current
|
|
* pivot point.
|
|
* This function is passed as the comparison function of qsort().
|
|
* @param pPt1 A pointer to the first point
|
|
* @param pPt2 A pointer to the second point
|
|
* @return >0 if the first point is to the left of the second, <0 otherwise
|
|
*/
|
|
static int compRadial(const TQPoint* pPt1, const TQPoint* pPt2) {
|
|
int nResult;
|
|
|
|
// Determine which point is to the left of the other. If the angle is
|
|
// the same, the greater point is the one farther from the pivot
|
|
nResult = ISLEFT(s_ptPivot, (*pPt1), (*pPt2));
|
|
if (nResult == 0)
|
|
return FARTHEST(s_ptPivot, (*pPt1), (*pPt2));
|
|
|
|
return nResult;
|
|
}
|
|
};
|
|
|
|
TQPoint ConvexHull::s_ptPivot;
|
|
|
|
/**
|
|
* Class constructor.
|
|
* @param pCanvas The canvas on which to draw the edge
|
|
* @param pHead The edge's starting point
|
|
* @param pTail The edge's end point
|
|
*/
|
|
GraphEdge::GraphEdge(TQCanvas* pCanvas, GraphNode* pHead, GraphNode* pTail) :
|
|
TQCanvasPolygonalItem(pCanvas),
|
|
m_pHead(pHead),
|
|
m_pTail(pTail),
|
|
m_arrPoly(4)
|
|
{
|
|
}
|
|
|
|
/**
|
|
* Class destructor.
|
|
*/
|
|
GraphEdge::~GraphEdge()
|
|
{
|
|
// Classes derived from TQCanvasPolygonalItem must call hide() in their
|
|
// detructor (according to the TQt documentation)
|
|
hide();
|
|
}
|
|
|
|
/**
|
|
* Calculates the area surrounding the edge, and the bounding rectangle of
|
|
* the edge's polygonal head.
|
|
* The calculated area is used to find items on the canvas and to display
|
|
* tips. The bounding rectangle defines the tip's region (@see TQToolTip).
|
|
* TODO: The function assumes that the we can simply append the polygon's
|
|
* array to that of the splines. Is this always the case, or should we sort
|
|
* the points of the polygon in radial order?
|
|
* @param arrCurve The control points of the edge's spline
|
|
* @param ai Used to calculate the arrow head polygon
|
|
*/
|
|
void GraphEdge::setPoints(const TQPointArray& arrCurve, const ArrowInfo& ai)
|
|
{
|
|
ConvexHull ch;
|
|
uint i;
|
|
int nXpos, nYpos;
|
|
|
|
// Redraw an existing edge
|
|
if (m_arrArea.size() > 0)
|
|
invalidate();
|
|
|
|
// Store the point array for drawing
|
|
m_arrCurve = arrCurve;
|
|
|
|
// Calculate the arrowhead's polygon
|
|
makeArrowhead(ai);
|
|
|
|
// Compute the convex hull of the edge
|
|
ch.resize(m_arrCurve.size() + m_arrPoly.size() - 2);
|
|
ch.putPoints(0, m_arrCurve.size() - 1, m_arrCurve);
|
|
ch.putPoints(m_arrCurve.size() - 1, m_arrPoly.size() - 1, m_arrPoly);
|
|
ch.compute(m_arrArea);
|
|
|
|
// Calculate the head's bounding rectangle
|
|
m_rcTip = TQRect(m_arrPoly[0], m_arrPoly[0]);
|
|
for (i = 1; i < m_arrPoly.size(); i++) {
|
|
nXpos = m_arrPoly[i].x();
|
|
if (nXpos < m_rcTip.left())
|
|
m_rcTip.setLeft(nXpos);
|
|
else if (nXpos > m_rcTip.right())
|
|
m_rcTip.setRight(nXpos);
|
|
|
|
nYpos = m_arrPoly[i].y();
|
|
if (nYpos < m_rcTip.top())
|
|
m_rcTip.setTop(nYpos);
|
|
else if (nYpos > m_rcTip.bottom())
|
|
m_rcTip.setBottom(nYpos);
|
|
}
|
|
}
|
|
|
|
/**
|
|
* Sets the call information associated with this edge.
|
|
* @param sFile The call's file path
|
|
* @param sLine The call's line number
|
|
* @param sText The call's text
|
|
*/
|
|
void GraphEdge::setCallInfo(const TQString& sFile, const TQString& sLine,
|
|
const TQString& sText)
|
|
{
|
|
m_sFile = sFile;
|
|
m_sLine = sLine;
|
|
m_sText = sText;
|
|
}
|
|
|
|
/**
|
|
* Constructs a tool-tip string for this edge.
|
|
* @return The tool-tip text
|
|
*/
|
|
TQString GraphEdge::getTip() const
|
|
{
|
|
TQString sTip;
|
|
|
|
sTip = m_sText + "<br><i>" + m_sFile + "</i>:" + m_sLine;
|
|
return sTip;
|
|
}
|
|
|
|
/**
|
|
* Draws the spline as a sequence of cubic Bezier curves.
|
|
* @param painter Used for drawing the item on the canvas view
|
|
*/
|
|
void GraphEdge::drawShape(TQPainter& painter)
|
|
{
|
|
uint i;
|
|
|
|
// Draw the polygon
|
|
painter.drawConvexPolygon(m_arrPoly);
|
|
|
|
// Draw the Bezier curves
|
|
for (i = 0; i < m_arrCurve.size() - 1; i += 3)
|
|
painter.drawCubicBezier(m_arrCurve, i);
|
|
|
|
#if 0
|
|
// Draws the convex hull of the edge
|
|
TQPen pen = painter.pen();
|
|
TQBrush br = painter.brush();
|
|
painter.setPen(TQPen(TQColor(255, 0, 0)));
|
|
painter.setBrush(TQBrush());
|
|
painter.drawPolygon(m_arrArea);
|
|
painter.setPen(pen);
|
|
painter.setBrush(br);
|
|
#endif
|
|
}
|
|
|
|
/**
|
|
* Computes the coordinates of the edge's arrow head, based on its curve.
|
|
* @param ai Pre-computed values used for all edges
|
|
*/
|
|
void GraphEdge::makeArrowhead(const ArrowInfo& ai)
|
|
{
|
|
TQPoint ptLast, ptPrev;
|
|
double dX1, dY1, dX0, dY0, dX, dY, dDeltaX, dDeltaY, dNormLen;
|
|
|
|
// The arrowhead follows the line from the second last to the last points
|
|
// in the curve
|
|
ptLast = m_arrCurve[m_arrCurve.size() - 1];
|
|
ptPrev = m_arrCurve[m_arrCurve.size() - 2];
|
|
|
|
// The first and last points of the polygon are the end of the curve
|
|
m_arrPoly.setPoint(0, ptLast.x(), ptLast.y());
|
|
m_arrPoly.setPoint(3, ptLast.x(), ptLast.y());
|
|
|
|
// Convert integer points to double precision values
|
|
dX1 = (double)ptLast.x();
|
|
dY1 = (double)ptLast.y();
|
|
dX0 = (double)ptPrev.x();
|
|
dY0 = (double)ptPrev.y();
|
|
|
|
// The values (x1-x0), (y1-y0) and sqrt(1 + tan(theta)^2) are useful
|
|
dDeltaX = dX1 - dX0;
|
|
dDeltaY = dY1 - dY0;
|
|
|
|
// The normalised length of the arrow's sides
|
|
dNormLen = ai.m_dLength / sqrt(dDeltaX * dDeltaX + dDeltaY * dDeltaY);
|
|
|
|
// Compute the other two points
|
|
dX = dX1 - ((dDeltaX - ai.m_dTan * dDeltaY) / ai.m_dSqrt) * dNormLen;
|
|
dY = dY1 - ((dDeltaY + ai.m_dTan * dDeltaX) / ai.m_dSqrt) * dNormLen;
|
|
m_arrPoly.setPoint(1, (int)dX, (int)dY);
|
|
|
|
dX = dX1 - ((dDeltaX + ai.m_dTan * dDeltaY) / ai.m_dSqrt) * dNormLen;
|
|
dY = dY1 - ((dDeltaY - ai.m_dTan * dDeltaX) / ai.m_dSqrt) * dNormLen;
|
|
m_arrPoly.setPoint(2, (int)dX, (int)dY);
|
|
}
|