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 !
- Ok just try with these points
Point points[] = {
{0,0}, {5,5}, {5,0}, {0,5}
};
- 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)