QPolygonF error

Daniil S.

move the slider and graph will sometimes bug

.pro file

QT  += core gui

greaterThan(QT_MAJOR_VERSION, 4): QT += widgets

CONFIG += c++11

# You can make your code fail to compile if it uses deprecated APIs.
# In order to do so, uncomment the following line.
#DEFINES += QT_DISABLE_DEPRECATED_BEFORE=0x060000    # disables all the APIs deprecated before Qt 6.0.0

SOURCES += \
    main.cpp \
    mainwindow.cpp

HEADERS += \
    mainwindow.h

FORMS += \
    mainwindow.ui

# Default rules for deployment.
qnx: target.path = /tmp/$${TARGET}/bin
else: unix:!android: target.path = /opt/$${TARGET}/bin
!isEmpty(target.path): INSTALLS += target

main.cpp

#include "mainwindow.h"

#include <QApplication>
#include <QWidget>

int main(int argc, char *argv[])
{
  QApplication a(argc, argv);
  MainWindow w;
  w.show();
  return a.exec();
}

mainwindow.h

#pragma once

#include <QMainWindow>
#include <QPainterPath>

QT_BEGIN_NAMESPACE
namespace Ui { class MainWindow; }
QT_END_NAMESPACE

class MainWindow : public QMainWindow
{
  Q_OBJECT

  static QVector<QPointF> HtpType(QVector<QPointF> low_graphic, QVector<QPointF> high_graphic);
  static int GetTimeProjection(qreal x_coord, QPointF left_point, QPointF right_point);

public:
  MainWindow(QWidget *parent = nullptr);
  ~MainWindow();

public slots:
  void recalculate(int value);

private:
  Ui::MainWindow *ui;
};

mainwindow.cpp

#include "mainwindow.h"
#include "ui_mainwindow.h"

QVector<QPointF> MainWindow::HtpType(QVector<QPointF> low_graphic, QVector<QPointF> high_graphic)
{
  QVector<QPointF> combined, intersected_low, after_high;

  QPointF before_enter(-1,-1), after_exit(-1,-1);
  auto low_iterator(low_graphic.begin());
  while (low_iterator != low_graphic.end()) {

    if (low_iterator->x() < high_graphic.first().x()) {

      combined.push_back(*low_iterator); 
      before_enter = *low_iterator; 
    }
    else if (low_iterator->x() >= high_graphic.first().x() && low_iterator->x() <= high_graphic.last().x()) {

      intersected_low.push_back(*low_iterator); 

    } else if (low_iterator->x() > high_graphic.last().x()) {

      if (after_exit == QPointF(-1,-1))  
        after_exit = *low_iterator;

      after_high.push_back(*low_iterator); 
    }
    low_iterator++;
  }

  if (intersected_low.isEmpty()) {

    if (before_enter.y() == -1 && after_exit.y() == -1) { 
      high_graphic.push_front(QPointF(high_graphic.first().x(), -1));
      high_graphic.push_back(QPointF(high_graphic.last().x(), -1));

      Q_FOREACH(QPointF point, high_graphic)
        if (combined.last() != point)
          combined.push_back(point);

      Q_FOREACH(QPointF point, after_high)
        if (combined.last() != point)
          combined.push_back(point);

      return combined;
    } else { 

      intersected_low.push_back(QPointF(high_graphic.first().x(), GetTimeProjection(high_graphic.first().x(), before_enter, after_exit)));
      intersected_low.push_back(QPointF(high_graphic.last().x(), GetTimeProjection(high_graphic.last().x(), before_enter, after_exit)));
    }
  }

  QPolygonF low_polygon(intersected_low), high_polygon(high_graphic);

  QPointF prepend_point(before_enter.y() != -1 ? QPointF(high_graphic.first().x(), GetTimeProjection(high_graphic.first().x(), before_enter, intersected_low.first()))
                                               : QPointF(high_graphic.first().x(), -1));

  low_polygon.prepend(prepend_point);
  if (combined.last() != prepend_point)
    combined.push_back(prepend_point);

  low_polygon.prepend(QPointF(high_graphic.first().x(), -2));
  low_polygon.append(after_exit.y() != -1 ? QPointF(high_graphic.last().x(), GetTimeProjection(high_graphic.last().x(), intersected_low.last(), after_exit))
                                          : QPointF(high_graphic.last().x(), -1));
  low_polygon.append(QPointF(high_graphic.last().x(), -2));

  for(int i(0); i < low_polygon.count(); i++)
    if (low_polygon.at(i).y() == -1)
      low_polygon[i].ry() = 0;

  high_polygon.prepend(QPointF(high_graphic.first().x(), -2));
  high_polygon.append(QPointF(high_graphic.last().x(), -2));

  QPolygonF united_low(low_polygon.united(high_polygon));
  united_low.erase(std::remove_if(united_low.begin(), united_low.end(), [](QPointF p) { return p.y() == -2; }), united_low.end());

  if (united_low.last() == united_low.first())
    united_low.removeLast(); 

  QPointF after_high_point(high_graphic.last().x(), -1);
  if (after_exit.y() != -1)
    after_high_point.ry() = GetTimeProjection(high_graphic.last().x(), intersected_low.last(), after_exit);
  united_low.push_back(after_high_point);

  Q_FOREACH(QPointF point, united_low)
    if (combined.last() != point)
      combined.push_back(point);

  Q_FOREACH(QPointF point, after_high)
    if (combined.last() != point)
      combined.push_back(point);

  return combined;
}

int MainWindow::GetTimeProjection(qreal x_coord, QPointF left_point, QPointF right_point)
{
  if (left_point.y() == -1)
    left_point.ry() = 0;
  if (right_point.y() == -1)
    right_point.ry() = 0;

  qreal x_min = (( right_point.x() <= left_point.x() ) ? right_point.x() : left_point.x());
  qreal x_max = (( right_point.x() >= left_point.x() ) ? right_point.x() : left_point.x());
  qreal y_min = (( right_point.y() <= left_point.y() ) ? right_point.y() : left_point.y());
  qreal y_max = (( right_point.y() >= left_point.y() ) ? right_point.y() : left_point.y());

  int direction = 0;

  if (left_point.y() != right_point.y())
    direction = ((left_point.y() < right_point.y()) ? 1 : -1);

  qreal delta_x = x_max - x_min;
  qreal delta_y = y_max - y_min;

  int value = 0;

  direction == -1 ? value = (delta_x ? y_min + delta_y - (delta_y / delta_x) * (x_coord - x_min) : y_min + delta_y)
                            : value = (delta_x ? y_min + (delta_y / delta_x) * (x_coord - x_min) : y_min);

  return value;
}

MainWindow::MainWindow(QWidget *parent)
  : QMainWindow(parent)
  , ui(new Ui::MainWindow)
{
  ui->setupUi(this);
  ui->graphicsView->setScene(new QGraphicsScene(ui->graphicsView));

  ui->horizontalSlider->setRange(0, 255);
  connect(ui->horizontalSlider, &QSlider::valueChanged, this, &MainWindow::recalculate);
}

MainWindow::~MainWindow()
{
  delete ui;
}

void MainWindow::recalculate(int value)
{
  QVector<QPointF> high, low1;
  high << QPointF(293,0) << QPointF(406.102, 225) << QPointF(556,0);
  low1 << QPointF(0,-1) << QPointF(79,-1) << QPointF(79,31) << QPointF(182.303,value) << QPointF(643,0) << QPointF(673,31) << QPointF(673,-1) << QPointF(1000,- 1);

  QVector<QPointF> result(HtpType(HtpType(low1, high), high));

  QPointF first(result.first());
  first.ry() = std::abs(255 - first.y());
  QPainterPath path(first);
  for(int i(1); i < result.count(); i++) {

    QPointF next(result.at(i));
    next.ry() = std::abs(255 - next.y());
    path.lineTo(next);
  }

  ui->graphicsView->scene()->clear();
  ui->graphicsView->scene()->addPath(path);
}

mainwindow.ui

<?xml version="1.0" encoding="UTF-8"?>
<ui version="4.0">
 <class>MainWindow</class>
 <widget class="QMainWindow" name="MainWindow">
  <property name="geometry">
   <rect>
    <x>0</x>
    <y>0</y>
    <width>800</width>
    <height>600</height>
   </rect>
  </property>
  <property name="windowTitle">
   <string>MainWindow</string>
  </property>
  <widget class="QWidget" name="centralwidget">
   <widget class="QGraphicsView" name="graphicsView">
    <property name="geometry">
     <rect>
      <x>50</x>
      <y>50</y>
      <width>681</width>
      <height>461</height>
     </rect>
    </property>
   </widget>
   <widget class="QSlider" name="horizontalSlider">
    <property name="geometry">
     <rect>
      <x>290</x>
      <y>520</y>
      <width>160</width>
      <height>16</height>
     </rect>
    </property>
    <property name="orientation">
     <enum>Qt::Horizontal</enum>
    </property>
   </widget>
  </widget>
  <widget class="QMenuBar" name="menubar">
   <property name="geometry">
    <rect>
     <x>0</x>
     <y>0</y>
     <width>800</width>
     <height>20</height>
    </rect>
   </property>
  </widget>
  <widget class="QStatusBar" name="statusbar"/>
 </widget>
 <resources/>
 <connections/>
</ui>

Daniil S.

@Christian-Ehrlicher what you need or a smaller example?

JonB

@Daniil-S said in QPolygonF error:

or a smaller example?

Do you really need about 100 lines of code to draw a polygon to illustrate whatever your problem is? Have you reduced this to some minimum which exemplifies the problem? Any example to illustrate a point which is longer than about 20 lines is suspect....

Christian Ehrlicher

I will not debug your code, as @JonB said (and also me some time ago) a simple list with the polygons as input and the (wrong) and correct output is the way to go.

Daniil S.

  QVector<QPointF> high, low;
  high << QPointF(293,0) << QPointF(406.102, 225) << QPointF(556,0);
  low << QPointF(79,-1) << QPointF(182.303, 57) << QPointF(673,-1);

  qDebug() << HtpType(HtpType(low, high), high);

  QVector<QPointF> high1, low1;
  high1 << QPointF(293,0) << QPointF(406.102, 225) << QPointF(556,0);
  low1 << QPointF(79,-1) << QPointF(182.303, 60) << QPointF(673,-1);

  qDebug() << HtpType(HtpType(low1, high1), high1);

first qDebug() (second point of low Y = 57) bad result

QVector(QPointF(79,-1), QPointF(182.303,57), QPointF(293,44), QPointF(293,0), QPointF(293,44), QPointF(313.881,41.5388), QPointF(293,0), QPointF(313.881,41.5388), QPointF(406.102,225), QPointF(546.601,14.1078), QPointF(556,13), QPointF(556,0), QPointF(406.102,225), QPointF(313.881,41.5388), QPointF(556,-1), QPointF(673,-1))

second qDebug() (second point of low Y = 60) right result

QVector(QPointF(79,-1), QPointF(182.303,60), QPointF(293,46), QPointF(314.79,43.3487), QPointF(406.102,225), QPointF(545.85,15.2349), QPointF(556,14), QPointF(556,-1), QPointF(673,-1))

to combine two plots, I need to use this method, because graphs has flags that cannot be changed during combine, so the intersection is first searched and it is combined to the top

Christian Ehrlicher

This is a testcase similar to what we want to see:

int main(int argc, char **argv)
{
  QCoreApplication app(argc, argv);

  QPolygonF p1 = QVector<QPointF>({{1., 0.}, {2., 1.}, {3., 1.}, {4., 1.}});
  QPolygonF p2 = QVector<QPointF>({{2., 2.}, {3., 2.}, {4., 5.}, {3., 2.}});
  QPolygonF united = p1.united(p2);
  QPolygonF expected = QVector<QPointF>({{1., 0.}, {2., 1.}, {3., 1.}, {4., 1.}, {1., 0.}, {2., 2.}, {3., 2.}, {4., 5.}, {3., 2.}, {2., 2.}, {1., 0.}});
  qDebug() << (united == expected);
  qDebug() << united;
  qDebug() << expected;

  return 0;
}

Daniil S.

@Christian-Ehrlicher

int main(int argc, char *argv[])
{
  QPolygonF high, low;
  high << QPointF(293, 0) << QPointF(406.102, 225) << QPointF(556, 0);
  low << QPointF(79, -1) << QPointF(182.303, 60) << QPointF(673, -1);



  QPolygonF low1(low.united(high).united(high))
      , expected({ QPointF(79,-1), QPointF(182.303,60), QPointF(314.876,43.5194), QPointF(406.102,225), QPointF(546.162,14.7677), QPointF(673,-1), QPointF(79,-1) });

  qDebug() << low1;
  qDebug() << expected;
  qDebug() << (expected == low1);

  return 0;
}

qDebug()

QPolygonF(QPointF(79,-1)QPointF(182.303,60)QPointF(314.876,43.5194)QPointF(293,0)QPointF(556,0)QPointF(406.102,225)QPointF(314.876,43.5194)QPointF(182.303,60)QPointF(79,-1)QPointF(314.876,43.5194)QPointF(406.102,225)QPointF(546.162,14.7677)QPointF(673,-1)QPointF(79,-1)QPointF(182.303,60)QPointF(314.876,43.5194)QPointF(293,0)QPointF(556,0)QPointF(406.102,225)QPointF(314.876,43.5194)QPointF(79,-1))

QPolygonF(QPointF(79,-1)QPointF(182.303,60)QPointF(314.876,43.5194)QPointF(406.102,225)QPointF(546.162,14.7677)QPointF(673,-1)QPointF(79,-1))

false

Daniil S.

@Christian-Ehrlicher still not what you need?

kshegunov

low.united(high).united(high)?

Why the second call? What does calling it only once produce?

Daniil S.

@kshegunov I have an application that combines graphs of changing values, nothing prevents different "scenes" with same graphs that can combined more times. now I have 3 scenes, on 3 lines, the top two scenes have exactly the same graph, and if i combine them all, this leads to this error

kshegunov

Okay, this answers the first question, what about the second? Does calling .union only once produce the correct result?

Christian Ehrlicher

@kshegunov said in QPolygonF error:

Does calling .union only once produce the correct result?

Yes, but with slightly different numbers (not visible in a plain debug output). I would guess somewhere in the clipping logic a rounding error triggers this bug (e.g. 314.87615740 / 43.51943745 <-> 314.87600000 / 43.51940000)

Daniil S.

@kshegunov yes, but I cant check top polygons are equal, because they must be combined in order in the loop and can have different overlay types, and checking high by points before united is not entirely correct, because a polygon can contain a point, but not a union

kshegunov

@Christian-Ehrlicher said in QPolygonF error:

Yes, but with slightly different numbers (not visible in a plain debug output). I would guess somewhere in the clipping logic a rounding error triggers this bug (e.g. 314.87615740 / 43.51943745 <-> 314.87600000 / 43.51940000)

Looks truncated more than a rounding error.

@Daniil-S said in QPolygonF error:

yes, but I cant check top polygons are equal, because they must be combined in order in the loop and can have different overlay types, and checking high by points before united is not entirely correct, because a polygon can contain a point, but not a union

I was asking to discern whether the problem is that the two unions apply the same polygon only, there's a lot of edge cases whenever you're dealing with lines which are almost parallel (e.g. https://codereview.qt-project.org/c/qt/qtbase/+/292807).

Please search the tracker and if this isn't reported, do so. Attach the minimal code to reproduce as well. Whenever I finish with that QLineF thing, given time I'll take a look.

Christian Ehrlicher

@kshegunov said in QPolygonF error:

Looks truncated more than a rounding error.

No error - qDebug() prints not the complete double value, I guess the values are taken from there. Mine are the exact ones :)

So basically a polygon is united with a polygon which nearly matches parts of the first polygon which fails sometimes.

kshegunov

@Christian-Ehrlicher said in QPolygonF error:

So basically a polygon is united with a polygon which nearly matches parts of the first polygon which fails sometimes.

Yes, what I imagine happens. Probably somewhere in the clip/intersection code there's some numerical instability that breaks it silently.

Daniil S.

@kshegunov yes, it only happens if two identical polygons are combine.
here i think, is what is needed

kshegunov

lol. "Out of scope" ... what can I say ...

I suggest you open a new one, attach the reproducing code (the minimal one that @Christian-Ehrlicher insisted on), and put in the:
"Relates to ..." field in JIRA QTBUG-38037, as it does indeed seem related.

Daniil S.

https://bugreports.qt.io/browse/QTBUG-100172

kshegunov

As I was looking into this, I also opened:

https://bugreports.qt.io/browse/QTBUG-100302