Beta
Combine Overlapping Polygons
Loading description...
Algorithms
Geometry
.avif)
This comment has been reported as {{ abuseKindText }}.
Show
This comment has been hidden. You can view it now .
This comment can not be viewed.
- |
- Reply
- Edit
- View Solution
- Expand 1 Reply Expand {{ comments?.length }} replies
- Collapse
- Spoiler
- Remove
- Remove comment & replies
- Report
{{ fetchSolutionsError }}
-
-
Your rendered github-flavored markdown will appear here.
-
Label this discussion...
-
No Label
Keep the comment unlabeled if none of the below applies.
-
Issue
Use the issue label when reporting problems with the kata.
Be sure to explain the problem clearly and include the steps to reproduce. -
Suggestion
Use the suggestion label if you have feedback on how this kata can be improved.
-
Question
Use the question label if you have questions and/or need help solving the kata.
Don't forget to mention the language you're using, and mark as having spoiler if you include your solution.
-
No Label
- Cancel
Commenting is not allowed on this discussion
You cannot view this solution
There is no solution to show
Please sign in or sign up to leave a comment.
The current reference solution returns a clearly incorrect answer in the following test case:
Thanks, should be fixed now. I also added a fixed case similar to this to the tests.
In
Fixed Tests-Simple Case-Test 1, I got the following message:Could you explain why my answer is incorrect? 🤔
Ahh, that's on me. There was an error in comparing polygons that was corrected in the sample tests but not the main ones. Should be fixed now.
I wonder if using floats as inputs and outputs does not make things unnecessarily complicated, because now you have to add tolerance to all kinds of checks like equality of points, collinearity, etc., and document it. However, this kind of linear calculations can be done completely in rational numbers (i.e. fractions). If you made input points always placed on integer lattice, or possibly in locations with fractional coordinates, then all intersection points could be represented with fractions, and compared for strict equality. There would be no need for tolerance checks, there would be no potential ambiguities like should the points common for input and output be returned identical, or will they be also compared with tolerance, etc.
Yeah, my original idea was just to be fairly lenient with tolerance checks when testing solutions, but the deeper I got into this the more I realized there are going to be tolerance checks all over the place.
I'll take a stab at using rational numbers.
Thanks!
Alright, I gave this a go. Definitely got rid of a lot of the parts of the solution/checker I didn't like.
I didn't expect that it would impact the performance as much as it did, though. I had to cut down the random tests, and the reference solution takes 4~7 seconds now instead of ~1 before. I'll keep looking to see if I can improve it.
Let me know if you have other thoughts.
But the points need to be adjacent? Or does a random order of correct points pass the specs?
They do need to be in order, but can start at any vertex and go either clockwise or counterclockwise. I'll see if I can come up with better language for that in the description.
The description requires an assumption that the polygons are non self-intersecting (they're clearly non-convex). Otherwise there would be no way to tell which side is "inside".
That's what I had intended with
but I'll change it to "non self-intersecting" as that's clearer.
Modifying the input will cause test display to show the input polygon after it has been modified.
Thanks, should be fixed now.