Talk:Convex hull: Difference between revisions
Content added Content deleted
mNo edit summary |
No edit summary |
||
Line 66: | Line 66: | ||
It should be |
It should be |
||
int t = hLen + 1; |
int t = hLen + 1; |
||
for (i = len - 1; i >= 0; i--) { |
for (i = len - 1; i >= 0; i--) { |
||
Line 76: | Line 78: | ||
break; |
break; |
||
} |
} |
||
: 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). |
: 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). |
||
Line 81: | Line 84: | ||
: 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! |
: 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 <nowiki>--~~~~</nowiki>. This helps readers comprehend talk pages. --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 21:07, 22 December 2020 (UTC) |
: P.S. please sign your comments on the talk pages, using <nowiki>--~~~~</nowiki>. This helps readers comprehend talk pages. --[[User:Rdm|Rdm]] ([[User talk: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 |
Revision as of 23:38, 22 December 2020
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;
}
- 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