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

Subject: Re: [geometry] access violation in update_discarded(...)
From: Valentin Ziegler (vziegler_at_[hidden])
Date: 2014-10-29 12:26:52

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
>
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
       _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