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)
- 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 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)