CGAL users discussion list

[Alessandro Attanasi <>]

Hi all,

thanks for the replies, I read all the documentation on convex hull 2D before using it and to be specific to this problem the key sentence from the manual is:

"The function ch_graham_andrew_scan() generates the counterclockwise sequence of extreme points from a given set of input points that are not left of the line defined by the first and last points in this sequence."

As I interpreted it, I first gave to the function the result of a previous convex hull computation obtaining what I was expecting, i.e. a subset of point of the input hull that are between the the two point p and q that I specified (this is in line with the Panos' reply for which input points has to be sorted). After that I asked myself what's happening if I feed the function with points belonging to a convex hull but they not define ccw polygon, or if more generally I feed the function with a generic set of points. The function returns to me something and I was asking myself if it was right. 

Into the manual I read after the ch_graham_anderson() example  the precondition 

"The range [first,beyond) contains at least two different points. The points in [first,beyond) are sorted with respect to pq, i.e. the sequence of points in [first,beyond) define a counterclockwise polygon, for which the Graham-Sklansky-procedure [11] works"

that I was thinking was related only to the example, maybe not, it is general. 

However, sorry if I was boring yourself with my questions, or worst if I was wasting your time. I'm going to learn the library and I have on one desktop the manual every time open, I really want to use it because I think it is really a valuable resource to implement computational geometry algorithms. If the mailing-list is devoted only to bug problems, ok I stop immediately myself to post other stuff, learning the library by myself doing mistakes and hoping to find the solution in some way.

As a software developer I know how difficult and time expansive is to write clear and accurate documentation, and your documentation is really good so for sure I interpreted it in a bad way, sorry again.

The reason for which I was playing with the function in that strange ways is that I used to stressed library functions in many ways in order to deep understand its behaviour, because before using an external library I would be sure to don't use it in an inappropriate way into a my software.

Best

Alessandro

On 19 January 2014 11:15, Andreas Fabri <> wrote:

Alessandro,

What about reading the manual before USING something???

http://doc.cgal.org/latest/Convex_hull_2/group__PkgConvexHull2Subsequence.html#gafa026d25f9fee686e7a58af0ff365f86


andreas

On 18/01/2014 23:25, Alessandro Attanasi wrote:

Hi,

I'm not understanding the behaviour of the graham_andrew_scan()

what should I expect if I have the following points?


                q7
                           q4
q1     q2      q3
                           q5
                q6

  q1  (-1,0)
  q2  (0,0)
  q3  (1,0)
  q4  (2,1)
  q5  (2,-1)
  q6  (1.5,-2)
  q7  (1.5,2)

I filled a std::vector<Point_2> scan_test with this points in the order
given by the numbers above, then I called

CGAL::graham_andrew_scan(scan_test.begin(),scan_test.end(),std::back_inserter(scan_result));

being std::vector<Point_2> scan_result.

And as result I obtained

q1,q3,q4 into scan_result. Why?

Thanks
Alessandro

--
Andreas Fabri, PhD
Chief Officer, GeometryFactory
Editor, The CGAL Project

phone: +33.492.954.912    skype: andreas.fabri

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss

--

http://giovanninoperdigiorno.blogspot.it/

http://giovanninocartoons.blogspot.it/

https://gist.github.com/alecsphys