CGAL users discussion list

[Nicholas Mario Wardhana <>]

On 2 March 2012 18:51, Sebastien Loriot (GeometryFactory)
<>
 wrote:
> Maybe another optimization problem.
> Can you provide a minimal example showing the problem?
>
> Sebastien.
>
>
> On 03/02/2012 11:32 AM, Nicholas Mario Wardhana wrote:
>>
>> Dear all,
>>
>> Given an input point in 3D space, I am trying to find the closest
>> point in a list of thousands to tens of thousands of points. However,
>> I often got the following assertion error.
>>
>> CGAL error: assertion violation!
>> Expression : new_rd>= copy_rd
>> File       : D:\nixx\Documents\Visual Studio
>> 2008\Projects\Testbed\dependencies\
>> CGAL-3.9\include\CGAL/Orthogonal_incremental_neighbor_search.h
>> Line       : 267
>> Explanation:
>> Refer to the bug-reporting instructions at
>> http://www.cgal.org/bug_report.html
>>
>> Sometimes the error is in line 288 instead. I am wondering if somebody
>> can give me a clue about what causes this error? The list of points is
>> generated from a preceding algorithm, so I suspect there were some
>> mistakes in it.
>>
>> The strange thing is that results might vary in Debug and Release
>> configurations. There was one time when I wanted to debug the code by
>> inputting the point which previously gave error, but it turned out
>> that no error was produced.
>>
>> I found this thread:
>>
>>
>> http://cgal-discuss.949826.n4.nabble.com/Spatial-Searching-How-to-cope-with-duplicate-points-td3002341.html
>>
>> but the patch posted by Dr Loriot there does not work for me, as it
>> caused some tens to hundreds of compilation errors. I also suppose
>> that there is no duplicate point in the list.
>>
>> I use CGAL 3.9 and Boost 1.48, and compile my code using Visual Studio
>> 2008 on both Windows Vista and Windows 7. Please let me know if I need
>> to give more information.
>>
>> By the way, I am presently upgrading the Boost library, and afterwards
>> I will rebuild CGAL rebuild my project again, so I will see whether
>> there will still be an error after this.
>>
>> Thank you very much!
>>
>> Best regards,
>> Nicholas
>>
>
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss
>

Thank you very much for your quick reply, Dr. Loriot!

As for the minimum example, let's see if I can do it, as the error
seems to depend on the list of points. Previously, I tested with 1000
collinear points along z axis (that is, (0, 0, 0) to (0, 0, 1000),
with a distance of 1 for every pair of nearby points), and it was
fine. I will try to generate a new list of points which is small
enough to be hard-coded.

For now, I can give the following snippet.

// ---------------- Snippet starts here ----------------

typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef CGAL::Point_3<Kernel>  Point;
typedef CGAL::Search_traits<double, CGAL3DPointNNS<NNSData>, const
double*, ConstructCoordIterator<NNSData>> TreeTraits;
typedef CGAL::Orthogonal_incremental_neighbor_search<TreeTraits,
NNSDistance<NNSData>> NeighbourSearch;
typedef typename NeighbourSearch::Tree Tree;

// ...

CGAL3DPointNNS<NNSData> query = CGAL3DPointNNS<NNSData>(rkInput.x,
rkInput.y, rkInput.z, NNSData());
Tree tree(m_pointList.begin(), m_pointList.end());
NeighbourSearch search(tree, query);
rSortedNeighbourList.clear();
rDataList.clear();
rSquaredDistanceList.clear();

for(NeighbourSearch::iterator neighbourIterator = search.begin();
        neighbourIterator != search.end();
        neighbourIterator++)
{
        // Assertion violation happens somewhere in this loop!
        Vec3 point(neighbourIterator->first.x(),
neighbourIterator->first.y(), neighbourIterator->first.z());
        rSortedNeighbourList.push_back(point);
        rDataList.push_back(neighbourIterator->first.data);
        rSquaredDistanceList.push_back(neighbourIterator->second);
}

// ---------------- Snippet ends here ----------------

Some explanations about the classes and variables:
- CGAL3DPointNNS is based on the class Point in

http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Spatial_searching/Chapter_main.html#Subsection_60.3.5
,

- NNSData is a data class which I embed in every point in the space
- Vec3 is our implementation of point in 3D space
- m_pointList is the list of points
- rkInput is the input point, whose closest point in m_pointList is to be 
found
- rSortedNeighbourList is an output parameter to store the list of
points, sorted by distance to rkInput
- rDataList is the similarly sorted list of NNSData variables
- rSquaredDistanceList is the similarly sorted list of squared
distance of points in rSortedNeighbourList

The error comes up when I iterate through the for loop. Unfortunately,
as I mentioned in my previous e-mail, for some random points which I
input manually, it didn't give any error when I debugged the code in
Debug configuration.

Thank you!

Best regards,
Nicholas