Talk:Convex hull

I found some errors in the C code when I compare with c++ code : code C++

   // lower hull
   for (const auto& pt : p) {
       while (h.size() >= 2 && !ccw(h.at(h.size() - 2), h.at(h.size() - 1), pt)) {
           h.pop_back();
       }
       h.push_back(pt);
   }

code C :

  /* lower hull */
   for (i = 0; i < len; ++i) {
       while (hLen >= 2) {
           hptr = h;
           while (hptr->next->next != NULL) {
               hptr = hptr->next;
           }
           if (ccw(&hptr->data, &hptr->next->data, &p[i])) { <== mistake
               break;
           }

It should be

  /* lower hull */
   for (i = 0; i < len; ++i) {
       while (hLen >= 2) {
           hptr = h;
           while (hptr->next->next != NULL) {
               hptr = hptr->next;
           }
           if (ccw(&hptr->next->data, &hptr->data, &p[i])) {   <==== good code
               break;
           }

The same error is done in upper hull

Another error

C++ code

   // upper hull
   auto t = h.size() + 1;
   for (auto it = p.crbegin(); it != p.crend(); it = std::next(it)) {
       auto pt = *it;
       while (h.size() >= t && !ccw(h.at(h.size() - 2), h.at(h.size() - 1), pt)) {
           h.pop_back();
       }
       h.push_back(pt);
   }

C code

   /* upper hull */
                            <== t is fogotten
   for (i = len - 1; i >= 0; i--) {
       while (hLen >= 2) {
           hptr = h;
           while (hptr->next->next != NULL) {
               hptr = hptr->next;
           }
           if (ccw(&hptr->data, &hptr->next->data, &p[i])) {
               break;
           }

It should be

   int t = hLen + 1;
   for (i = len - 1; i >= 0; i--)	{
   while (hLen >= t) 
   	hptr = h;
       while (hptr->next->next != NULL){
           hptr = hptr->next;
       }
       if (ccw(&hptr->next->data, &hptr->data, &p[i]))	{
           break;
       }

Last error

   int comp(const void *lhs, const void *rhs) {
       Point lp = *((Point *)lhs);
       Point rp = *((Point *)rhs);
       if (lp.x < rp.x) return -1;
       if (rp.x < lp.x) return 1;
       return 0;
   }

It should be

   int comp(const void* lhs, const void* rhs) {
       Point lp = *((Point*)lhs);
       Point rp = *((Point*)rhs);
       if (lp.x < rp.x) return -1;
       if (rp.x < lp.x) return 1;
       return rp.y - lp.y ;
   }

You should test the code, and think about the results here. For example, "ccw" is a routine which determines whether the winding is clockwise or counterclockwise. But from which side? Anyways... since that's not a documented issue... ccw should work regardless of the winding direction -- as long as the winding direction is consistent. So... you have encountered a real issue here. But it's probably not a code correctness issue -- it's probably a lack of adequate documentation issue (which is a frequent problem for coders).

Similarly, on the second issue you brought up, just throwing code out -- without any documentation and without any test results -- does not adequately illustrate the issue.

That said, taking a close look at the implementation, like you have done here, is great. We all-too-often have had errors in code here on this site -- often for very understandable reasons. So double checking results is frequently a good thing. Thanks!

P.S. please sign your comments on the talk pages, using --~~~~. This helps readers comprehend talk pages. --Rdm (talk) 21:07, 22 December 2020 (UTC)

I'm sure of these errors because I tried this code for an exercice on Codingame (Encounter Surface) and I didn't get the good results.

I compare with C++ and Java codes, found the mistakes, correct then as I explain and now it works !

May be the code is correct for the data given but it's wrong !

Trap D (talk)

Hmm... color me surprised. Or maybe there was a mistake in how you applied the code (since you didn't manage to get your signature right, here, that sort of emphasizes that possibility). I might try it out myself one of these days... --Rdm (talk) 01:38, 23 December 2020 (UTC)

Ok just try with these points

   Point points[] = {
       {0,0}, {5,5}, {5,0}, {0,5}
   };

Trap D (talk)

That gives me the result

Convex Hull: [(0, 0), (5, 0), (5, 5), (0, 5)]

which is correct -- a square is its own convex hull. So I guess I do not understand what issue you are concerned about.

(Why do you not use --~~~~ to sign your comments? Having the date in your signature helps guide the eye and will still be useful, years later.) --Rdm (talk) 20:41, 23 December 2020 (UTC)

I get the problem : I tried this code on Kubuntu with Eclipse, it works !? But, on Windows 10 with Visual Studio C (or Code Blocks, or web site Codingame which uses gcc 9.2.1 mode C17) it doesn't. Anyway I keep asserting that the code is wrong : the function comp doesn't care of the coordinate y of the points and that is false !!! --Trap D (talk) 09:31, 24 December 2020 (UTC)

I just try with points {0,0},{5,0},{0,5},{5,5} on kubuntu and I get [(0, 0), (5, 0), (0, 5)] --Trap D (talk) 14:13, 24 December 2020 (UTC)

Hmm... I do not see how changing the winding order could cause these sorts of discrepancies. Which suggests to me that the problem is elsewhere and swapping the first two arguments to ccw merely conceals the problem without actually fixing it.

That said, I also do not know how to isolate a problem which I do not have. --Rdm (talk) 18:59, 24 December 2020 (UTC)

I had the same problem with my Phix translation of the C code, however I only needed to add the fogotten t.

I also added more tests and a simple plot for visual verification of the results. I will also point out that the Raku (and therefore also Sidef) output is wrong in that the (1,-9) of (-3, -9) (1, -9) (14, -9) is clearly colinear and therefore should not be part of the hull. --Pete Lomax (talk) 19:19, 24 December 2020 (UTC)

I don't know, if your question is "which of these given points are on the hull?" than then the Raku implementation would be correct. I note that the task is somewhat vague in that regard. At any rate, if it offends you so, change the line if ccw( |@h.tail(2), $point ) >= 0 { to if ccw( |@h.tail(2), $point ) > 0 { and intermediate colinear points will not be reported. It doesn't bother me enough to change it. --Thundergnat (talk) 22:33, 29 December 2020 (UTC)

Apparently that's not legal Raku (I put the one = back in and it's fine again, took that one char out and it broke again, a real ??!!??WTF??!! moment):

Ah, of course: it starts with ((-3, -9), (1, -9)) but the first thing it does is pop the (1,-9). --Pete Lomax (talk) 03:21, 30 December 2020 (UTC)

 Convex Hull (7 points): [(-3, -9) (19, -8) (17, 5) (12, 17) (5, 19) (-3, 15) (-9, -3)]
 Too few positionals passed; expected 3 arguments but got 2
   in sub ccw at ./main.raku line 7
   in sub graham-scan at ./main.raku line 39
   in block <unit> at ./main.raku line 57

 exit status 1

The diagram at 1:00 of the Youtube link is very clear on this matter, plus what he says at 1:22, it seems common sense to me that if the set is every pixel used to draw a 400x400 square outline, the convex hull is 4 points, not all 1,596. --Pete Lomax (talk) 03:03, 30 December 2020 (UTC)

Ah. Ok, that definitely is a bug, untrapped edge condition. I'll fix that. While I'm at it, I'll edit the example to ignore colinear points. I don't think my interpretation was completely bogus, but you've convinced me that it is less correct. (And it's changing one character, not a big deal.) --Thundergnat (talk) 14:54, 30 December 2020 (UTC)