-1

I am attempting to sort three points for a triangle in order to add it successfully into a physics engine. All of the triangles whose position is smaller than 0.0 on the x axis show up correctly. However, after that point the first element (v[0]) is always set to {0.0, 0.0} and the rest seem okay. Here is my main function that does the sorting and adding.

void Core::addPoly(float x1, float y1, 
                   float x2, float y2, 
                   float x3, float y3) {

    std::vector<PVector> v(3);
    v.push_back(PVector(x1, y1));
    v.push_back(PVector(x2, y2));
    v.push_back(PVector(x3, y3));

    PVector center((x1+x2+x3)/3, (y1+y2+y3)/3);

    std::sort(v.begin(), v.end(), [center](PVector b, PVector a) { 
        if (a.x >= 0 && b.x < 0)
            return true;
        if (a.x == 0 && b.x == 0)
            return a.y > b.y;

        // compute the cross product of vectors (center -> a) x (center -> b)
        float det = (a.x-center.x) * (b.y-center.y) - (b.x - center.x) * (a.y - center.y);
        if (det < 0)
            return true;
        if (det > 0)
            return false;

        // points a and b are on the same line from the center
        // check which point is closer to the center
        float d1 = (a.x-center.x) * (a.x-center.x) + (a.y-center.y) * (a.y-center.y);
        float d2 = (b.x-center.x) * (b.x-center.x) + (b.y-center.y) * (b.y-center.y);
        return d1 > d2;
    });

    emap->polys.push_back(Polygon(v[0], v[1], v[2]));
}

I am using the sorting function provided here. It originally had the first element of all triangles pointed to center (however I don't believe this is correct behaviour)- I switched a and b in the lambda declaration and now it only shows up after 0.0 on the x axis.

If we have 3 triangles passed in (Imagine | to be the 0.0 and ___ to be 0.0 on a plane)

^     |
    ^ |   ^
______|_____________

The 0'th vertice of the third triangle will actually make it like this:

^     |
    ^ |  ___/|
______|_/______________

(This is supposed to be a triangle)

However, 0.0 was never passed to addPoly.

Community
  • 1
  • 1
jett
  • 1,276
  • 2
  • 14
  • 34
  • goto [code_review](http://codereview.stackexchange.com); –  Jan 19 '13 at 04:26
  • @VladLazarenko Why? Is this not SO format? – jett Jan 19 '13 at 04:30
  • @billz I don't understand why after a certain point a la past 0.0 on x axis the first element `(PVector) v[0]`is set to 0.0 since that number isn't passed as a number to be sorted. – jett Jan 19 '13 at 04:38
  • Why is your vertex input not already guaranteed to be either CW or CCW? – Steven Lu Jan 19 '13 at 14:11
  • @StevenLu this is interfaced with boost python. I want to keep the python code as gotcha free as possible, and to minimize duplication of effort. – jett Jan 19 '13 at 14:35
  • 1
    just be aware it will be quite a bit slower with that sort in there – Steven Lu Jan 19 '13 at 16:19

1 Answers1

1

This line:

std::vector<PVector> v(3);

Causes your vector to get initialized with three <0.0,0.0> values. Changing it to 

std::vector<PVector> v;

should fix your issue.

The code seems to work like this:

struct PVector 
{ 
    float x; 
    float y; 
    PVector(float x, float y) : x(x),y(y){}
    PVector() : x(0.0f), y(0.0f) {}
};


static void addPoly(float x1, float y1, 
                   float x2, float y2, 
                   float x3, float y3) {

    std::vector<PVector> v;
    v.push_back(PVector(x1, y1));
    v.push_back(PVector(x2, y2));
    v.push_back(PVector(x3, y3));

    PVector center((x1+x2+x3)/3, (y1+y2+y3)/3);

    std::sort(v.begin(), v.end(), [center](PVector b, PVector a) -> bool { 
        if (a.x >= 0 && b.x < 0)
            return true;
        if (a.x == 0 && b.x == 0)
            return a.y > b.y;

        // compute the cross product of vectors (center -> a) x (center -> b)
        float det = (a.x-center.x) * (b.y-center.y) - (b.x - center.x) * (a.y - center.y);
        if (det < 0)
            return true;
        if (det > 0)
            return false;

        // points a and b are on the same line from the center
        // check which point is closer to the center
        float d1 = (a.x-center.x) * (a.x-center.x) + (a.y-center.y) * (a.y-center.y);
        float d2 = (b.x-center.x) * (b.x-center.x) + (b.y-center.y) * (b.y-center.y);
        return d1 > d2;
    });

    //emap->polys.push_back(Polygon(v[0], v[1], v[2]));
}
Tawnos
  • 1,877
  • 1
  • 17
  • 26
  • Oh wow.... I was trying to preallocate the vectors size by doing that. Well, I didn't know it actually added anything- just thought it would reserve the sizeof 3 vectors. Am I right in attempting to do this ^ And thanks for the answer, this was a dumb learning moment. It finally makes sense. (: – jett Jan 19 '13 at 04:59
  • Did that fix it for you? I am not exactly sure what this code is attempting :) – Tawnos Jan 19 '13 at 04:59
  • Yes it did. The reason for the semi convoluted is that this is a function referenced by boost python with values that cannot be predetermined (otherwise this issue would not arise to begin with). Thanks again, you have made my day. – jett Jan 19 '13 at 05:47