Problem of type

Pages: 12
Hi,
I have a vector<Neighbourhood> neighbourhood such as neighbourhood[w] contains w's neighbours.
Actually, the neighbours are stored in a std::set and for each w, its neighbours are ordered by distance from w.
So, I've tried to implement Neighbourhood but it brings some problems...

Here is my try :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct Neighbourhood {
    Neighbourhood(Point, vector<PointDouble>*);
    Point mayor;
    vector<PointDouble> *W;

    struct my_less {
        operator()(Point, Point);
    };

    set<Point, my_less> points;
};

Neighbourhood::Neighbourhood(Point mayor, vector<PointDouble>* W) {
    this->mayor = mayor;
    this->W = W;
    (this->my_less)::operator()(Point p1, Point p2) {
        return distance(p1, mayor, W) < distance(p2, mayor, W);
    }
}


Knowing that :
1
2
3
4
5
6
7
typedef struct {
    double x;
    double y;
    double z;
} PointDouble;

typedef size_t Point;


and that W is a vector such as W[i] contains (x, y, z) where x, y and z are the coordinates of the point.

The reason why I put the point "mayor" is because I need a structure my_less which is different for every point w. So I need to define the structure my_less inside Neighbourhood, so the set can have the right type...

I have two questions :
- Is it possible to do all that in a more elegant way ? Is this way even correct ?
- Then, if I want to define an iterator of the set, how can I do ? I've tried set<Point, neighbours[w].my_less> odd = points.rbegin(); but it hasn't worked.

I hope you'll have the time to look at my problem.
Thanks,
pierrotdu18
Last edited on
Hmm, I've just realized that I'm trying to use a vector which elements haven't the same type...
Nevertheless, I really need to have this structure, can I find something in the STL which would be suitable ?
Hello, I've been racking my brains on this for a while and will pass it on to you not completely finished but hope it will be of some use:

I don't think you need any vector at all but a just a set with a custom comparator based on the distance from PointDouble::this. The trouble I'm having is how to pass PointDouble::this to the custom comparator. I found this link here that gave some hints but not the complete path:
http://stackoverflow.com/questions/12456153/how-to-sort-set-of-coordinates-in-ascending-order-by-distance-from-point-x1-y1

My steps, in short:
1. forward declare struct PointDouble
2. forward declard double distance (const PointDouble& lhs, const PointDouble& rhs) - distance b/w 2 points
3. define struct PointDouble with a member struct DistanceCompare that compares the distances of 2 PointDouble objects from a common point

In the code I've commented what works and what doesn't:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <set>

struct PointDouble;
double distance(const PointDouble& lhs, const PointDouble& rhs);
struct PointDouble
{
    double _x;
    double _y;
    double _z;
    struct DistanceCompare
    {
        PointDouble* _origin;
        DistanceCompare (PointDouble* origin) : _origin(origin){}
        bool operator ()(const PointDouble& lhs, const PointDouble& rhs)
        {
            return distance(*_origin, lhs) < distance (*_origin, rhs);
        }
    };
    PointDouble* origin = this;
   // PointDouble::DistanceCompare comp(origin);//error: origin is not a type
    std::set<PointDouble, DistanceCompare> mySet;//this works but need to make the comparator a function of origin
};

int main()
{
    PointDouble* ptr;
    PointDouble::DistanceCompare comp(ptr);//this ctor works unlike the one within struct PointDouble
}
double distance(const PointDouble& lhs, const PointDouble& rhs){}

Sorry I couldn't be of more help but, hopefully, we'll both learn something out of this
Your functor needs to hold some state. Something like this, maybe:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
struct PointDouble { double x, y, z; };
using Point = std::size_t;

struct Neighbourhood;

struct PointLess {
    const Neighbourhood& neighborhood;

    PointLess(const Neighbourhood& n) : neighborhood(n) {};

    bool operator()(Point a, Point b);
};

struct Neighbourhood {
    Neighbourhood(Point, std::vector<PointDouble>*);
    Point mayor;
    std::vector<PointDouble> *W;   // why a pointer rather than a reference?

    std::set<Point, PointLess> points;
};

bool PointLess::operator()(Point a, Point b) {
    return distance(a, neighborhood.mayor, neighborhood.W) < distance(b, neighborhood.mayor, neighborhood.W);
}

Neighbourhood::Neighbourhood(Point mayor, std::vector<PointDouble>* W) : mayor(mayor), W(W), points(PointLess(*this)) {
}
When I put your code and
1
2
3
4
5
vector<Neighbourhood> neighbours;
for (Point w = 0; w < n; ++w) {
    neighbours.push_back(Neighbourhood(w, W));
    neighbours[w].points.insert(0);
}


Then if for a w I put :
 
set<Point, neighbours[w].points::key_comp()>& points = neighbours[w].points;


Then I have the error
 
[...]/reconstruction.cpp|58|error: call to non-constexpr function 'std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::operator[](std::vector<_Tp, _Alloc>::size_type) [with _Tp = Neighbourhood; _Alloc = std::allocator<Neighbourhood>; std::vector<_Tp, _Alloc>::reference = Neighbourhood&; std::vector<_Tp, _Alloc>::size_type = unsigned int]'|


I don't understand what that means...
OK, here's a workable solution (I hope):

1. struct Point;
2. double distance();
3. struct PointDouble which has (a) static data member of type Point called _origin, (b) struct data member DistanceCompare that overloads () operator for 2 Point objects depending on their distance from _origin and (c) a std::multiset, neighborhood, with a custom comparator DistanceCompare. A set will not work because it will reject separate points that have same distance from _origin. PointDouble and Point have similar ctor's i.e. taking x, y and z
4. In main() declare a PointDouble object with same co-ordinates as it's _origin and insert Points into this object's neighborhood

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <memory>
#include <set>
#include <cmath>

struct Point
{
    double _x;
    double _y;
    double _z;

    Point (double x, double y, double z) : _x(x), _y(y), _z(z){};
};
std::ostream& operator << (std::ostream& os, const Point& p)
{
    os << "(" << p._x << ", " << p._y << ", " << p._z << ")";
}
double distance(const Point& lhs, const Point& rhs);
struct PointDouble
{
    static Point _origin;
    double _PD_x;
    double _PD_y;
    double _PD_z;

    PointDouble (double x, double y, double z) : _PD_x(x), _PD_y(y), _PD_z(z){}
    struct DistanceCompare
    {
        bool operator()(const Point& lhs, const Point& rhs)
        {
            return distance(lhs, PointDouble::_origin) < distance (rhs, PointDouble::_origin);
        }
    };
    std::multiset<Point, DistanceCompare> neighborhood;
};
Point origin(0,0,0);
Point PointDouble::_origin = origin;

int main()
{
    Point a(1, 2, 3), b(-1, 2, -3), c(-2, 3, 4), d(2, -3, -4), e(3, -4, 5), f(-3, 4, -5);
    PointDouble p(0,0,0);
    p.neighborhood.insert (a);
    p.neighborhood.insert (b);
    p.neighborhood.insert (c);
    p.neighborhood.insert (d);
    p.neighborhood.insert (e);
    p.neighborhood.insert (f);

    std::cout << "The neighborhood of: " << origin << "looks like this: \n";

    for (auto& elem : p.neighborhood)
    {
        std::cout << elem << '\n';
    }
}
double distance(const Point& lhs, const Point& rhs)
{
    return std::pow(lhs._x - rhs._x, 2) + std::pow(lhs._y - rhs._y, 2) + std::pow(lhs._z - rhs._z, 2);
}
Output
1
2
3
4
5
6
7
The neighborhood of: (0, 0, 0)looks like this:
(1, 2, 3)
(-1, 2, -3)
(-2, 3, 4)
(2, -3, -4)
(3, -4, 5)
(-3, 4, -5)

You can try and move PointDouble up as a member of Point to keep things tight
When I put your code and

It isn't clear who the "you" in that quote is, but assuming it's a response to my post, the syntax for
set<Point, neighbours[w].points::key_comp()>& points = neighbours[w].points;
is not correct.

Any of the following would be correct, although you should probably prefer the last:
std::set<Point, PointLess>& points = neighbours[w].points;

std::set<Point, decltype(neighbours[w].points)::key_compare>& points = neighbours[w].points;

auto& points = neighbours[w].points;

Last edited on
Thanks a lot gunnerfunner I'm going to adapt your code a bit so it can be compatible with my project.
Thanks to you as well cire, I'll use auto (I didn't know this syntax)
With template non-type or expression arguments you can move to choice of origin to the interface rather than keep it within the implementation. This gives the end user the ability to choose bespoke origins rather than a program defined one, which was (0,0,0) in the previous case. These arguments have to be passed as int (I have also seen mentions of passing as double& but found it difficult to implement). Here's an example with the same Points seen from different origins:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <memory>
#include <set>
#include <cmath>

struct Point
{
    double _x;
    double _y;
    double _z;

    Point (double x, double y, double z) : _x(x), _y(y), _z(z){};
};
std::ostream& operator << (std::ostream& os, const Point& p)
{
    os << "(" << p._x << ", " << p._y << ", " << p._z << ")";
}
double distance(const Point& lhs, const Point& rhs);

template <typename T, int a, int b, int c>
struct PointDouble
{
    double _PD_x;
    double _PD_y;
    double _PD_z;

    PointDouble (double x, double y, double z) : _PD_x(x), _PD_y(y), _PD_z(z){}
    template <typename T1, int a1, int b1, int c1>
    struct DistanceCompare
    {
        T _origin = T(a1, b1, c1);

        bool operator()(const Point& lhs, const Point& rhs)
        {
            return distance(lhs, _origin) < distance (rhs, _origin);
        }
    } ;

    std::multiset<Point, DistanceCompare<T, a, b, c>> neighborhood;
};

int main()
{
    Point a(.9, 33, 6), b(-1, 2, -3), c(-2, 3, 4), d(2, -3, -4), e(5, -4, -14), f(0.7, 0.2, 0.7);
    PointDouble<Point, 1, 33, 6> p(1,33,6);
    Point p1(1, 33, 6);

    p.neighborhood.insert (a);
    p.neighborhood.insert (b);
    p.neighborhood.insert (c);
    p.neighborhood.insert (d);
    p.neighborhood.insert (e);
    p.neighborhood.insert (f);

    std::cout << "The neighborhood of: " << p1 << " looks like this: \n";

    for (auto& elem : p.neighborhood)
    {
        std::cout << elem << '\n';
    }

    std::cout << "\n\n";

    PointDouble<Point, 0, 0, 0> s(0, 0, 0);
    Point s1(0, 0, 0);

    s.neighborhood.insert (a);
    s.neighborhood.insert (b);
    s.neighborhood.insert (c);
    s.neighborhood.insert (d);
    s.neighborhood.insert (e);
    s.neighborhood.insert (f);

    std::cout << "The neighborhood of: " << s1 << " looks like this: \n";

    for (auto& elem : s.neighborhood)
    {
        std::cout << elem << '\n';
    }
}
double distance(const Point& lhs, const Point& rhs)
{
    return std::pow(lhs._x - rhs._x, 2) + std::pow(lhs._y - rhs._y, 2) + std::pow(lhs._z - rhs._z, 2);
}

Output
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
The neighborhood of: (1, 33, 6) looks like this:
(0.9, 33, 6)
(-2, 3, 4)
(-1, 2, -3)
(0.7, 0.2, 0.7)
(2, -3, -4)
(5, -4, -14)


The neighborhood of: (0, 0, 0) looks like this:
(0.7, 0.2, 0.7)
(-1, 2, -3)
(-2, 3, 4)
(2, -3, -4)
(5, -4, -14)
(0.9, 33, 6)




Well, I think it's better if I put my entire code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <vector>
#include <set>
#include <limits>

struct Coordinates {
    double x;
    double y;
    double z;
};

struct Triangle;
struct Edge;
struct SimplicialComplex;

struct Point {
    static Coordinates coordinates;
    size_t index;

    struct Compare {
        bool operator()(const Point& lhs, const Point& rhs) {
            return distance(lhs.coordinates, Point::coordinates) < distance(rhs.coordinates, Point::coordinates);
        }
    };

    std::multiset<Point*, Compare> neighbourhood;

    SimplicialComplex simplices;
};

struct Edge {
    Point& p1;
    Point& p2;
};

struct Triangle {
    Point& p1;
    Point& p2;
    Point& p3;
};

struct Edge_less {
    bool operator()(Edge e1, Edge e2) {
        return e1.p1 < e2.p1 || (e1.p1 == e2.p1 && e1.p2 < e2.p2);
    }
};

struct Triangle_less {
    bool operator()(Triangle t1, Triangle t2) {
        return t1.p1 < t2.p1 || (t1.p1 == t2.p1 && t1.p2 < t2.p2) || (t1.p1 == t2.p1 && t1.p2 == t2.p2 && t1.p3 < t2.p3);
    }
};

struct SimplicialComplex {
    std::set<Edge, Edge_less> edges;
    std::set<Triangle, Triangle_less> triangles;
};


double distance(const Coordinates&, const Coordinates&);
double distance(const Point&, const Point&);
double distance(const Point, const std::vector<size_t>&);
Point farthest(const std::vector<PointDouble>&, const std::vector<Point>&);


Indeed a point needs :
- coordinates
- an index (the reason is not important)
- neighbours
- some simplicies to which it is attached (see structure SimplicialComplex)

Well, another problem I have is that my compiler doesn't like the fact that Point has a SimplicialComplex object (because it is not entierly defined at this point), and I cannot swap the order because it would be the same problem.
Also, I changed the type of the multiset (a Point carries lots of information so neighbours should have pointers to points rather than the points themselves).

PS: I hope you didn't realize I was French, anyway I'm sorry if my English is not perfect
Last edited on
1. Overload <, == for Point
2. For incomplete types such as SimplicalComplex, use (smart) pointers
3. farthest(...) arguments should be Point?
Following compiles but of course I can't say anything more than that until I see the full program:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <vector>
#include <set>
#include <limits>

using namespace std;
struct Coordinates;
struct Point;
double distance(const Coordinates&, const Coordinates&);
double distance(const Point&, const Point&);
double distance(const Point, const std::vector<size_t>&);
Point farthest(const std::vector<Point>&, const std::vector<Point>&);

struct Coordinates {
    double x;
    double y;
    double z;
};

struct Triangle;
struct Edge;
struct SimplicialComplex;

struct Point {
    static Coordinates coordinates;
    size_t index;

    struct Compare {
        bool operator()(const Point& lhs, const Point& rhs) {
            return distance(lhs.coordinates, Point::coordinates) < distance(rhs.coordinates, Point::coordinates);
        }
           };

        bool operator < (const Point& rhs){}
        bool operator == (const Point& rhs){}

    std::multiset<Point*, Compare> neighbourhood;

    SimplicialComplex* simplices;
};

struct Edge {
    Point& p1;
    Point& p2;
};

struct Triangle {
    Point& p1;
    Point& p2;
    Point& p3;
};

struct Edge_less {
    bool operator()(Edge e1, Edge e2) {
        return e1.p1 < e2.p1 || (e1.p1 == e2.p1 && e1.p2 < e2.p2);
    }
};

struct Triangle_less {
    bool operator()(Triangle t1, Triangle t2) {
        return t1.p1 < t2.p1 || (t1.p1 == t2.p1 && t1.p2 < t2.p2) || (t1.p1 == t2.p1 && t1.p2 == t2.p2 && t1.p3 < t2.p3);
    }
};

struct SimplicialComplex {
    std::set<Edge, Edge_less> edges;
    std::set<Triangle, Triangle_less> triangles;
};

int main()
{

}


joyeux Noël et bonne chance
Well, I've put all that in my project and I've corrected as many errors as possible, yet my code isn't compiling.
Maybe that's because I began to learn C++ two weeks ago :p
I send you a link if you want to have a look, otherwise I'll try to repair it in a few days because I spend my whole days on it and I have much other work to do !
https://github.com/pierrotdu18/TIPE/tree/master/Reconstruction/Algorithmes/3D

(the goal is to implement this algorithm http://geometrica.saclay.inria.fr/team/Steve.Oudot/papers/go-ruwc-07/go-ruwc-07.pdf )
Last edited on
Your Triangle and Edge ctor's look dubious. Variables i, j, k are pointer variables, so to say i < j, etc is just comparing memory addresses, which is not very meaningful in this context. Perhaps you need to, at least, de-reference the pointers first.

I could be wrong but it seems you're trying to determine which Point should go to which end of the Edge or which vertex of the Triangle depending on some criterion (perhaps distance from the 'origin'?) in which case you need to distinguish b/w the data-members of Edge (closest, nearest) and Triangle (closest, mid, farthest) and find a way of passing the 'origin'
Point to the ctor's of these types. You've already done this in the case of the multi-set comparator so that could serve as an example.

As you've chosen to use the static Coordinates coordinates approach, as explained in my later post, do be aware that the limitation of this method is that the value of the static variable is not determined within the user-interface. So if the header and/or implementation files are not available the end user has no means to changing it's value. That is where the template based approach that I sent later has an advantage.

The research paper is way over my head but if someone can read, and understand, it perhaps you'll get some additional inputs.
Indeed, the constructors weren't correct : now the points are de-referenced and the comparaison is between the attribute "index" which is only there to ensure the unicity of the representation (I could've used a set but knowing that the simplexes have a maximum of 3 three points (my algo is for dimension 3 but it can be generalized for any euclidian space and even for every metric space) then it would be killing a fly with a sledgehammer in my opinion).
But again if you think there is a better way to do this please tell me :)

There isn't any user interface or anything like that : the goal of the algorithm is, starting from a list of points in 3D which sampled over an underlying shape, reconstruct the shape (see the pictures in the research article for an example). So, the program should be used like this
reconstruct.exe points.xyz
thus there isn't any problem with the approach you proposed is it ?

Anyway thank you so much for your help.


EDIT

What is strange is that I have an error on that line :
1
2
3
for (Point* p : L) {
    ofile << p->coordinates.x << " " << p->coordinates.y << " " << p->coordinates.z << endl;
}

"Undefined reference to 'Point::coordinates'", while L is a vector<Point*>...
Last edited on
I could've used a set ...

The benefit of using a standard library container is that it sorts the Point objects readily via operator overload and so the code for the Triangle ctor becomes much smaller. Below is an outline for a generalized Point struct that has a size_t type member, _index:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

struct Point
{
    size_t _index;
    std::string _other_stuff = " " ;

    bool operator < (const Point& rhs)const
    {
        return _index < rhs._index;
    }
    Point(size_t index) : _index (index){}
};
std::ostream& operator << (std::ostream& os, const Point& rhs)
{
    os << rhs._index ;
    return os;
}
int main()
{
    Point p1(2), p2(3), p3(1);
    std::vector<Point> vec;
    vec.push_back(p1);
    vec.push_back(p2);
    vec.push_back(p3);
    std::sort(vec.begin(), vec.end());

    for (auto& elem : vec)
    {
        std::cout << elem << " ";
    }
    std::cout << '\n';
}

Output
1
2
3
4
1 2 3//now you can assign the sorted vector to the Triangle's data-members; 

Process returned 0 (0x0)   execution time : 0.119 s
Press any key to continue.

There isn't any user interface or anything like that ...

If you own the entire program I suppose you could get away with it, particulary as you seem to have spent a lot of time on developing this approach but do be aware of its limitations for your own understanding

I've just realized that std::multiset wasn't that adaped for my situation : a std::vector would be better as I have somewhere to consider only the x first points of the neighbourhood, and to test if a neighbour is among those x first neighbours... For now I used Compare(*it, *next(foo.begin(), x)) but it would be much easier with a vector that I'd have to sort as you've proposed.

And indeed I have written all the code and I'm alone for that project, it is as part of my course in "classe préparatoire" as we call it in French.
I do understand the semantical difference between the two approaches, yet as I've told you, I began to learn C++ about two weeks ago with the only aim of having a fast and optimized programmed version of the algorithm I'm studying besides, so for the moment I'm trying to have a correct code rather than to understand every sweet syntaxes of the language, something that I will love spending time on next year if I pass my competitive exams :)

Do you have any idea why I get the error I mentioned ?

PS: writing all that makes me work on my english : double benefit
Last edited on
Do you have any idea why I get the error I mentioned ?


1
2
3
4
5
6
struct Point {
    static Coordinates coordinates;
    size_t index;

    struct Compare {
        bool operator()(const Point& lhs, const Point& rhs) {


coordinates is declared in the class definition, but it is never defined.

In a non-header source file somewhere you must include the definition:
Coordinates Point::coordinates { 0.0, 0.0, 0.0 };
Last edited on
Wait, that means that there's only one "coordinates" for all points ?
Each point must have its own coordinates right...

For the moment I've got something like this
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<Point> W;

size_t i = 0;
while (!ifile.eof()) {
    Point w;
    W.push_back(w);
    double x, y, z;
    ifile >> x;
    ifile >> y;
    ifile >> z;
    W[i].coordinates.x = x;
    W[i].coordinates.y = y;
    W[i].coordinates.z = z;
    W[i].index = i;
    ++i;
}

then can I access w's coordinates with w.coordinates ?
Wait, that means that there's only one "coordinates" for all points ?

Yes.

Each point must have its own coordinates right...

If the coordinates member of a Point is static, no.

If that member is static than this:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<Point> W;

size_t i = 0;
while (!ifile.eof()) {   // Looping on eof is wrong, here, btw.
    Point w;
    W.push_back(w);
    double x, y, z;
    ifile >> x;
    ifile >> y;
    ifile >> z;
    W[i].coordinates.x = x;
    W[i].coordinates.y = y;
    W[i].coordinates.z = z;
    W[i].index = i;
    ++i;
}

is functionally equivalent to:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<Point> W;

size_t i = 0;
while (!ifile.eof()) {
    Point w;
    W.push_back(w);
    double x, y, z;
    ifile >> x;
    ifile >> y;
    ifile >> z;
    Point::coordinates.x = x;
    Point::coordinates.y = y;
    Point::coordinates.z = z;
    W[i].index = i;
    ++i;
}
Why is looping on eof wrong?

Ok, I might have not understand at all what the difference between the two approaches is. Now I think I get it.
So, if I want different coordinates for each point I may use the template version gunnerfunner has proposed? Is there any shorter way of doing it?
Last edited on
Pages: 12