
March 27th, 2017, 09:33 AM
#1
How to write a Comparator when the order of elements does not matter
Code:
bool Edge::operator<(const Edge& e) const
{
return std::tie(this>v0, this>v1) < std::tie(e.v0, e.v1);
}
also when this>v0 == e.v1 && this>v1 == e.v0
How do I rewrite this comparator?
Thanks
Jack

March 27th, 2017, 10:48 AM
#2
Re: How to write a Comparator when the order of elements does not matter
Well I don't quite understand what you mean by "the order doesn't matter". Maybe you mean that both elements of this should be smaller than both elements of e?
In that case you can do this,
Code:
return std::max(this>v0, this>v1) < std::min(e.v0, e.v1);

March 27th, 2017, 05:26 PM
#3
Re: How to write a Comparator when the order of elements does not matter
Hello,
I actually meant that
when I add the elements
in case 1: v0==v1 and v1==v0
and case 2: v0==v0 and v1==v1
, the items are deemed to be the same, and they won't add to the container as two separate items....
Thanks
Jack

March 28th, 2017, 12:16 AM
#4
Re: How to write a Comparator when the order of elements does not matter
Originally Posted by luckiejacky
in case 1: v0==v1 and v1==v0
and case 2: v0==v0 and v1==v1
, the items are deemed to be the same
That can easily be translated into code. This and e are equal when:
Code:
return ((this>v0==e.v1) && (this>v1==e.v0))  ((this>v0==e.v0) && ((this>v1==e.v1));
An example. Say this holds (1,2) in any order and e also holds (1,2) in any order and they are to be considered equal regardless of order. Then you have these four cases of equality,
1: (1,2) (1,2)
2: (1,2) (2,1)
3: (2,1) (1,2)
4: (2,1) (2,1)
The equality in cases 1 and 4 can be detected with a "straight" componentwise comparison and cases 2 and 3 with a "crosswise" comparison. This is what the code snippet I supplied does.
Note that you can reduce the four cases to 1 by keeping the components of Edge sorted. Ensuring that v0 <= v1 already in the Edge constructor is likely to save you lots of trouble later on.
Last edited by wolle; March 28th, 2017 at 04:42 AM.

March 28th, 2017, 09:15 PM
#5
Re: How to write a Comparator when the order of elements does not matter
Thanks for helping....
I just received a crash with this code.... (Comparator changed)
And sometimes, when the 3 edges are different in the first place, I just got one of them actually added into the container after all.
Code:
std::vector<Face>& faces = GetFaces();
const std::vector<D3DXVECTOR3>& verts = GetVertices();
std::set<Edge> newEdges;
for (int i = 0; i < faces.size(); i++)
{
Edge newEdge0, newEdge1, newEdge2;
newEdge0.v0 = faces[i].v0;
newEdge0.v1 = faces[i].v1;
newEdge1.v0 = faces[i].v1;
newEdge1.v1 = faces[i].v2;
newEdge2.v0 = faces[i].v2;
newEdge2.v1 = faces[i].v0;
D3DXVECTOR3 v0pos = verts[faces[i].v0];
D3DXVECTOR3 v1pos = verts[faces[i].v1];
D3DXVECTOR3 v2pos = verts[faces[i].v2];
newEdge0.v0_pos = v0pos;
newEdge0.v1_pos = v1pos;
newEdge0.faceId = faces[i].id;
newEdge1.v0_pos = v1pos;
newEdge1.v1_pos = v2pos;
newEdge1.faceId = faces[i].id;
newEdge2.v0_pos = v2pos;
newEdge2.v1_pos = v0pos;
newEdge2.faceId = faces[i].id;
newEdges.insert(newEdge0);
newEdges.insert(newEdge1);
newEdges.insert(newEdge2);
faces[i].m_edges.push_back(newEdge0);
faces[i].m_edges.push_back(newEdge1);
faces[i].m_edges.push_back(newEdge2);
}
Could you please shed some lights on this?
Thanks
Jack
Last edited by luckiejacky; March 28th, 2017 at 09:21 PM.

March 29th, 2017, 02:10 AM
#6
Re: How to write a Comparator when the order of elements does not matter
Originally Posted by luckiejacky
Could you please shed some lights on this?
You want to store edges in an std::set and for that you need to define a < (less) relation between the edges. The set will keep the edges sorted according to the < relation but it will also use it to establish equality to prevent edges from being inserted more than once. Say we have two edges e1 and e2. Equality is established like so: e1==e2 when !(e1<e2) && !(e2<e1).
The edges e1 and e2 are line segments, each with endpoints v0 and v1. First we assume v0 <= v1. We look at the left endpoints and state that e1<e2 when e1.v0<e2.v0. But if we stop here, due to the way equality is established, we can get a false equality when e1.v0==e2.v0. To resolve this we also involve the right endpoints and state that in the case that e1.v0==e2.v0 then e1<e2 when e1.v1<e2.v1.
This essentially means we have used both the position and length of line segments to establish the < relation. Position as primary criterion and length as secondary. In code,
Code:
boolean less(Edge e1, Edge e2) {
return (e1.v0<e2.v0)  ((e1.v0==e2.v0) && (e1.v1<e2.v1));
}
As I've said, it pays off to to keep v0 and v1 presorted according to v0 <= v1 but if you for some reason cannot have that there is no way around a sort (in one way or another, explicit or implicit). This is one way,
Code:
boolean less(Edge s1, Edge s2) {
Edge e1,e2;
e1.v0 = std::min(s1.v0, s1.v1);
e1.v1 = std::max(s1.v0, s1.v1);
e2.v0 = std::min(s2.v0, s2.v1);
e2.v1 = std::max(s2.v0, s2.v1);
return (e1.v0<e2.v0)  ((e1.v0==e2.v0) && (e1.v1<e2.v1));
}
It's not tested but it should work, at least in principle
Last edited by wolle; March 29th, 2017 at 07:11 AM.

March 29th, 2017, 05:15 AM
#7
Re: How to write a Comparator when the order of elements does not matter
Good. It works. Thanks, I've learnt something.... Really thanks
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
This a Codeguru.com survey!
