Segmentation fault

[nowy20180820]

  #include<iostream>
#include<cstdlib>

using namespace std;

/* Implements a divide-and-conquer, prune-and-search,triangular expansion
algorithm to find the convex hull of points in the plane.*/

struct Point
{
    float x,y;
};

struct SetElement
{
    Point info;
    SetElement *next;
};

struct PointSet
{
    SetElement *front,*rear,*current;
};

//PointSet operations

void NewSet(PointSet &S)
// Creates a new PointSet S
{
    S.front = new SetElement;
    S.rear = S.front;
    S.current = S.front;
}

void Reset(PointSet &S)
//Moves the current position within PointSet S to the beginning
{
    S.current = S.front->next;
}

void Include(Point p,PointSet &S)
//Includes a point p in PointSet S
{
    SetElement *element;
    element = new SetElement;
    element->info = p;
    element->next = nullptr;
    S.rear->next = element;
    S.rear = element;

}

Point CurrentPoint(PointSet S)
//Returns the value of the current point in PointSet S
{
    return S.current->info;
}

void Advance(PointSet &S)
//Advances the current pointer in PointSet S
{
    S.current = S.current->next;
}

bool Empty(PointSet S)
//Determines if PointSet S is empty
{
    return (S.front->next == nullptr);
}

bool MorePoints(PointSet S)
//Determines if the current pointer of PointSet S is at the end
{
    return S.current != nullptr;
}

void Remove(Point &p,PointSet &S)
//Removes and returns a point p from (non-empty) PointSet S
{
    SetElement *element;
    element = S.front->next;
    p = element->info;
    S.front->next = element->next;
    delete element;
}

void Eliminate(PointSet &S)
//Eliminates PointSet S
{
    Point pt;
    while(!Empty(S)){
        Remove(pt,S);
    }
}

//QuickHull IO routines

void InputSet(PointSet &data)
//Eliminates PointSet S
{
    int n,i;
    Point p;
    cin>>n;
    NewSet(data);
    for(i = 1;i<=n;i++)
    {
        cin>>p.x>>p.y;
        Include(p,data);
    }
}

void OutputPoint(Point p)
//Outputs point p
{
    cout<<p.x<<" "<<p.y<<"\n";
}

//Algorithm tools

float ScaledDistance(Point u,Point v,Point p)
/*Finds the distance between vector uv and point p, scaled by
the length of vector uv*/
{
    return (v.x - u.x) * (p.y - u.y) - (v.y - u.y)*(p.x - u.x);
}

float Direction(Point u,Point v,Point p)
//Finds the (scaled) signed distance between vector uv and point p
{
    return (v.x - u.x) * (p.y - u.y) - (v.y - u.y)*(p.x - u.x);
}

float Projection(Point u,Point v,Point p)
/*Finds the parallel projection of point p onto vector uv, scaled
by the length of vector uv*/
{
    return (v.x - u.x) * (p.x - u.x) + (v.y - u.y) * (p.y - u.y);
}

void Select(Point &p,Point &q,PointSet S)
//Selects two primary vertices p and q from a (non-empty) set S
{
    Point pt;
    Reset(S);
    q = CurrentPoint(S);
    p = q;
    Advance(S);
    while(MorePoints(S)){
        pt = CurrentPoint(S);
        if((pt.y < q.y)||((pt.y == q.y)&&(pt.x < q.x))){
            q = pt;
        }
        else if((pt.y > p.y)||((pt.y == p.y) && (pt.x > p.x))){
            p = pt;
        }
        Advance(S);
    }
}

void Split(Point p,Point q,PointSet &S,PointSet &R,PointSet &L)
/*Splits S into sets R and L, to the rright and left of baseline pq,
respectively*/
{
    float dir;
    Point pt;
    NewSet(R);
    NewSet(L);
    while(!Empty(S)){
        Remove(pt,S);
        dir = Direction(p,q,pt);
        if(dir > 0.0){ // point is on the right
            Include(pt,R);
        }
        else if(dir < 0.0){ // point is on the left
            Include(pt,L);
        }
    }
}

void PruneAndSplit(Point p,Point q,Point r,PointSet &S,PointSet &U,PointSet &L)
/*Selects the upper and lower outside sets, U and L, for baseline pq
and farthest-point r*/
{
    PointSet internal;
    Split(p,r,S,U,internal);
    Split(r,q,internal,L,internal);
    Eliminate(internal);
}

Point FarthestPoint(Point p,Point q,PointSet S)
//Finds a point in (non-empty) S farthest from baseline pq
{
    float maxdist,dist;
    Point u,r,pt;
    maxdist = 0.0;
    Reset(S);
    while(MorePoints(S)){
        pt = CurrentPoint(S);
        dist = ScaledDistance(p,q,pt);
        if(dist > maxdist){
            maxdist = dist;
            r = pt;
        }
        else if(dist == maxdist){
             //compare parallel projections along the baseline
            if(Projection(p,q,pt) > Projection(p,q,r)){
                maxdist = dist;
                r = pt;
            }
        }
        Advance(S);
    }
    return r;
}

//Main Algorithm

void QuickHull(Point p, Point q,PointSet &S)
/*Finds the convex hull of S given that p and q  are primary vertices
and S lies to the right of baseline pq*/
{
    Point r;
    PointSet U,L;
    if(!Empty(S)){
        r = FarthestPoint(p,q,S);
        PruneAndSplit(p,q,r,S,U,L);
        QuickHull(p,r,U);
        OutputPoint(r);
        QuickHull(r,q,L);
    }
}

int main()//Hull
{
    PointSet S,L,R;
    Point p,q;
    InputSet(S);
    cout<<"\n";
    Select(p,q,S);
    Split(p,q,S,R,L);
    OutputPoint(p);
    QuickHull(p,q,R);
    OutputPoint(q);
    QuickHull(q,p,L);
    system("PAUSE");
    return 0;
}

I get following message

Program received signal SIGSEGV, Segmentation fault.
At F:\quick_hull.cpp:82
#0 0x401491 Remove(p=..., S=...) (F:\quick_hull.cpp:82)
#1 0x4017c6 Split(p=..., q=..., S=..., R=..., L=...) (F:\quick_hull.cpp:170)
#2 0x4018c6 PruneAndSplit(p=..., q=..., r=..., S=..., U=..., L=...) (F:\quick_hull.cpp:187)
#3 0x401ae5 QuickHull(p=..., q=..., S=...) (F:\quick_hull.cpp:227)
#4 0x401c1e main() (F:\quick_hull.cpp:243)

I thought thet error is in Remove function
and tried to surround it by try catch
or if statement but it was unsuccessfull

[Duthomhas]

Your naming is a bit at odds with the logic, and the logic is a bit spread out. You’ll have to give me a little bit to examine your code.

But... I can already tell you that the problem is either a hanging pointer or a bounds failure due to a bookkeeping failure when pruning.

This looks a bit over the top for a convex hull algorithm, but again, give me a short bit...

[nowy20180820]

How can I use debugger from Code::Blocks IDE to get more information
about this error
Are there good tutorials how to use debugger ?

Will informations about algorithm which is used here be helpful for avoiding this error

I found text about Quickhull with example code in Pascal
Pascal code has the same kind of error
Text is nearly 30 years old

Here is Algorithm description
https://surface.syr.edu/eecs_techreports/65/


In Debugging Window -> Memory dump
i get message

"Cannot access memory at address 0x0"

It probably means that program tries to dereference null pointer
but I dont see it in lines shown at call stack

[Duthomhas]

Alas, that algorithm (https://surface.syr.edu/cgi/viewcontent.cgi?referer=https://www.google.com/&httpsredir=1&article=1058&context=eecs_techreports) is bogus. It looks like it should be very straight-forward, but there are a few wrinkles that aren’t quite right, and the math for this kind of stuff is fickle if you aren’t really careful. The fact that the algorithm nearly duplicates itself with minor variations is a bit of a red flag to me as well.

Anyway, I’m done looking at it for the day, so, sorry, not much help. I’ll probably mess with it again.

Is this homework? Must you use this algorithm?

You have a number of dangling pointers right from the start that are messing you up. Be very careful on your linked list initializations. And, as I said, I haven’t quite finished analyzing the correct flow of the algorithm. Maybe I’m being dense and missing something, but until it clicks in my brain I cannot really speculate intelligently on what else could be going wrong.

(If you don’t have to use this algorithm, there is a standard O(n log n) algorithm called Andrew’s Monotone Chain which is exceedingly simple to implement and very quick —the sorting is actually more complicated than the hull selection.)

Anyway, give me a day or two and I’ll look at it again. Sorry.

[lastchance]

@nowy20180820

Could you try this, please. There were a multitude of problems with your linked list and an error in your prune and split routine.

I didn't have problems with the basic algorithm.

https://imgur.com/DgsEGJp

#include<iostream>
#include<cstdlib>

using namespace std;

//*************************************************************************
// Implements a divide-and-conquer, prune-and-search,triangular expansion *
// algorithm to find the convex hull of points in the plane.              *
//*************************************************************************


struct Point
{
    float x,y;
};

struct SetElement
{
    Point info;
    SetElement *next = nullptr;
};

struct PointSet
{
    SetElement *front = nullptr, *rear = nullptr;
};


//************************
// Added for convenience *
//************************
ostream &operator << ( ostream &str, const Point &p ) 
{
    return str << p.x << ", " << p.y;
}

ostream &operator << ( ostream &str, const PointSet &S )
{
    SetElement *element = S.front;
    while ( element != nullptr )
    {
        str << element->info << "\n";
        element = element->next;
    }
    return str;
}



//**********************
// PointSet operations *
//**********************

void Include( Point p, PointSet &S )
// Includes a point p at the end of PointSet S
{
    SetElement *element = new SetElement;
    element->info = p;
    element->next = nullptr;

    if ( S.rear == nullptr ) S.front      = element;
    else                     S.rear->next = element;
    S.rear = element;
}

bool Empty( PointSet S )
// Determines if PointSet S is empty
{
    return ( S.front == nullptr );
}

void Remove( Point &p, PointSet &S )
// Removes and returns a point p from (front of non-empty) PointSet S
{
    SetElement *element = S.front;
    p = element->info;
    S.front = element->next;
    if ( S.front == nullptr ) S.rear = nullptr;
    delete element;
}

void Eliminate(PointSet &S)
// Eliminates PointSet S
{
    Point pt;
    while( !Empty( S ) )
    {
        Remove( pt, S );
    }
}



//************************
// QuickHull IO routines *
//************************

void InputSet( PointSet &S )
// Inputs set of points
{
    int n, i;
    Point p;
    cin >> n;
    for ( i = 1; i <= n; i++ )
    {
       cin >> p.x >> p.y;
       Include( p, S );
    }
}


//******************
// Algorithm tools *
//******************

float ScaledDistance ( Point u, Point v, Point p )
// Finds the distance between line vu and point p (multiplied by length vu)
// Equals z component of vp cross vu
{
    return ( p.x - v.x ) * ( u.y - v.y ) - ( p.y - v.y ) * ( u.x - v.x );
}

float Direction( Point u, Point v, Point p )
// Gives the signed turn vp to vu (+ve means right)
// Comes from z component of vp cross vu (just like above!)
{
    return ( p.x - v.x ) * ( u.y - v.y ) - ( p.y - v.y ) * ( u.x - v.x );
}

float Projection(Point u,Point v,Point p)
// Finds the projection of p onto vector vu (multiplied by length vu)
// Comes from vp dot vu
{
    return ( p.x - v.x ) * ( u.x - v.x ) + ( p.y - v.y ) * ( u.y - v.y );
}

void Select( Point &p, Point &q, PointSet S )
// Selects two primary vertices p and q from a (non-empty) set S
// Such that p is largest y and q is smallest y (or rightmost or leftmost if a tie)
{
    Point pt;
    SetElement *element = S.front;
    q = element->info;
    p = q;
    element = element->next;
    while( element != nullptr )
    {
        pt = element->info;
        if ( ( pt.y < q.y ) || ( pt.y == q.y && pt.x < q.x ) ) q = pt;
        if ( ( pt.y > p.y ) || ( pt.y == p.y && pt.x > p.x ) ) p = pt;
        element = element->next;
    }
}

void Split( Point p, Point q, PointSet &S, PointSet &R, PointSet &L )
// Splits S into sets R and L, to the right and left of baseline pq, respectively
{
    float dir;
    Point pt;
    while( !Empty( S ) )
    {
        Remove( pt, S );
        dir = Direction( p, q, pt );
        if ( dir > 0.0 ) Include( pt, R );
        if ( dir < 0.0 ) Include( pt, L );
    }
}

void PruneAndSplit( Point p, Point q, Point r, PointSet &S, PointSet &U, PointSet &L)
// Selects the upper and lower outside sets, U and L, for baseline pq and farthest-point r
{
    PointSet internal1, internal2;
    Split( p, r, S, U, internal1 );
    Split( r, q, internal1, L, internal2 );
    Eliminate( internal2 );
}

Point FarthestPoint( Point p, Point q, PointSet S )
// Finds a point in (non-empty) S farthest from baseline pq
{
    float maxdist, dist;
    Point r, pt;
    maxdist = 0.0;
    SetElement *element = S.front;
    while( element != nullptr )
    {
        pt = element->info;
        dist = ScaledDistance( p, q, pt );
        if( dist > maxdist )
        {
            maxdist = dist;
            r = pt;
        }
        else if ( dist == maxdist )
        {
            //compare parallel projections along the baseline
            if( Projection( p, q, pt ) > Projection( p, q, r ) )
            {
                maxdist = dist;
                r = pt;
            }
        }
        element = element->next;
    }
    return r;
}

//Main Algorithm

void QuickHull( Point p, Point q, PointSet &S )
/*Finds the convex hull of S given that p and q  are primary vertices
and S lies to the right of baseline pq*/
{
    Point r;
    PointSet U, L;
    if ( !Empty( S ) )
    {
        r = FarthestPoint( p, q, S );
        PruneAndSplit( p, q, r, S, U, L );
        QuickHull( p, r, U );
        cout << r << '\n';
        QuickHull( r, q, L );
    }
}




int main()      
{
    PointSet S, L, R;
    Point p, q;

    InputSet( S );
    Select( p, q, S );
    Split( p, q, S, R, L );
    cout << p << '\n';
    QuickHull( p, q, R );
    cout << q << '\n';
    QuickHull( q, p, L);
//  system("PAUSE");
}

Points file for testing (redirect to input from command line):
50
0  6
4  9
1  0
1  4
4  9
4  5
2  6
4  8
5  6
4  7
3  3
1  5
4  7
1  3
5  6
2  7
7  1
2  1
1  2
4  6
9  8
5  8
8  5
3  4
9  1
0  6
7  7
0  0
9  0
9  4
8  6
6  5
8  5
4  0
4  4
9  4
6  7
0  0
8  7
8  1
7  7
5  1
7  5
9  1
8  5
3  5
1  3
1  8
9  2
8  6

[Duthomhas]

lastchance has again saved the day!

:O)

It’s nice to have time to play.

[nowy20180820]

No it is not a homework
I had Jarvis and Graham at school but it was approximately 15 years ago

English is not my native language but I also think that their vesion of algorithm
is not as buggy as Duthomhas claims

I at the beginning suspected that problem is in memory management
for their data stucture but I cant localize and fix error

I only translated their code
Lastchance you corrected it and i think that you are the person
who should send them proposition for code correction


lastchance do you know any good OpenGL tutorials
I have downloaded freeglut with glew and i would like to
illustrate this algorithm

Thanks guys especially for you lastchance

[lastchance]

@nowy20180820

nowy20180820 wrote:

lastchance do you know any good OpenGL tutorials

I'm afraid that I don't use OpenGL. If I want to do any serious graphics or write GUIs then I use dislin. However, for just plotting points and lines in the plane, as I did here, I simply redirected input and output from the command line:
a.exe < pts.in > pts.out
and then used GnuPlot.

Your algorithm was actually quite straightforward to follow, as it was tied very closely to the paper that you linked to. I actually quite liked the algorithm. Most of the errors came from the linked list. I know how to use pointers and allocate objects on the heap in both C++ and Fortran, but your routines didn't look like they had been translated from those, so I largely had to rewrite them. You mentioned Pascal, but I've never used it.

If the original code is as old as you suggest then it probably precedes the standardisation of C++. In particular, it wouldn't have had any of the STL library available. For what you did with your containers here (added points, iterated through them, removed points) I think you would do better by using a standard C++ container. I hope that you don't mind, but I took the liberty of rewriting your code, removing all the user-defined linked list and simply using std::vector, specifically std::vector<Point>. That way you can be sure of the memory management.

I have also slightly simplified your algorithm; for example the "direction" and "scaled distance" routines are essentially the same code, albeit used for different purposes. I've also overloaded the stream operators << and >> for Point. You can tailor them to your own needs.

#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;


//*************************************************************************
// Implements a divide-and-conquer, prune-and-search,triangular expansion *
// algorithm to find the convex hull of points in the plane.              *
//*************************************************************************

struct Point
{
   double x, y;
};



//**************
// IO routines *
//**************

ostream &operator << ( ostream &str, const Point &p )
{
   return str << p.x << ", " << p.y;
}


istream &operator >> ( istream &str, Point &p )
{
   return str >> p.x >> p.y;
}


void Input( vector<Point> &S )
// Input points
{
   int n;
   cin >> n;

   Point pt;
   for ( int i = 0; i < n; i++ )
   {
      cin >> pt;
      S.push_back( pt );
   }
}



//******************
// Algorithm tools *
//******************

double ScaledDistance( Point u, Point v, Point p )
// Finds the signed distance between line vu and point p (multiplied by length vu)
// Equals z component of vp cross vu. 
// Positive means right; negative means left
{
   return ( p.x - v.x ) * ( u.y - v.y ) - ( p.y - v.y ) * ( u.x - v.x );
}

double Projection( Point u, Point v, Point p )
// Finds the projection of p onto vector vu (multiplied by length vu)
// Comes from vp dot vu
{
   return ( p.x - v.x ) * ( u.x - v.x ) + ( p.y - v.y ) * ( u.y - v.y );
}

void Select( Point &p, Point &q, const vector<Point> &S )
// Selects two primary vertices p and q from a (non-empty) set S
// Such that p is largest y and q is smallest y (or rightmost or leftmost if a tie)
{
   q = p = S[0];
   for ( int i = 1; i < S.size(); i++ )
   {
      Point pt = S[i];
      if ( pt.y < q.y || ( pt.y == q.y && pt.x < q.x ) ) q = pt;
      if ( pt.y > p.y || ( pt.y == p.y && pt.x > p.x ) ) p = pt;
   }
}

void Split( Point p, Point q, vector<Point> &S, vector<Point> &R, vector<Point> &L )
// Splits S into sets R and L, to the right and left of baseline pq, respectively
{
   for ( Point pt : S )
   {
      double d = ScaledDistance( p, q, pt );
      if ( d > 0.0 ) R.push_back( pt );
      if ( d < 0.0 ) L.push_back( pt );
   }
   S.clear();
}

void PruneAndSplit( Point p, Point q, Point r, vector<Point> &S, vector<Point> &U, vector<Point> &L)
// Selects the upper and lower outside sets, U and L, for baseline pq and farthest-point r
{
   vector<Point> internal1, internal2;
   Split( p, r, S, U, internal1 );
   Split( r, q, internal1, L, internal2 );
}

Point FarthestPoint( Point p, Point q, const vector<Point> &S )
// Finds a point in (non-empty) S farthest from baseline pq
{
   double maxdist = 0.0;
   Point r;
   for ( Point pt : S )
   {
      double dist = ScaledDistance( p, q, pt );
      if ( dist > maxdist )
      {
         maxdist = dist;
         r = pt;
      }
      else if ( dist == maxdist )
      {
         if ( Projection( p, q, pt ) > Projection( p, q, r ) )
         {
            maxdist = dist;
            r = pt;
         }
      }
   }
   return r;
}


//****************
//Main Algorithm *
//****************

void QuickHull( Point p, Point q, vector<Point> &S )
// Finds the convex hull of S given that p and q  are primary vertices
// and S lies to the right of baseline pq
{
   vector<Point> U, L;
   if ( !S.empty() )
   {
      Point r = FarthestPoint( p, q, S );
      PruneAndSplit( p, q, r, S, U, L );
      QuickHull( p, r, U );
      cout << r << '\n';
      QuickHull( r, q, L );
   }
}




int main()      
{
   vector<Point> S, L, R;
   Point p, q;

   Input( S );
   Select( p, q, S );
   Split( p, q, S, R, L );
   cout << p << '\n';
   QuickHull( p, q, R );
   cout << q << '\n';
   QuickHull( q, p, L);
}

[nowy20180820]

I translated Robert Lafore's linked list from Java to C++
In CLRS Introduction to algorithm I found pseudocode for Graham scan
but Robert Lafore's linked list is missing a few useful functions

I have written Jarvis march which seems to be working
but I allocated memory for two linked list and I would like to know
can i get the same efect without allocating memory for second linked list

If I start a new topic will you look at it ?

[nowy20180820]

https://ideone.com/mK1Xj7

Here I have Jarvis code with linked list translated from Lafore Algorithm in Java
and it works without errors like seqmentation fault but here I would like to write
similar main.cpp and got seqmentation fault

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include "DoublyLinkedList.hpp"

using namespace std;

int ScaledDistance(Point u,Point v, Point p)
{
    return (p.x - v.x) * (u.y - v.y) - (p.y - v.y) * (u.x - v.x);
}


int Direction(Point u,Point v, Point p)
{
    return (p.x - v.x) * (u.y - v.y) - (p.y - v.y) * (u.x - v.x);
}

int Projection(Point u, Point v, Point p)
{
    return (p.x - v.x) * (u.x - v.x) + (p.y - v.y) * ( u.y - v.y);
}


void Select( Point &p, Point &q, DoublyLinkedList<Point> &S)
{
    Point pt;
    Link<Point> *element = S.getFirst();
    q = element->getData();
    p = q;
    element = element->getNext();
    while(element != nullptr)
    {
        pt = element->getData();
        if((pt.y < q.y) || (pt.y == q.y && pt.x < q.x)) q = pt;
        if((pt.y > p.y) || (pt.y == p.y && pt.x > p.x)) p = pt;
        element = element->getNext();
    }
}

void Split(Point p, Point q, DoublyLinkedList<Point> &S,DoublyLinkedList<Point> &R,DoublyLinkedList<Point> &L)
{
    int dir;
    Point pt;
    while(!S.isEmpty())
    {
        pt = S.getFirst()->getData();
        S.deleteFirst();
        dir = Direction(p,q,pt);
        if(dir > 0) R.insertLast(pt);
        if(dir < 0) L.insertLast(pt);
    }
}

void PruneAndSplit(Point p, Point q,Point r, DoublyLinkedList<Point> &S,DoublyLinkedList<Point> &U,DoublyLinkedList<Point> &L)
{
    DoublyLinkedList<Point> internal1,internal2;
    Split(p,r,S,U,internal1);
    Split(r,q,internal1,L,internal2);
    while(!internal2.isEmpty())
        internal2.deleteFirst();
}

Point FarthestPoint(Point p,Point q,DoublyLinkedList<Point> S)
{
    int maxdist,dist;
    Point r,pt;
    maxdist = -1;
    Link<Point> *element = S.getFirst();
    while(element != nullptr)
    {
        pt = element->getData();
        dist = ScaledDistance(p,q,pt);
        if(dist > maxdist)
        {
            maxdist = dist;
            r = pt;
        }
        else if(dist == maxdist)
        {
            if(Projection(p,q,pt) > Projection(p,q,r))
            {
                maxdist =  dist;
                r = pt;
            }
        }
        element = element->getNext();
    }
    return r;
}

void QuickHull(Point p,Point q,DoublyLinkedList<Point> &S,DoublyLinkedList<Point> &B)
{
    DoublyLinkedList<Point> U,L;
    Point r;
    if(!S.isEmpty())
    {
        r = FarthestPoint(p,q,S);
        PruneAndSplit(p,q,r,S,U,L);
        QuickHull(p,r,U,B);
        B.insertLast(r);
        QuickHull(r,q,L,B);
    }
}

void Solve(DoublyLinkedList<Point> &A,DoublyLinkedList<Point> &B)
{
    DoublyLinkedList<Point> S,L,R;
    Point p,q;
    Link<Point> *current = A.getFirst();
    while(current != nullptr)
    {
        S.insertLast(current->getData());
        current = current->getNext();
    }
    Select(p,q,S);
    Split(p,q,S,R,L);
    B.insertLast(p);
    QuickHull(p,q,R,B);
    B.insertLast(q);
    QuickHull(q,p,L,B);
}

int main(int argc, char *argv[])
{
    DoublyLinkedList<Point> A;
    DoublyLinkedList<Point> B;
    fstream fin;
    Point p;
    string path("input.txt");
    string line;
    stringstream ss;
    int counter;
    if(argc == 2)
        path=argv[1];
    fin.open(path.c_str(),ios::in);
    if(!fin.good())
          return 1;
    while(getline(fin,line))
    {
       ss.clear();
       ss.str(line);
       counter = 1;
       while(ss)
       {
            try
            {
                switch(counter)
                {
                    case 1:
                    {
                         ss>>p.x;
                         break;
                    }
                    case 0:
                    {
                         ss>>p.y;
                         A.insertLast(p);
                         break;
                    }
                }
            }
            catch(...)
            {

            }
            counter = (counter + 1)%2;
     }
      Solve(A,B);
      cout<<"List A \n";
       A.displayForward();
       A.displayBackward();
       cout<<"List B \n";
       B.displayForward();
       B.displayBackward();
       while(!A.isEmpty())
          A.deleteFirst();
       while(!B.isEmpty())
          B.deleteFirst();
    }
    fin.close();
    system("PAUSE");
    return EXIT_SUCCESS;
}

Command line gdb gave me this log

Currently logging to "gdb.txt".
Future logs will be written to convexHull.log.
Logs will be appended to the log file.
Output will be logged and displayed.
Starting program: F:\ConvexHull\QuickHull\convexHull\bin\Release/convexHull.exe
[New Thread 3152.0x320c]
[New Thread 3152.0x1374]
[New Thread 3152.0x3404]
[New Thread 3152.0x2be0]

Program received signal SIGSEGV, Segmentation fault.
0x00402cf7 in Link<Point>::setPrevious(Link<Point>*) () at F:/ConvexHull/QuickHull/convexHull/Link.hpp:71
71 this->previous = previous;
#0 0x00402cf7 in Link<Point>::setPrevious(Link<Point>*) () at F:/ConvexHull/QuickHull/convexHull/Link.hpp:71
#1 0x00402ac3 in DoublyLinkedList<Point>::deleteFirst() ()
at F:/ConvexHull/QuickHull/convexHull/DoublyLinkedList.hpp:120
#2 0x00401686 in Split(Point, Point, DoublyLinkedList<Point>&, DoublyLinkedList<Point>&, DoublyLinkedList<Point>&) ()
at F:\ConvexHull\QuickHull\convexHull\main.cpp:50
#3 0x0040174f in PruneAndSplit(Point, Point, Point, DoublyLinkedList<Point>&, DoublyLinkedList<Point>&, DoublyLinkedList<Point>&) () at F:\ConvexHull\QuickHull\convexHull\main.cpp:60
#4 0x004019bd in QuickHull(Point, Point, DoublyLinkedList<Point>&, DoublyLinkedList<Point>&) ()
at F:\ConvexHull\QuickHull\convexHull\main.cpp:101
#5 0x00401b65 in Solve(DoublyLinkedList<Point>&, DoublyLinkedList<Point>&) ()
at F:\ConvexHull\QuickHull\convexHull\main.cpp:121
#6 0x00401e27 in main () at F:\ConvexHull\QuickHull\convexHull\main.cpp:171
A debugging session is active.

Inferior 1 [process 3152] will be killed.

Quit anyway? (y or n) error return ../../gdb-7.2/gdb/windows-nat.c:1243 was 5

GDB showed me these lines but what in this code really causes segmentation fault

lastchance i would be pleased more if you explain me how to debug segmentation fault
This code is just an example

[salem c]

A few commands to be getting on with.

1. Print variables (globals, or locals in the current stack frame)
Eg. print this

2. Navigate the call stack
bt - print the call stack
up - go up the stack one level (to the caller)
down - go down one level (to the callee)
frame 3 - go to a specific frame (choose your own number)
list - show the 10 lines of source code around the current location

Sometimes, you can easily figure out what went wrong just from looking at the current state.
But if not, it's time for...

3. Controlling program execution.
The first step is identify some point in the code to stop at.
A few frames back from the crash is as good a place as any.
b PruneAndSplit - breakpoint at the start of a function.
b main.cpp:60 - the same as above, but written as a filename and line number.

4. Go time
run - runs the program, with any command line params that you would use normally.
At some point, the code will hit the breakpoint and return you to the debug prompt.

Then you can proceed with caution using
step - step to next source line, follows function calls.
next - step to next source line, doesn't follow calls (to step over things you know work)
finish - run until the end of this function.
continue - just run until the next breakpoint / crash / program exit.

At each step, you can use the print command to look at the program state.
What you're looking for is anything which doesn't match your expectation.

[lastchance]

@nowy20180820,

Firstly, we can't debug what we can't see.

Secondly, there is nothing in your algorithm that requires a linked list. I have already rewritten your earlier code with a std::vector. Even if you did absolutely require a linked list you should use the one in the standard library. Many of these algorithms were devised in the days before we had dynamically-resizeable containers: now we have many.

Thirdly, from your original post the error is almost certainly in your linked list, not the geometric algorithms. You need to test that SEPARATELY. Write a short driver program - not your convex hull algorithm - to test the individual functions of the linked list: insertion, deletion, find, clear, print out (in both directions).

@salem c has given good advice on the use of a debugger. I can't comment on that as I am old-fashioned enough to put in output statements to find where crashes occur and what variable values are beforehand. More importantly, I build up slowly, testing functions separately. You need to do the same with your code, not try to assemble a composite whole before testing.

[nowy20180820]

1. Is there a general procedure how to fix segmentation fault ?
How to detect which pointer operation caused this error
and how correct it

2. Textbook in my native language suggested me to use circular doubly linked list
but i found only linear linked list in Lafore's Algorithms in Java
I rewrote it with template to be able to use it also for other algorithms
Linked lists seems to be a good introduction to binary trees , structure of the single nodes
look the same on the first sight but pointers are used differently
Linked list will be useful later for graph represenation when adjacency matrices will waste memory
Access to the text file is sequential , linked list also has sequential access so relatively small file
can be easily loaded to file
Insertion and deletion on array need copying data and
insertion and deletion on linked list need pointer iteration
We can partially avoid copying data in array by reindexing but
still we will have to copy data while resizing and the concept of reindexing is closer to array based lists
Yes linked lists are slower than arrays in some cases but convex hull is not a good example of that

Before I go further I would like to know how to use pointers
if go further now segmentation fault also can happen
but data structures will be more complicated

Yes std::vector version works fine, thanks

3. It is strange but Jarvis works without errors on Lafore's version of linked list
and it may implies that error is in main.cpp
On the other hand Quickhull version i found works with Lastchance's linked list
and this leads our favourite mathematical logic to contradiction
Both Jarvis and Quickhull use the same functions from linked list

Maybe it is good idea to test the linked list
but before i test Lafore linked list is missing two useful functions
Natural merge sort and remove duplicateas
For convex hull comparator function in natural merge sort will be
function comparing angles , duplicates are colinear points

Could you show how to write these two functions on your linked list ?

[salem c]

> 1. Is there a general procedure how to fix segmentation fault ?
No.

Here are just some of the things which can go wrong.
A lot of the time, you're also dealing with spatial and temporal issues as well.
- spatial, the problem shows up in one part of the code, but the root cause is somewhere else.
- temporal, the code 'works' (possibly for years) and then blows up, because...
-- some code got added
-- changing a compiler flag
-- new version of the compiler.
-- new version of a dependent library.
-- porting the code to another platform (this always flushes out a whole host of hidden issues).

Here is a simple example with multiple faults. The system is under no obligation to crash instantly at the moment of the error.

char *s = new char[5];
strcpy(s,"hello");  // oops #1, memory overrun.  The string needs 6 chars including the \0
// time passes
delete s;  // oops #2, incorrect delete
// time passes
cout << s; // oops #3, using a stale pointer 

Tools like 'valgrind' certainly help with spatial issues, as they can trap problems when they happen, as opposed to when they show up.

[nowy20180820]

I think i know why segmentation fault occurs
Lists are passed by value and default copy constructor copied pointers
Then default destructor deleted it and pointers pointed to invalid location
When i pass list by reference segmentation fault disappear

[dhayden]

It looks like the OP's code is a direct port of the Pascal program in the paper referenced in the 3rd post. It doesn't work because C++ doesn't initialize variables to 0 like Pascal does. In particular, an empty PointSet contains one SetElement whose next pointer is uninitialized.

There's also a bug in the Pascal. Lastchance's version pointed me at the bug since his doesn't have it:

PROCEDURE Split(p,q:Point; VAR S,R,L:PointSet);
...
BEGIN
    NewSet(R);
    NewSet(L);
    ...
END;

PROCEDURE PruneAndSplit(p,q,r:Point; VAR S,U,L: PointSet);
VAR internal : PointSet;
BEGIN
    Split(p,r,S,U,internal);
    Split(r,q,internal,L,internal);
    Eliminate(internal);
END;

Notice that the underlined line passes internal to parameters S and L in Split. But Split reinitializes L. That reinitializes S too. The fix is use a second dummy PointSet.

Finally, it appears to me that the Pascal program leaks all the nodes that aren't part of the convex hull.

Here is a version that uses C++ forward_lists to mimic what the Pascal program does. It might be slightly faster than lastchance's since it just twiddles with the list links rather than copying the points themselves.

#include <forward_list>
#include <iostream>

using std::forward_list;
using std::istream;
using std::ostream;
using std::cin;
using std::cout;

struct Point {
    double x,y;
};

typedef forward_list<Point> PointSet;

// Inputs the original set of data points from is.
// This reads a number N followed by N pairs of x,y numbers (space separated)
// and stores them in data.
// Example of input stream:
// 3
// 1 2
// 3.3 4.0
// 1.0 1.2
void InputSet(PointSet &data, istream &is) {
    unsigned N;

    data.clear();
    is >> N;
    while (N--) {
	Point p;
	is >> p.x >> p.y;
	data.push_front(p);
    }
    if (!is.good()) {
	std::cerr << "Can't read points\n";
    }
}

void OutputPoint(const Point &p, ostream &os) {
    os << p.x << ", " << p.y << '\n';
}

// Compute the distance between vectors uv and point p, scaled by the
// length of vector uv
double ScaledDistance(const Point &u,
		     const Point &v,
		     const Point &p)
{
    double result = (v.x-u.x) * (p.y-u.y) - (v.y-u.y) * (p.x-u.x);
    return result;
}

// Find sthe scaled signed distance bewteen vector uv and point p. Seems
// to be the same as ScaledDistance??
double Direction(const Point &u,
		 const Point &v,
		 const Point &p)
{
    return ScaledDistance(u,v,p);
}

// Finds the parallel proojection of point p onto vector uv, scaled by
// the length of vector uv
double Projection(const Point &u,
		  const Point &v,
		  const Point &p)
{
    double result = (v.x-u.x) * (p.x-u.x) + (v.y-u.y) * (p.y-u.y);
    return result;
}

// Select 2 primary verticies p and q from a (non-empty) set S
void Select(Point &p, Point &q, PointSet &S)
{
    p = q = S.front();
    PointSet::iterator iter(S.begin());
    while (++iter, iter != S.end()) {
	Point &pt(*iter);	// shorthand
	if (pt.y < q.y || (pt.y == q.y && pt.x < q.x)) {
	    q = pt;
	} else if (pt.y > p.y || (pt.y == p.y && pt.x > p.x)) {
	    p = pt;
	}
    }    
}


// Split S into sets R and L, to the right and left of baseline pq,
// respectively.
void Split(const Point &p, const Point &q,
	   PointSet &S,
	   PointSet &R,
	   PointSet &L)
{
    R.clear();
    L.clear();
    while (!S.empty()) {
	Point &pt(S.front());
	double dir = Direction(p,q,pt);
	if (dir > 0.0) {
	    R.splice_after(R.before_begin(), S, S.before_begin());
	} else if (dir < 0.0) {
	    L.splice_after(L.before_begin(), S, S.before_begin());
	} else {
	    S.pop_front();
	}
    }
}

// Selects the upper and lower outside sets (U and L) for baseline
// pq and farthese-point r
void PruneAndSplit(const Point &p,
		   const Point &q,
		   const Point &r,
		   PointSet &S,
		   PointSet &U,
		   PointSet &L)
{
    PointSet internal, dummy;
    Split(p,r,S,U,internal);
    Split(r,q,internal, L, dummy);
}

// Find a point in (non-empty) S farthest from baseline pq
// NOTE: what if the distances are all negative?
Point FarthestPoint(const Point &p,
		   const Point &q,
		   PointSet &S)
{
    double maxDist=0, dist;
    Point result;
    for (const Point &pt : S) {
	dist = ScaledDistance(p,q,pt);
	if (dist > maxDist ||
	    (dist == maxDist && Projection(p,q,pt) > Projection(p,q,result))) {
	    maxDist = dist;
	    result = pt;
	}
    }
    return result;
}


//
// Main algorithm
//

// Finds the convex hull of S given that p and q are primary vertices
// and S lies to the right of baseline pq
void QuickHull(const Point &p, const Point &q, PointSet &S)
{
    Point r;
    PointSet U, L;
    if (!S.empty()) {
	r = FarthestPoint(p,q,S);
	PruneAndSplit(p,q,r,S,U,L);
	QuickHull(p,r,U);
	OutputPoint(r, cout);
	QuickHull(r,q,L);
    }
}

int main()
{
    PointSet S,R,L;
    Point p,q;
    
    InputSet(S, cin);
    Select(p,q,S);
    Split(p,q,S,R,L);
    OutputPoint(p, cout);
    QuickHull(p,q,R);
    OutputPoint(q, cout);
    QuickHull(q,p,L);
}