Re: [Boost-users] [Graph] Issue with is_straight_line_drawing?

Subject: Re: [Boost-users] [Graph] Issue with is_straight_line_drawing?
From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2008-10-04 18:52:00

On Fri, Oct 3, 2008 at 9:08 AM, Aaron Windsor <aaron.windsor_at_[hidden]> wrote:
> On Thu, Oct 2, 2008 at 3:00 PM, David Gleich <dgleich_at_[hidden]> wrote:
>> Hi,
>>
>> I'm concerned about the output I'm getting from the
>> is_straight_line_drawing function in the Boost Graph library.  My
>> understanding was that it should report true when the graph and
>> positions are a planar embedding (no edge crossings).
>>
>> Based on this understanding, I thought the code listed at the end of
>> the message should say that the drawing for a clique on 4 vertices,
>> with positions on a square, is not planar (see the picture below).
>> This arrangement has one edge crossing.  The function outputs that the
>> graph is a plane drawing.
>>
>> Did I misunderstand what the is_straight_line_drawing function is
>> supposed to do?
>>
>> Thanks,
>> David Gleich
>
> <snip>
>
>>  /*
>>  should be
>>      0
>>    / | \
>>   3--|--1
>>    \ | /
>>      2
>>  which is not a plane drawing.
>>  */
>
> <snip>
>
> Hi David,
>
> You're right - this looks like a bug in is_straight_line_drawing. The
> sweep of the plane isn't comparing the two perpendicular edges (0,2)
> and (1,3), which intersect. I'll look at the code a little more
> closely this weekend and see if I can't come up with a fix.
>
> Regards,
> Aaron
>

Hi David,

I just committed a fix for this bug to trunk - an additional
comparison was needed at each event point during the sweep of the
plane. Let me know if you'd like a patch.

Regards,
Aaron