Re: [Boost][BGL] "is_straight_line_drawing()" is buggy for large graphs

From: hermann_at_[hidden]
Date: 2024-10-05 14:19:48

On 2024-10-05 13:42, Seth wrote:
> [...]
>> So edges have vertex (78821, 71094) in common, but have different
>> slopes 69141/-69140 and 69142/-69141, and assert proves the bug.
> 
> I think I was confused by the wording. The assert failing seemed to
> imply that you *expected* the predicate to return true for the given
> line drawing.
> 
> I think I now understand that you actually mean that you mean the
> assert proves a bug in the Chrobak-Paine implementation, which
> generates just just off-straight data due to rounding issues?
> 
> If so, never mind me, I bet everyone else involved immediately got that 
> :)
> 
Sorry, non-native speaker here.

chrobak_payne_straight_line_drawing() creates integer coordinates - so 
no problem:

OUT: PositionMap

     A Writable LValue Property Map that models the Position Map concept. 
The Position Map concept requires that the value mapped to be an object 
that has members x and y. For example, if p models PositionMap and v is 
a vertex in the graph, p[v].x and p[v].y are valid expressions. The type 
of x and y must be implicitly convertable to std::size_t.

is_straight_line_drawing() works on integer coordinates most time.
The problem is the internal call of intersects() with double arguments.

So

inline bool intersects(double x1, double y1, double x2, double y2, 
double a1,
     double b1, double a2, double b2, double epsilon = 0.000001)

should be changed to

inline bool intersects(T x1, T y1, T x2, T_t y2,
                        T a1, T b1, T a2, T b2)

without epsilon, and integer type T. It should be implemented with
any of the integer coordinate precision loss free algorithms.

Regards,

Hermann.