Description
I experienced "is_straight_line_drawing()" returning false for valid straight line drawing of a maximal planar graph with 10million vertices first:
https://lists.boost.org/Archives/boost/2024/10/257979.php
Later I was able to reduce to 1million vertices, and now to only three vertices with this simplified gist:
https://gist.github.com/Hermann-SW/992b43eef29f1ef28c4bf2727f0a7c16
After the straight line drawing for the K₃ was computed, I did overwrite the determined coordinates for the three vertices with the coordinates of three vertices reported for initial 10million vertex graph. With that coordinates and the edges in same direction as in previous graph the problem is recreated fast:
hermann@7950x:~$ f=is_straight_line_drawing.recreate
hermann@7950x:~$ g++ -O3 -Wall -pedantic -Wextra $f.cpp -o $f
hermann@7950x:~$ ./is_straight_line_drawing.recreate
is_straight_line_drawing.recreate: is_straight_line_drawing.recreate.cpp:101: int main(int, char**): Assertion `is_straight_line_drawing(g, straight_line_drawing)' failed.
Aborted (core dumped)
hermann@7950x:~$
The problem is that "is_straight_line_drawing()" working on coordinates of std::size_t does call function using double, causing false report:
inline bool intersects(double x1, double y1, double x2, double y2, double a1,
double b1, double a2, double b2, double epsilon = 0.000001)
{
There are plenty of intersection test algorithms that avoid doing division and report correct result for integer coordinates, eg:
- https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection#Given_two_points_on_each_line_segment
- https://www.dcs.gla.ac.uk/~pat/52233/slides/Geometry1x1.pdf#page=4
"bool intersects()" needs to be implemented with integer coordinates for correct response.
This is the graph from recreate gist:
graph g(3);
add_edge(0, 1, g);
add_edge(2, 0, g);
add_edge(1, 2, g);
And these are the coordinates:
straight_line_drawing[0].x = 4143438;
straight_line_drawing[0].y = 86426;
straight_line_drawing[1].x = 4064945;
straight_line_drawing[1].y = 7932;
straight_line_drawing[2].x = 4064944;
straight_line_drawing[2].y = 7931;
There is a very small angle between edge 0--1 and edge 2--0 at vertex 0, with slope of edges 78494/78493 and 78495/78494, which cannot be correctly handled by double type function:
4143438-4064945 = 78493
86426-7932 = 78494
4143438-4064944 = 78494
86426-7931 = 78495