How to find if two polygons intersect

[jbarnesweb]

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.

[jbarnesweb]

I set this up with putting a square or a circle in the path.

[jbarnesweb]

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).