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

4 Oct 2008

      On Fri, Oct 3, 2008 at 9:08 AM, Aaron Windsor  wrote:
...
On Thu, Oct 2, 2008 at 3:00 PM, David Gleich  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