ASSERT when intersecting "criss-crossed" polygon with box

[koying]

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>			

[barendgehrels]

I'll have a look. Do you happen to have the coordinates in text-form?

[koying]

Mmm... I'm not notified of updates on the ticket...

Whatever:

• The coordinates are -122.3731, 37.3472, -122.2243, 37.4983

• If you are using merkaartor:
  • The Merkaartor ticket:  http://trac.openstreetmap.org/ticket/2317
  • I also attach a .MDC with only the problematic polygon

[barendgehrels]

Reproduction of problem in test environment

[barendgehrels]

Chris,

In test environment the problem didn't show up. However, the assertion was clear enough. I changed the implementation by returning in a possibly endless loop. Does this solve the problem for this case?

Furthermore, there will be a function "is_simple" returning TRUE if it does not have self-intersections. This will help to avoid this problem.

Regards, Barend

[koying]

If you tried with Merkaartor, sorry, I forgot to mention that you have to zoom in a couple of time for the assertion to trigger (As clipping is costly, I only clip when the canvas would become too memory hungry).

What will be the result of the intersection with your patch, all (i.e. the original polygon) or nothing?

[barendgehrels]

Zoomed in version

[barendgehrels]

Zoomed in indeed reproduces the problem.

The new behaviour is a polygon with rings as long as they are successfully generated. So in this case 2 rings, the third ring was aborted because of the criss-crossing. See last attachment.

[koying]

Notification test by Chris

[mloskot]

Test if ticket update notification will be sent to Chris and others.

[koying]

Actually, if I zoom as far as ticket17_reproduce2.png with the current patch, I receive no rings/polygons at all...

PS: I didn't receive Mateusz's update notification, wether personally or thru the list... Did the others received it thru the list?

[barendgehrels]

- didn't get notifications indeed

- What you get might be dependant on order. So sometimes nothing might be possible. I'll relook to the problem in the weekend, to solve it more structurally.

[koying]

Replying to barendgehrels:

- What you get might be dependant on order. So sometimes nothing might be possible. I'll relook to the problem in the weekend, to solve it more structurally.

As far as I'm concerned, the "is_simple" function (or any other mean, like an exception) is fine. I'd just bypass clipping in this (rare) case.

[barendgehrels]

I proposed is_simple but it leads (for the moment) to confusion. I've created an 'intersects' function that should check if two polygons intersect, and can also be used for one polygon to check self-intersections. You can use that one.

Alternatively you can now also call get_intersection_points with one polygon (and an intersection-point-vector) to get all self-intersection points.

This is probably enough to close this ticket (I did)

The behaviour of traverse should still be that it continues even with self-intersecting polygons but that is not yet implemented.

[barendgehrels]

Traversal is now enhanced in the sense that if invalid polygons are encountered, what is built up is outputted and the process continues. This means that the output polygons, in those case, are still not valid. But at least you see something, and there is no assertion of exception, and some might be not too bad.

To change this structurally, self-intersections should be tested as well. We don't want to do this always, but it could be done iff these kinds of anomalies occur. However, that requires some changes that should be planned later.

Actually this is all to handle polygons that were asummed invalid when designing the algorithm. The algorithm assumes that the inside of a polygon is always on the right side. In these cases, it is not. Therefore, the intersection of these polygons might contain an area that was not inside any input polygon.

[koying]

Grmbl... Those non-notifications are really bugging!

Thanks, I'll test that.