0

i'm trying to implement a brute force approach to the convex hull but i'm having issues. I have the following:

void convexHull(point *array)
{
    double a,b,c,checkVal,found;
    for (int i = 0; i < 8; i++)
    {
        for (int j = i+1; j < 8; j++)
        {
            found = 0;
            a = array[j].y - array[i].y;
            b = array[j].x - array[i].x;
            c = (array[i].x * array[j].y) - (array[i].y * array[j].x);

            for (int k = 0; k < 8;k++)
            {
                checkVal = (a * array[k].x) + (b * array[k].y) - c;


                if (checkVal == 0)
                {
                    found = 1;
                    break;
                }

           }

           if (found == 1)
           {
                printf("%lf %lf\n",nums[i].x,nums[j].y);
           }
        }
    }
}

I have 8 points which i'm reading in which is why the indexes end at 8. I have been trying to find examples online but can't find much to help me. Once I calculate checkVal I am pretty sure I have to check if it equals 0 or not and break the loop, and print the points at num[i] and num[j] but I can't seem to get it working. How do I check the condition to print the set of points?

FreeStyle4
  • 272
  • 6
  • 17
  • So where is the check you are talking about? – Eugene Sh. Feb 10 '17 at 23:16
  • Since you wrote you already have tried something, can you please show THAT? – koalo Feb 10 '17 at 23:16
  • Sorry, ill edit my check part in. I didn't include it because it was wrong – FreeStyle4 Feb 10 '17 at 23:18
  • 1
    Possible duplicate of [Is floating point math broken?](http://stackoverflow.com/questions/588004/is-floating-point-math-broken) – Eugene Sh. Feb 10 '17 at 23:23
  • It is easier to find errors in existing code than to speculate over non-existing code ;-) – koalo Feb 10 '17 at 23:23
  • Assuming the array defines a *closed* hull you must also check that the array wraps round as continuously convex too, which will involve the modulus of array indices. At each node, you check the linearity of 3 consecutive vertices, that is, two consecutive edges. – Weather Vane Feb 10 '17 at 23:28
  • ... so you only need *one* loop which examines vertices `i` and `(i + 1) % 8` and `(i + 2) % 8` to determine whether the hull is convex. – Weather Vane Feb 10 '17 at 23:35

0 Answers0