Geometry Boost List: [GGL] #17: ASSERT when intersecting "criss-crossed" polygon with box

Subject: [GGL] #17: ASSERT when intersecting "criss-crossed" polygon with box
From: Chris Browet (cbro)
Date: 2009-09-29 11:45:21

Or maybe there is a way to anticiapte the fact that it will fail, i.e. a way
to know if the polygon is valid?

- Chris -

2009/9/29 GGL <trac_at_[hidden]>

> #17: ASSERT when intersecting "criss-crossed" polygon with box
>
> ----------------------------+-----------------------------------------------
>  Reporter:  koying          |       Owner:
>     Type:  defect          |      Status:  new
>  Priority:  minor           |   Milestone:  <unspecified>
> Component:  ggl/algorithms  |     Version:  svn-trunk
>  Keywords:                  |
>
> ----------------------------+-----------------------------------------------
>  I receive an assert when doing polygon_2d by box_2d intersection in a very
>  specific case (see image attached).
>
>  In the context of the Openstreetmap project, someone "cheated" and criss-
>  crossed the polygon segment to avoid doing holes in the polygon.
>  Even if the polygon construct is not valid, it should throw an exception
>  rather than an ASSERT.
>
>  This lead to an assert with the following backtrace:
>  {{{
>  0       msvcrt!_assert  C:\WINDOWS\system32\msvcrt.dll  0
>  1       ggl::traverse<ggl::linear_ring<ggl::point_xy<double,
>  ggl::cs::cartesian>, std::vector, std::allocator>,
>  ggl::polygon<ggl::point_xy<double, ggl::cs::cartesian>, std::vector,
>  std::vector, std::allocator, std::allocator>,
>  ggl::box<ggl::point_xy<double, ggl::cs::cartesian> >,
>
>  std::deque<ggl::detail::intersection::intersection_point<ggl::point_xy<double,
>  ggl::cs::cartesian> >,
>
>  std::allocator<ggl::detail::intersection::intersection_point<ggl::point_xy<double,
>  ggl::cs::cartesian> > > >,
>
>  std::back_insert_iterator<std::vector<ggl::linear_ring<ggl::point_xy<double,
>  ggl::cs::cartesian>, std::vector, std::allocator>,
>  std::allocator<ggl::linear_ring<ggl::point_xy<double, ggl::cs::cartesian>,
>  std::vector, std::allocator> > > > >    traverse.hpp    372
>  2
>
>  ggl::detail::intersection::intersection_polygon_box<ggl::polygon<ggl::point_xy<double,
>  ggl::cs::cartesian>, std::vector, std::vector, std::allocator,
>  std::allocator>, ggl::box<ggl::point_xy<double, ggl::cs::cartesian> >,
>  std::back_insert_iterator<std::vector<ggl::polygon<ggl::point_xy<double,
>  ggl::cs::cartesian>, std::vector, std::vector, std::allocator,
>  std::allocator>, std::allocator<ggl::polygon<ggl::point_xy<double,
>  ggl::cs::cartesian>, std::vector, std::vector, std::allocator,
>  std::allocator> > > >, ggl::polygon<ggl::point_xy<double,
>  ggl::cs::cartesian>, std::vector, std::vector, std::allocator,
>  std::allocator> >::apply        intersection.hpp        225
>  3       ggl::dispatch::intersection_reversed<ggl::box_tag,
>  ggl::polygon_tag, ggl::polygon_tag, ggl::box<ggl::point_xy<double,
>  ggl::cs::cartesian> >, ggl::polygon<ggl::point_xy<double,
>  ggl::cs::cartesian>, std::vector, std::vector, std::allocator,
>  std::allocator>,
>  std::back_insert_iterator<std::vector<ggl::polygon<ggl::point_xy<double,
>  ggl::cs::cartesian>, std::vector, std::vector, std::allocator,
>  std::allocator>, std::allocator<ggl::polygon<ggl::point_xy<double,
>  ggl::cs::cartesian>, std::vector, std::vector, std::allocator,
>  std::allocator> > > >, ggl::polygon<ggl::point_xy<double,
>  ggl::cs::cartesian>, std::vector, std::vector, std::allocator,
>  std::allocator> >::apply     intersection.hpp        384
>  4       ggl::intersection<ggl::polygon<ggl::point_xy<double,
>  ggl::cs::cartesian>, std::vector, std::vector, std::allocator,
>  std::allocator>, ggl::box<ggl::point_xy<double, ggl::cs::cartesian> >,
>  ggl::polygon<ggl::point_xy<double, ggl::cs::cartesian>, std::vector,
>  std::vector, std::allocator, std::allocator>,
>  std::back_insert_iterator<std::vector<ggl::polygon<ggl::point_xy<double,
>  ggl::cs::cartesian>, std::vector, std::vector, std::allocator,
>  std::allocator>, std::allocator<ggl::polygon<ggl::point_xy<double,
>  ggl::cs::cartesian>, std::vector, std::vector, std::allocator,
>  std::allocator> > > > > intersection.hpp        427
>  5       Road::buildPath Road.cpp        623
>  6       MapView::buildFeatureSet        MapView.cpp     332
>  7       MapView::paintEvent     MapView.cpp     190
>  8       QWidget::event  qwidget.cpp     7687
>  9       MapView::event  MapView.cpp     1172
>  10      QApplicationPrivate::notify_helper      qapplication.cpp
>  4056
>  11      QApplication::notify    qapplication.cpp        4021
>  12      QCoreApplication::notifyInternal        qcoreapplication.cpp
>  610
>  13      QCoreApplication::sendSpontaneousEvent  qcoreapplication.h
>  216
>  14      QWidgetPrivate::drawWidget      qwidget.cpp     5079
>  15      QWidgetBackingStore::sync       qbackingstore.cpp       1261
>  16      QWidgetPrivate::syncBackingStore        qwidget.cpp     1603
>  17      QWidget::event  qwidget.cpp     7827
>  18      QMainWindow::event      qmainwindow.cpp 1399
>  19      QApplicationPrivate::notify_helper      qapplication.cpp
>  4056
>  20      QApplication::notify    qapplication.cpp        4021
>  ...     <More>
>  }}}
>
> --
> Ticket URL: <http://trac.osgeo.org/ggl/ticket/17>
> GGL <http://geometrylibrary.geodan.nl>
> Generic Geometry Library
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/ggl/attachments/20090929/d91bb84b/attachment.html