Boost Users :
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:
>> 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?
>> David Gleich
>> should be
>> / | \
>> \ | /
>> which is not a plane drawing.
> 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.
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.
Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net