Geometry Boost List: Re: [geometry] access violation in update_discarded(...)

Subject: Re: [geometry] access violation in update_discarded(...)
From: Menelaos Karavelas (menelaos.karavelas_at_[hidden])
Date: 2014-10-29 12:31:56

Hi Valentin.

Thanks for the report. I think with this information we will be able to 
track down the problem.
In the meantime I suggest that either you of Volker file a bug report.

Many thanks.

Best,

- m.

On 29/10/2014 06:26 ??, Valentin Ziegler wrote:
>
> 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_at_[hidden] 
> <mailto:vziegler_at_[hidden]>
> Senior Software Engineer
>
>
> *We are looking for C++ Developers:* http://www.think-cell.com/career
> ------------------------------------------------------------------------
> think-cell Software GmbH 	http://www.think-cell.com 
> <http://www.think-cell.com/>
> Chausseestr. 8/E 	phone / fax 	[phone] / -19
> 10115 Berlin, Germany 	US phone / fax 	[phone]
> Amtsgericht Berlin-Charlottenburg, HRB 85229 | European Union VAT Id 
> DE813474306
> Directors: Dr. Markus Hannebauer, Dr. Arno Schödl
>
>
> *From:*Geometry [mailto:geometry-bounces_at_[hidden]] *On Behalf 
> Of *Volker Schöch
> *Sent:* Montag, 27. Oktober 2014 18:40
> *To:* Boost.Geometry library mailing list (geometry_at_[hidden] 
> <mailto:geometry_at_[hidden]>)
> *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
>
> _intPolygonpolygonA;
>
>        boost::geometry::read_wkt("MULTIPOLYGON(((488 2035,527 2035,527 
> 2093,488 2093)))", polygonA); // does not throw
>
> _intRectrectB;
>
>        boost::geometry::read_wkt("BOX(417 2064,597 2064)", rectB); // 
> does not throw
>
> _intPolygonpolygonC;
>
>        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
>
>
>
> _______________________________________________
> Geometry mailing list
> Geometry_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/geometry