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; }