Skip to content

"is_straight_line_drawing()" is buggy for large graphs #388

Closed
@Hermann-SW

Description

@Hermann-SW

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:

  1. https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection#Given_two_points_on_each_line_segment
  2. 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

Metadata

Metadata

Assignees

Labels

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions