Hi,
I investigated Volker's example and found the problems are caused by undefined behaviour within the comparison function object
sort_on_segment_and_ratio, which is used for sorting vectors of
indexed_turn_operation.
Running Volker's code, we get into the following callstack:
copy_segment_point(... SegmentIdentifier const& seg_id, .... )
copy_segment_points(...)
sort_on_segment_and_ratio::get_situation_map(...)
sort_on_segment_and_ratio::consider_relative_order(...)
sort_on_segment_and_ratio::operator()(...)
std::sort(...)
enrich_sort(...)
enrich_intersection_points(...)
...
difference(polygonA, rectB, polygonC);
...
Note that the seg_id argument for copy_segment_point is taken from the indexed turn operations being compared (i.e., either subject.seg_id or
subject.other_id).
If seg_id.source_index == -1, copy_segment_points does not copy any data, thus the computation continues with random junk values from the stack :-(
This is exactly what happens in Volker's example, as some of the turning points have other_id.source_index == -1.
As a consequence,
sort_on_segment_and_ratio::operator()(...) gives nondeterministic comparision results which confuses Visual Studio's std::sort implementation so much that it starts writing to memory locations outside
the input range (Please note that this is NOT a bug of std::sort).
I do not have the expertise to tell where these negative source_index values come from and whether these values are to be expected or if they arise due to some
issue. It would be nice if someone could look into this.
Valentin
--
Valentin Ziegler | vziegler@think-cell.com
Senior Software Engineer
| think-cell Software GmbH | http://www.think-cell.com | |
| Chausseestr. 8/E | phone / fax | +49 30 666473-10 / -19 |
| 10115 Berlin, Germany | US phone / fax | +1 800 891 8091 / +1 212 504 3039 |
| Amtsgericht Berlin-Charlottenburg, HRB 85229 | European Union VAT Id DE813474306 | ||
| Directors: Dr. Markus Hannebauer, Dr. Arno Schödl | ||
From: Geometry [mailto:geometry-bounces@lists.boost.org]
On Behalf Of Volker Schöch
Sent: Montag, 27. Oktober 2014 18:40
To: Boost.Geometry library mailing list (geometry@lists.boost.org)
Subject: Re: [geometry] access violation in update_discarded(...)
Hi,
Unfortunately I have not hear from you in this regard. It seems that I still cannot reliably reproduce the issue, but when it occurs, it occurs
in the following scenario. Apparently, something is broken in your memory management:
{
// RT#8837
_intPolygon polygonA;
boost::geometry::read_wkt("MULTIPOLYGON(((488
2035,527 2035,527 2093,488 2093)))", polygonA);
// does not throw
_intRect rectB;
boost::geometry::read_wkt("BOX(417
2064,597 2064)", rectB);
// does not throw
_intPolygon polygonC;
boost::geometry::difference(polygonA, rectB, polygonC);
// ACCESS VIOLATION
}
Maybe you could make an effort and step through this simple example once to see if everything works as expected?
I understand that the box and/or the polygon may not conform to all requirements (not spike-free etc.) but in any case, IMO the geometry library
should not crash with a memory fault.
As always, my
points are based on int and my polygons are counter-clockwise and
not closed.
Regards
Volker