summaryrefslogtreecommitdiffstats
path: root/src/libvpsc/rectangle.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/libvpsc/rectangle.cpp')
-rw-r--r--src/libvpsc/rectangle.cpp745
1 files changed, 0 insertions, 745 deletions
diff --git a/src/libvpsc/rectangle.cpp b/src/libvpsc/rectangle.cpp
deleted file mode 100644
index f040f4427..000000000
--- a/src/libvpsc/rectangle.cpp
+++ /dev/null
@@ -1,745 +0,0 @@
-/*
- * vim: ts=4 sw=4 et tw=0 wm=0
- *
- * libvpsc - A solver for the problem of Variable Placement with
- * Separation Constraints.
- *
- * Copyright (C) 2005-2008 Monash University
- *
- * This library is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Lesser General Public
- * License as published by the Free Software Foundation; either
- * version 2.1 of the License, or (at your option) any later version.
- * See the file LICENSE.LGPL distributed with the library.
- *
- * This library is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
- *
- * Author(s): Tim Dwyer
-*/
-
-/*
- * @brief Functions to automatically generate constraints for the
- * rectangular node overlap removal problem.
- *
- */
-
-#include <set>
-#include <cstdlib>
-#include <algorithm>
-#include <cstdio>
-
-#include "libvpsc/assertions.h"
-#include "libvpsc/solve_VPSC.h"
-#include "libvpsc/rectangle.h"
-#include "libvpsc/constraint.h"
-#include "libvpsc/variable.h"
-
-#include "libvpsc/isnan.h" /* Include last */
-
-using std::set;
-using std::vector;
-
-namespace vpsc {
-
-double Rectangle::xBorder = 0;
-double Rectangle::yBorder = 0;
-
-std::ostream& operator <<(std::ostream &os, const Rectangle &r) {
- os << "Hue[0.17],Rectangle[{"<<r.getMinX()<<","<<r.getMinY()<<"},{"<<r.getMaxX()<<","<<r.getMaxY()<<"}]";
- return os;
-}
-
-Rectangle::Rectangle(double x, double X, double y, double Y,bool allowOverlap)
- : minX(x),
- maxX(X),
- minY(y),
- maxY(Y),
- overlap(allowOverlap)
-{
- COLA_ASSERT(x<X);
- COLA_ASSERT(y<Y);
- COLA_ASSERT(getMinX()<getMaxX());
- COLA_ASSERT(getMinY()<getMaxY());
-}
-
-Rectangle::Rectangle()
- : minX(1),
- maxX(-1),
- minY(1),
- maxY(-1),
- overlap(false)
-{
- // Creates an invalid Rectangle
-}
-
-bool Rectangle::isValid(void) const
-{
- return ((minX <= maxX) && (minY <= maxY));
-}
-
-Rectangle Rectangle::unionWith(const Rectangle& rhs) const
-{
- if (!isValid())
- {
- return Rectangle(rhs);
- }
- else if (!rhs.isValid())
- {
- return Rectangle(*this);
- }
-
- double newMaxY = std::max(rhs.getMaxY(),maxY);
- double newMinY = std::min(rhs.getMinY(),minY);
- double newMinX = std::min(rhs.getMinX(),minX);
- double newMaxX = std::max(rhs.getMaxX(),maxX);
-
- return Rectangle(newMinX, newMaxX, newMinY, newMaxY);
-}
-
-void Rectangle::reset(unsigned d, double x, double X) {
- if(d==0) {
- minX=x;
- maxX=X;
- } else {
- minY=x;
- maxY=X;
- }
-}
-
-struct Node;
-struct CmpNodePos { bool operator()(const Node* u, const Node* v) const; };
-
-typedef set<Node*,CmpNodePos> NodeSet;
-
-struct Node {
- Variable *v;
- Rectangle *r;
- double pos;
- Node *firstAbove, *firstBelow;
- NodeSet *leftNeighbours, *rightNeighbours;
- Node(Variable *v, Rectangle *r, double p)
- : v(v),r(r),pos(p),
- firstAbove(NULL), firstBelow(NULL),
- leftNeighbours(NULL), rightNeighbours(NULL)
-
- {
- COLA_ASSERT(r->width()<1e40);
- }
- ~Node() {
- delete leftNeighbours;
- delete rightNeighbours;
- }
- void addLeftNeighbour(Node *u) {
- COLA_ASSERT(leftNeighbours!=NULL);
- leftNeighbours->insert(u);
- }
- void addRightNeighbour(Node *u) {
- COLA_ASSERT(rightNeighbours!=NULL);
- rightNeighbours->insert(u);
- }
- void setNeighbours(NodeSet *left, NodeSet *right) {
- leftNeighbours=left;
- rightNeighbours=right;
- for(NodeSet::iterator i=left->begin();i!=left->end();++i) {
- Node *v=*(i);
- v->addRightNeighbour(this);
- }
- for(NodeSet::iterator i=right->begin();i!=right->end();++i) {
- Node *v=*(i);
- v->addLeftNeighbour(this);
- }
- }
-};
-bool CmpNodePos::operator() (const Node* u, const Node* v) const {
- COLA_ASSERT(!isNaN(u->pos));
- COLA_ASSERT(!isNaN(v->pos));
- if (u->pos < v->pos) {
- return true;
- }
- if (v->pos < u->pos) {
- return false;
- }
- return u < v;
-}
-
-NodeSet* getLeftNeighbours(NodeSet &scanline,Node *v) {
- NodeSet *leftv = new NodeSet;
- NodeSet::iterator i=scanline.find(v);
- while(i!=scanline.begin()) {
- Node *u=*(--i);
- if(u->r->overlapX(v->r)<=0) {
- leftv->insert(u);
- return leftv;
- }
- if(u->r->overlapX(v->r)<=u->r->overlapY(v->r)) {
- leftv->insert(u);
- }
- }
- return leftv;
-}
-NodeSet* getRightNeighbours(NodeSet &scanline,Node *v) {
- NodeSet *rightv = new NodeSet;
- NodeSet::iterator i=scanline.find(v);
- for(++i;i!=scanline.end(); ++i) {
- Node *u=*(i);
- if(u->r->overlapX(v->r)<=0) {
- rightv->insert(u);
- return rightv;
- }
- if(u->r->overlapX(v->r)<=u->r->overlapY(v->r)) {
- rightv->insert(u);
- }
- }
- return rightv;
-}
-
-typedef enum {Open, Close} EventType;
-struct Event {
- EventType type;
- Node *v;
- double pos;
- Event(EventType t, Node *v, double p) : type(t),v(v),pos(p) {};
-};
-int compare_events(const void *a, const void *b) {
- Event *ea=*(Event**)a;
- Event *eb=*(Event**)b;
- if(ea->pos==eb->pos) {
- // when comparing opening and closing
- // open must come first
- if(ea->type==Open) return -1;
- return 1;
- } else if(ea->pos > eb->pos) {
- return 1;
- } else if(ea->pos < eb->pos) {
- return -1;
- } else if(isNaN(ea->pos) != isNaN(ea->pos)) {
- /* See comment in CmpNodePos. */
- return ( isNaN(ea->pos)
- ? -1
- : 1 );
- }
- return 0;
-}
-
-/*
- * Prepares constraints in order to apply VPSC horizontally. Assumes
- * variables have already been created.
- * useNeighbourLists determines whether or not a heuristic is used to
- * deciding whether to resolve all overlap in the x pass, or leave some
- * overlaps for the y pass.
- */
-void generateXConstraints(const Rectangles& rs, const Variables& vars,
- Constraints& cs, const bool useNeighbourLists)
-{
- const unsigned n = rs.size();
- COLA_ASSERT(vars.size()>=n);
- Event **events=new Event*[2*n];
- unsigned i,ctr=0;
- for(i=0;i<n;i++) {
- vars[i]->desiredPosition=rs[i]->getCentreX();
- Node *v = new Node(vars[i],rs[i],rs[i]->getCentreX());
- events[ctr++]=new Event(Open,v,rs[i]->getMinY());
- events[ctr++]=new Event(Close,v,rs[i]->getMaxY());
- }
- qsort((Event*)events, (size_t)2*n, sizeof(Event*), compare_events );
-
- NodeSet scanline;
- for(i=0;i<2*n;i++) {
- Event *e=events[i];
- Node *v=e->v;
- if(e->type==Open) {
- scanline.insert(v);
- if(useNeighbourLists) {
- v->setNeighbours(
- getLeftNeighbours(scanline,v),
- getRightNeighbours(scanline,v)
- );
- } else {
- NodeSet::iterator it=scanline.find(v);
- if(it!=scanline.begin()) {
- Node *u=*(--it);
- v->firstAbove=u;
- u->firstBelow=v;
- }
- it=scanline.find(v);
- if(++it!=scanline.end()) {
- Node *u=*it;
- v->firstBelow=u;
- u->firstAbove=v;
- }
- }
- } else {
- size_t result;
- // Close event
- if(useNeighbourLists) {
- for(NodeSet::iterator i=v->leftNeighbours->begin();
- i!=v->leftNeighbours->end();i++
- ) {
- Node *u=*i;
- double sep = (v->r->width()+u->r->width())/2.0;
- cs.push_back(new Constraint(u->v,v->v,sep));
- result=u->rightNeighbours->erase(v);
- COLA_ASSERT(result==1);
- }
-
- for(NodeSet::iterator i=v->rightNeighbours->begin();
- i!=v->rightNeighbours->end();i++
- ) {
- Node *u=*i;
- double sep = (v->r->width()+u->r->width())/2.0;
- cs.push_back(new Constraint(v->v,u->v,sep));
- result=u->leftNeighbours->erase(v);
- COLA_ASSERT(result==1);
- }
- } else {
- Node *l=v->firstAbove, *r=v->firstBelow;
- if(l!=NULL) {
- double sep = (v->r->width()+l->r->width())/2.0;
- cs.push_back(new Constraint(l->v,v->v,sep));
- l->firstBelow=v->firstBelow;
- }
- if(r!=NULL) {
- double sep = (v->r->width()+r->r->width())/2.0;
- cs.push_back(new Constraint(v->v,r->v,sep));
- r->firstAbove=v->firstAbove;
- }
- }
- result=scanline.erase(v);
- COLA_ASSERT(result==1);
- delete v;
- }
- delete e;
- }
- COLA_ASSERT(scanline.size()==0);
- delete [] events;
-}
-
-/*
- * Prepares constraints in order to apply VPSC vertically to remove ALL
- * overlap.
- */
-void generateYConstraints(const Rectangles& rs, const Variables& vars,
- Constraints& cs)
-{
- const unsigned n = rs.size();
- COLA_ASSERT(vars.size()>=n);
- Event **events=new Event*[2*n];
- unsigned ctr=0;
- Rectangles::const_iterator ri=rs.begin(), re=rs.end();
- Variables::const_iterator vi=vars.begin(), ve=vars.end();
- for(;ri!=re&&vi!=ve;++ri,++vi) {
- Rectangle* r=*ri;
- Variable* v=*vi;
- v->desiredPosition=r->getCentreY();
- Node *node = new Node(v,r,r->getCentreY());
- COLA_ASSERT(r->getMinX()<r->getMaxX());
- events[ctr++]=new Event(Open,node,r->getMinX());
- events[ctr++]=new Event(Close,node,r->getMaxX());
- }
- COLA_ASSERT(ri==rs.end());
- qsort((Event*)events, (size_t)2*n, sizeof(Event*), compare_events );
- NodeSet scanline;
-#ifndef NDEBUG
- size_t deletes=0;
-#endif
- for(unsigned i=0;i<2*n;i++) {
- Event *e=events[i];
- Node *v=e->v;
- if(e->type==Open) {
- scanline.insert(v);
- NodeSet::iterator it=scanline.find(v);
- if(it!=scanline.begin()) {
- Node *u=*(--it);
- v->firstAbove=u;
- u->firstBelow=v;
- }
- it=scanline.find(v);
- if(++it!=scanline.end()) {
- Node *u=*it;
- v->firstBelow=u;
- u->firstAbove=v;
- }
- } else {
- // Close event
- Node *l=v->firstAbove, *r=v->firstBelow;
- if(l!=NULL) {
- double sep = (v->r->height()+l->r->height())/2.0;
- cs.push_back(new Constraint(l->v,v->v,sep));
- l->firstBelow=v->firstBelow;
- }
- if(r!=NULL) {
- double sep = (v->r->height()+r->r->height())/2.0;
- cs.push_back(new Constraint(v->v,r->v,sep));
- r->firstAbove=v->firstAbove;
- }
-#ifndef NDEBUG
- deletes++;
- size_t erased=
-#endif
- scanline.erase(v);
- COLA_ASSERT(erased==1);
- delete v;
- }
- delete e;
- }
- COLA_ASSERT(scanline.size()==0);
- COLA_ASSERT(deletes==n);
- delete [] events;
-}
-#include "libvpsc/linesegment.h"
-using namespace linesegment;
-inline bool checkIntersection(
- const LineSegment::IntersectResult result,
- Vector const &intersection,
- RectangleIntersections &ri,
- bool &side, double &sideX, double &sideY) {
- switch(result) {
- case LineSegment::INTERSECTING:
- ri.intersects=side=true;
- sideX=intersection.x_;
- sideY=intersection.y_;
- case LineSegment::PARALLEL:
- case LineSegment::NOT_INTERSECTING:
- return true;
- case LineSegment::COINCIDENT:
- ri.intersects=ri.top=ri.bottom=ri.left=ri.right=false;
- return false;
- }
- return false;
-}
-void Rectangle::
-lineIntersections(double x1, double y1, double x2, double y2, RectangleIntersections &ri) const {
- Vector intersection;
- LineSegment l(Vector(x1,y1),Vector(x2,y2));
- LineSegment top(Vector(getMinX(),getMaxY()),Vector(getMaxX(),getMaxY()));
- if(!checkIntersection(
- l.Intersect(top,intersection),intersection,
- ri,ri.top,ri.topX,ri.topY)) {
- return;
- }
- LineSegment bottom(Vector(getMinX(),getMinY()),Vector(getMaxX(),getMinY()));
- if(!checkIntersection(
- l.Intersect(bottom,intersection),intersection,
- ri,ri.bottom,ri.bottomX,ri.bottomY)) {
- return;
- }
- LineSegment left(Vector(getMinX(),getMinY()),Vector(getMinX(),getMaxY()));
- if(!checkIntersection(
- l.Intersect(left,intersection),intersection,
- ri,ri.left,ri.leftX,ri.leftY)) {
- return;
- }
- LineSegment right(Vector(getMaxX(),getMinY()),Vector(getMaxX(),getMaxY()));
- if(!checkIntersection(
- l.Intersect(right,intersection),intersection,
- ri,ri.right,ri.rightX,ri.rightY)) {
- return;
- }
-}
-static const double ERROR_MARGIN = 1e-4;
-inline bool eq(double a, double b) {
- return fabs(a-b)<ERROR_MARGIN;
- //return a==b;
-}
-/*
-bool Rectangle::inside(double x, double y) const {
- return x>(minX+ERROR_MARGIN) && x<(maxX-ERROR_MARGIN)
- && y>(minY+ERROR_MARGIN) && y<(maxY-ERROR_MARGIN);
-}
-*/
-// p1=(x1,y1),p2=(x2,y2) are points on the boundary. Puts the shortest
-// path round the outside of the rectangle from p1 to p2 into xs, ys.
-void Rectangle::routeAround(double x1, double y1, double x2, double y2,
- std::vector<double> &xs, std::vector<double> &ys) {
- COLA_ASSERT(eq(x1,minX) || eq(x1,maxX) || eq(y1,minY) || eq(y1,maxY));
- COLA_ASSERT(eq(x2,minX) || eq(x2,maxX) || eq(y2,minY) || eq(y2,maxY));
- xs.push_back(x1);
- ys.push_back(y1);
- bool top1=eq(y1,maxY), top2=eq(y2,maxY),
- bottom1=eq(y1,minY), bottom2=eq(y2,minY);
- bool left1=eq(x1,minX), left2=eq(x2,minX),
- right1=eq(x1,maxX), right2=eq(x2,maxX);
- bool leftright = (left1 && right2) || (right1 && left2);
- bool topbottom = (top1 && bottom2) || (bottom1 && top2);
- bool lefttop = (left1 && top2) || (top1 && left2);
- bool righttop = (right1 && top2) || (top1 && right2);
- bool leftbottom = (left1 && bottom2) || (bottom1 && left2);
- bool rightbottom = (right1 && bottom2) || (bottom1 && right2);
- if(lefttop) {
- xs.push_back(minX);
- ys.push_back(maxY);
- } else if(righttop) {
- xs.push_back(maxX);
- ys.push_back(maxY);
- } else if(leftbottom) {
- xs.push_back(minX);
- ys.push_back(minY);
- } else if(rightbottom) {
- xs.push_back(maxX);
- ys.push_back(minY);
- } else if(leftright) {
- double midY = y1+(y2-y1)/2.0;
- if(left1) { // left to right
- if(midY<getCentreY()) { // route below
- // bottom left
- xs.push_back(getMinX());
- ys.push_back(getMinY());
- // bottom right
- xs.push_back(getMaxX());
- ys.push_back(getMinY());
- } else { // route above
- // top left
- xs.push_back(getMinX());
- ys.push_back(getMaxY());
- // top right
- xs.push_back(getMaxX());
- ys.push_back(getMaxY());
- }
- } else { // right to left
- if(midY<getCentreY()) { // route below
- // bottom right
- xs.push_back(getMaxX());
- ys.push_back(getMinY());
- // bottom left
- xs.push_back(getMinX());
- ys.push_back(getMinY());
- } else { // route above
- // top right
- xs.push_back(getMaxX());
- ys.push_back(getMaxY());
- // top left
- xs.push_back(getMinX());
- ys.push_back(getMaxY());
- }
- }
- } else if(topbottom) {
- double midX = x1+(x2-x1)/2.0;
- if(top1) {
- if(midX<getCentreX()) { // route left
- // top left
- xs.push_back(getMinX());
- ys.push_back(getMaxY());
- // bottom left
- xs.push_back(getMinX());
- ys.push_back(getMinY());
- } else { // route right
- // top right
- xs.push_back(getMaxX());
- ys.push_back(getMaxY());
- // bottom right
- xs.push_back(getMaxX());
- ys.push_back(getMinY());
- }
- } else { // bottom to top
- if(midX<getCentreX()) { // route left
- // bottom left
- xs.push_back(getMinX());
- ys.push_back(getMinY());
- // top left
- xs.push_back(getMinX());
- ys.push_back(getMaxY());
- } else { // route right
- // bottom right
- xs.push_back(getMaxX());
- ys.push_back(getMinY());
- // top right
- xs.push_back(getMaxX());
- ys.push_back(getMaxY());
- }
- }
- }
- xs.push_back(x2);
- ys.push_back(y2);
-}
-
-/*
- * moves all the rectangles to remove all overlaps. Heuristic
- * attempts to move by as little as possible.
- * no overlaps guaranteed.
- * @param rs the rectangles which will be moved to remove overlap
- */
-void removeoverlaps(Rectangles& rs) {
- const set<unsigned> fixed;
- removeoverlaps(rs,fixed);
-}
-#define ISNOTNAN(d) (d)==(d)
-/*
- * Moves rectangles to remove all overlaps. A heuristic
- * attempts to move by as little as possible. The heuristic is
- * that the overlaps are removed horizontally and then vertically,
- * each pass being a quadratic program in which the total squared movement
- * is minimised subject to non-overlap constraints. An optional third
- * horizontal pass (in addition to the first horizontal pass and the second
- * vertical pass) can be applied wherein the x-positions of rectangles are reset to their
- * original positions and overlap removal repeated. This may avoid some
- * unnecessary movement.
- * @param rs the rectangles which will be moved to remove overlap
- * @param fixed a set of indices to rectangles which should not be moved
- * @param thirdPass optionally run the third horizontal pass described above.
- */
-void removeoverlaps(Rectangles& rs, const set<unsigned>& fixed, bool thirdPass) {
- const double xBorder=Rectangle::xBorder, yBorder=Rectangle::yBorder;
- static const double EXTRA_GAP=1e-3;
- static const size_t ARRAY_UNUSED=1;
- unsigned n=rs.size();
- try {
- // The extra gap avoids numerical imprecision problems
- Rectangle::setXBorder(xBorder+EXTRA_GAP);
- Rectangle::setYBorder(yBorder+EXTRA_GAP);
- Variables vs(n);
- Variables::iterator v;
- unsigned i=0;
- vector<double> initX(thirdPass?n:ARRAY_UNUSED);
- for(v=vs.begin();v!=vs.end();++v,++i) {
- double weight=1;
- if(fixed.find(i)!=fixed.end()) {
- weight=10000;
- }
- *v=new Variable(i,0,weight);
- if(thirdPass) {
- initX[i]=rs[i]->getCentreX();
- }
- }
- Constraints cs;
- generateXConstraints(rs,vs,cs,true);
- Solver vpsc_x(vs,cs);
- vpsc_x.solve();
- Rectangles::iterator r=rs.begin();
- for(v=vs.begin();v!=vs.end();++v,++r) {
- COLA_ASSERT(ISNOTNAN((*v)->finalPosition));
- (*r)->moveCentreX((*v)->finalPosition);
- }
- COLA_ASSERT(r==rs.end());
- for_each(cs.begin(),cs.end(),delete_object());
- cs.clear();
- // Removing the extra gap here ensures things that were moved to be
- // adjacent to one another above are not considered overlapping
- Rectangle::setXBorder(xBorder);
- generateYConstraints(rs,vs,cs);
- Solver vpsc_y(vs,cs);
- vpsc_y.solve();
- r=rs.begin();
- for(v=vs.begin();v!=vs.end();++v,++r) {
- COLA_ASSERT(ISNOTNAN((*v)->finalPosition));
- (*r)->moveCentreY((*v)->finalPosition);
- }
- for_each(cs.begin(),cs.end(),delete_object());
- cs.clear();
- Rectangle::setYBorder(yBorder);
- if(thirdPass) {
- // we reset x positions to their original values
- // and apply a third pass horizontally so that
- // rectangles which were moved unnecessarily in the
- // first horizontal pass (i.e. their overlap
- // was later resolved vertically) have an
- // opportunity now to stay put.
- Rectangle::setXBorder(xBorder+EXTRA_GAP);
- r=rs.begin();
- for(v=vs.begin();v!=vs.end();++v,++r) {
- (*r)->moveCentreX(initX[(*v)->id]);
- }
- generateXConstraints(rs,vs,cs,false);
- Solver vpsc_x2(vs,cs);
- vpsc_x2.solve();
- r=rs.begin();
- for(v=vs.begin();v!=vs.end();++v,++r) {
- COLA_ASSERT(ISNOTNAN((*v)->finalPosition));
- (*r)->moveCentreX((*v)->finalPosition);
- }
- }
- Rectangle::setXBorder(xBorder);
- for_each(cs.begin(),cs.end(),delete_object());
- for_each(vs.begin(),vs.end(),delete_object());
- } catch (char *str) {
- std::cerr<<str<<std::endl;
- for(Rectangles::iterator r=rs.begin();r!=rs.end();++r) {
- std::cerr << **r <<std::endl;
- }
- }
- COLA_ASSERT(noRectangleOverlaps(rs));
-}
-
-
-bool noRectangleOverlaps(const Rectangles& rs)
-{
- Rectangle *u, *v;
- Rectangles::const_iterator i=rs.begin(), j, e=rs.end();
- for (;i!=e;++i)
- {
- u=*i;
- for (j=i+1;j!=e;++j)
- {
- v=*j;
- if (u->overlapX(v)>0)
- {
- COLA_ASSERT(u->overlapY(v)==0);
- }
- }
- }
- return true;
-}
-
-// checks if line segment is strictly overlapping.
-// That is, if any point on the line is inside the rectangle.
-bool Rectangle::overlaps(double x1, double y1, double x2, double y2)
-{
- RectangleIntersections ri;
- lineIntersections(x1,y1,x2,y2,ri);
- if(ri.intersects) {
- if(ri.countIntersections()==1) {
- // special case when one point is touching
- // the boundary of the rectangle but no part
- // of the line is interior
- if(!inside(x1,y1)&&!inside(x2,y2)) {
- return false;
- }
- }
- printf("Rectangle/Segment intersection (SVG):\n");
- printf("<svg style=\"stroke: black; fill: none;\">\n");
- printf("<polyline points=\"%f,%f %f,%f\" />\n",x1,y1,x2,y2);
- printf("<rect x=\"%f\" y=\"%f\" width=\"%f\" height=\"%f\" />\n",
- getMinX(),getMinY(),width(),height());
- printf("</svg>\n");
- ri.printIntersections();
- return true;
- }
- return false;
-}
-
-
-void RectangleIntersections::printIntersections()
-{
- printf("intersections:\n");
- if(top) printf(" top=%d:(%f,%f)\n",top,topX,topY);
- if(bottom) printf(" bottom=%d:(%f,%f)\n",bottom,bottomX,bottomY);
- if(left) printf(" left=%d:(%f,%f)\n",left,leftX,leftY);
- if(right) printf(" right=%d:(%f,%f)\n",right,rightX,rightY);
-}
-
-// Of the stored intersections, this returns the one closest to the
-// specified point
-void RectangleIntersections::nearest(double x, double y, double &xi, double &yi) {
- bool is[]={top, right, bottom, left};
- double xs[]={topX, rightX, bottomX, leftX};
- double ys[]={topY, rightY, bottomY, leftY};
- double dx, dy, l, minl = 999999999999999.0;
- for(unsigned i=0;i<4;i++)
- {
- if(is[i])
- {
- dx=xs[i]-x;
- dy=ys[i]-y;
- l=dx*dx + dy*dy;
- if(l<minl)
- {
- minl=l;
- xi=xs[i];
- yi=ys[i];
- }
- }
- }
-}
-
-}
generated by cgit v1.2.3 (git 2.25.1) at 2026-05-19 12:15:10 +0000