How to find if two polygons intersect
-
I'm having difficulty finding out if two polygons (or two lines for that matter) intersect. Would appreciate some help.
Here's my code.
@void Grid::onPaint()
{
QPainterPath path = createPath();
QDesktopWidget *widget = QApplication::desktop();
QScreen *screen = QApplication::screens().at(widget->primaryScreen());
QPainter painter(this);
double ppi = screen->physicalDotsPerInch();
double ascender = ((m_nib * m_ascender.spacing) / grid::MMToInch) * ppi;
double chgt = ((m_nib * m_capHgt.spacing) / grid::MMToInch) * ppi;
double xhgt = ((m_nib * m_xHgt.spacing) / grid::MMToInch) * ppi;
double des = ((m_nib * m_descender.spacing) / grid::MMToInch) * ppi;
double percent = 0;
qreal slantLinePixels = ((m_nib * m_slantLine.spacing) / grid::MMToInch) * ppi + 1;
qreal pctIncrease = (slantLinePixels + 10) / path.length();while (percent + pctIncrease <= 1) { QPointF point = path.pointAtPercent(percentageOffset(percent)); qreal angle = (m_baselineConstraints == BaselineConstraints::StaticAngle) ? 0 : path.angleAtPercent(percentageOffset(percent)); qreal realSlantAngle = angle + m_slantLine.angle; QLineF b, xh, ch, a, d, db, bxh, xhch, cha, ach, chxh, xhb, bd; b.setP1(point); b.setAngle(angle); b.setLength(slantLinePixels); bxh.setP1(b.p1()); bxh.setLength(xhgt); bxh.setAngle(realSlantAngle); xhch.setP1(bxh.p2()); xhch.setLength(chgt); xhch.setAngle(realSlantAngle); cha.setP1(xhch.p2()); cha.setLength(ascender); cha.setAngle(realSlantAngle); a.setP1(cha.p2()); a.setAngle(angle); a.setLength(slantLinePixels); ch.setP1(xhch.p2()); ch.setLength(slantLinePixels); ch.setAngle(angle); ach.setP1(a.p2()); ach.setP2(ch.p2()); xh.setP1(bxh.p2()); xh.setLength(slantLinePixels); xh.setAngle(angle); chxh.setP1(ch.p2()); chxh.setP2(xh.p2()); xhb.setP1(xh.p2()); xhb.setP2(b.p2()); bd.setP1(b.p2()); bd.setLength(des); bd.setAngle(xhb.angle()); d.setP1(bd.p2()); d.setLength(slantLinePixels); d.setAngle(((angle < 180) ? angle + 180 : angle - 180)); db.setP1(d.p2()); db.setP2(b.p1()); QLineF slant1(db.p1(), a.p1()); QLineF slant2(d.p1(), a.p2()); QPainterPath path2; QPolygonF poly; poly << db.p1() << a.p1() << a.p2() << d.p1() << db.p1(); path2.addPolygon(poly); foreach (QPainterPath p, m_lines) { if (p.intersects(path2)) { percent += .01; continue; } } m_lines.append(path2); QPen pen = painter.pen(); pen.setColor(Qt::black); painter.setPen(pen); painter.drawLine(b); drawLine(slant1, m_slantLine, painter); drawLine(slant2, m_slantLine, painter); drawLine(a, m_ascender, painter); drawLine(ch, m_capHgt, painter); drawLine(xh, m_xHgt, painter); drawLine(d, m_descender, painter); percent += pctIncrease; } m_lines.clear();
}
@
Obviously this is brute force. I've tried using QPolygon::intersected() with each polygon against every other polygon and QLineF::intersect() with every other line. I don't know why nothing like this works. I would like to use QPainter::translate() and QPainter::rotate(), but that's even harder (how do I keep up with the translated and rotated line coordinates?).
Everything I've tried draws the shapes with overlapping edges.
Any help appreciated.
-
I set this up with putting a square or a circle in the path.
-
If I could use QPainter::translate() and rotate(), I could get rid of all that setP1() and setP2() stuff and use a set of lines that I create outside of the while loop (each iteration draws the same shape, just rotated and translated).