[Boost-bugs] [Boost C++ Libraries] #12707: Missing edges in Voronoi Diagram

Subject: [Boost-bugs] [Boost C++ Libraries] #12707: Missing edges in Voronoi Diagram
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2016-12-21 18:42:02

#12707: Missing edges in Voronoi Diagram
------------------------------+----------------------
 Reporter:  alessandro@…      |      Owner:  ljsimons
     Type:  Bugs              |     Status:  new
Milestone:  To Be Determined  |  Component:  polygon
  Version:  Boost 1.56.0      |   Severity:  Problem
 Keywords:  voronoi           |
------------------------------+----------------------
 A couple finite edges are missing from the Voronoi diagram built for the
 following segments:

 {{{
 LINESTRING(42127548 699996,42127548 10135750)
 LINESTRING(42127548 10135750,50487352 10135750)
 LINESTRING(50487352 10135750,50487352 699995)
 LINESTRING(50487352 699995,51187348 0)
 LINESTRING(51187348 0,64325952 0)
 LINESTRING(64325952 0,65025956 699996)
 LINESTRING(65025956 699996,65025956 10135750)
 LINESTRING(65025956 10135750,72633752 10135750)
 LINESTRING(72633752 10135750,72633752 699995)
 LINESTRING(72633752 699995,73333744 0)
 LINESTRING(73333744 0,86471456 0)
 LINESTRING(86471456 0,87171440 699996)
 LINESTRING(87171440 699996,87171440 10121802)
 LINESTRING(87171440 10121802,92690455 10323692)
 LINESTRING(92690455 10323692,93364864 11023201)
 LINESTRING(93364864 11023201,93364864 15074997)
 LINESTRING(93364864 15074997,92664848 15074997)
 LINESTRING(92664848 15074997,92664848 11023201)
 LINESTRING(92664848 11023201,86471456 10796700)
 LINESTRING(86471456 10796700,86471456 699996)
 LINESTRING(86471456 699996,73333744 699996)
 LINESTRING(73333744 699996,73333744 10835701)
 LINESTRING(73333744 10835701,64325952 10835701)
 LINESTRING(64325952 10835701,64325952 699996)
 LINESTRING(64325952 699996,51187348 699996)
 LINESTRING(51187348 699996,51187348 10835701)
 LINESTRING(51187348 10835701,41427552 10835701)
 LINESTRING(41427552 10835701,41427552 699996)
 LINESTRING(41427552 699996,28664848 699996)
 LINESTRING(28664848 699996,28664848 10835701)
 LINESTRING(28664848 10835701,19280052 10835701)
 LINESTRING(19280052 10835701,19280052 699996)
 LINESTRING(19280052 699996,5767387 699996)
 LINESTRING(5767387 699996,5767387 10796699)
 LINESTRING(5767387 10796699,699996 11023200)
 LINESTRING(699996 11023200,699996 15074997)
 LINESTRING(699996 15074997,0 15074997)
 LINESTRING(0 15074997,7 11023201)
 LINESTRING(7 11023201,668738 10323952)
 LINESTRING(668738 10323952,5067390 10127281)
 LINESTRING(5067390 10127281,5067390 699996)
 LINESTRING(5067390 699996,5767387 0)
 LINESTRING(5767387 0,19285884 5831)
 LINESTRING(19285884 5831,19980050 699996)
 LINESTRING(19980050 699996,19980050 10135750)
 LINESTRING(19980050 10135750,27964852 10135750)
 LINESTRING(27964852 10135750,27964852 699996)
 LINESTRING(27964852 699996,28664848 0)
 LINESTRING(28664848 0,41427551 0)
 LINESTRING(41427551 0,42127548 699996)
 }}}

 I'm attaching a SVG showing the Voronoi diagram. (The input segments are
 the contours of the grey polygon; the black edges are the finite edges of
 the diagram.)

 It might be related to #12067, but a finite edge is missing here instead
 of an infinite one.

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/12707>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.