Talk:Convex hull: Difference between revisions
Ok, that IS a bug.
(The author of this code should rectify it) |
Thundergnat (talk | contribs) (Ok, that IS a bug.) |
||
| (23 intermediate revisions by 4 users not shown) | |||
Line 66:
It should be
hptr = hptr->next;
}
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 <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 !
[[User:Trap D|Trap D]] ([[User talk: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... --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 01:38, 23 December 2020 (UTC)
: Ok just try with these points
Point points[] = {
{0,0}, {5,5}, {5,0}, {0,5}
};
[[User:Trap D|Trap D]] ([[User talk:Trap D|talk]])
:: That gives me the result
:: <pre>Convex Hull: [(0, 0), (5, 0), (5, 5), (0, 5)]</pre>
:: 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 <nowiki>--~~~~</nowiki> to sign your comments? Having the date in your signature helps guide the eye and will still be useful, years later.) --[[User:Rdm|Rdm]] ([[User talk: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''' !!! --[[User:Trap D|Trap D]] ([[User talk: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)] --[[User:Trap D|Trap D]] ([[User talk: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. --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 18:59, 24 December 2020 (UTC)
:::: I had the same problem with my Phix translation of the C code, however I <u>only</u> 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. --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|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 <code>if ccw( |@h.tail(2), $point ) >= 0 {</code> to <code>if ccw( |@h.tail(2), $point ) > 0 {</code> and intermediate colinear points will not be reported. It doesn't bother me enough to change it. --[[User:Thundergnat|Thundergnat]] ([[User talk: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). --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|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. --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|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.) --[[User:Thundergnat|Thundergnat]] ([[User talk:Thundergnat|talk]]) 14:54, 30 December 2020 (UTC)
| |||