I will really hate floating-point math.
I was just adding edges on the limiting rectangle. The first idea going through all Voronoi points than sorting them clockwise, adding corners, and making new edges seems simple.
I was completely wrong, it is much more complex.
I need to preserve information on which input points create that edge so I need to go through edges not Voronoi points thus new vector will have some points more times. Still not difficult and it will provide information which input points (cells) own the edge on limiting rectangle.
I tried it, it did not work. I try to find why and I found out that the issue is that these points on the edge of limiting area are not too close to be considered on edge by comparision function using floating point comparison through ulp. So my question was why. I have found that my calculation of these points are based on lineSegmentsIntersection function with edge line is AB and rectangle limiting line PQ:
inline std::optional<Vector2f> lineSegmentsIntersection (const Vector2f pointA, const Vector2f pointB, const Vector2f pointP, const Vector2f pointQ)
{
double ux = pointB.x - pointA.x;
double uy = pointB.y - pointA.y;
double px = pointQ.x - pointP.x;
double py = pointQ.y - pointP.y;
double denom = ux * py - px * uy;
if (compareToZero(denom) == std::partial_ordering::equivalent)
{
return std::nullopt; // Collinear
}
double a = (-uy * (pointA.x - pointP.x) + ux * (pointA.y - pointP.y)) / denom;
double b = ( px * (pointA.y - pointP.y) - py * (pointA.x - pointP.x)) / denom;
if (a >= 0 && a <= 1 && b >= 0 && b <= 1)
{
// intersection detected
float x = pointA.x + (b * ux);
float y = pointA.y + (b * uy);
return Vector2f(x, y);
}
return std::nullopt;
}
Everything seems right but there is very small logical error. Intersection point is based on point A, not point P or Q which even if it is float it use integral inside as it is limiting rectangle for visualisation. So just swaping AB with PQ solves the problem.
I think I will have small pause and than I will go through all code to make it more readable before final check that it works for any points with reasonable distance between them.
But floating point math with completely different accuracy in different calculations makes comparison really extreme difficult.
At least next step is done. Voronoi should be completed, so now I will start to implement testing for large random numbers to verify that it handles all possible cases correctly.
