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


Log in to reply
 

Looks like your connection to Qt Forum was lost, please wait while we try to reconnect.