Your program fails on this case:david wrote:Anyway here's my code, in case someone wants to test it.
Code: Select all
input:
1
0 0 5 0 2 4
4 0 6 0 -4 16
output:
pair 1: yes
Moderator: Board moderators
Your program fails on this case:david wrote:Anyway here's my code, in case someone wants to test it.
Code: Select all
input:
1
0 0 5 0 2 4
4 0 6 0 -4 16
output:
pair 1: yes
hvalakalinov wrote:Your program fails on this case:david wrote:Anyway here's my code, in case someone wants to test it.Code: Select all
input: 1 0 0 5 0 2 4 4 0 6 0 -4 16 output: pair 1: yes
I thought so because in the sample input we have:Darko wrote:Those two have all their points in common - I am not sure why you thought that we were looking for points with integer coordinates only.
No, there isn't any common point..cpphamza wrote:I thought so because in the sample input we have:Darko wrote:Those two have all their points in common - I am not sure why you thought that we were looking for points with integer coordinates only.
0 0 2 0 0 2
1 1 3 3 2 3
and answer is no although they've a common area (infinite non integer points)! can you please explain that?
I'm interested in implementing a convex polygon intersection algorithm, can you post your algorithm? (code, resources, links ...)I have code to find intersection of 2 convex polygons, so I just used that, then compute the area of the resulting polygons.
The O(n) algorithm to find intersection of 2 convex polygons is related to the idea of rotating calipers.cpphamza wrote:I'm interested in implementing a convex polygon intersection algorithm, can you post your algorithm? (code, resources, links ...)I have code to find intersection of 2 convex polygons, so I just used that, then compute the area of the resulting polygons.
Also can anyone expalin other approaches to solve this problem?
Thanks.
Rotating?sclo wrote:The O(n) algorithm to find intersection of 2 convex polygons is related to the idea of rotating calipers.
G.T. Toussaint. A simple linear algorithm for intersecting convex polygons. The Visual Computer. 1: 118-123. 1985.
Could you explain the process? step by step.. I cant figure out what I have to search in each strip. If you have a link explaing this would be helpful.Just sweeping left to right is enough. Imagine a vertical line through each vertex. You get O(N) strips, and in each strip at most 4 edges => each strip can be processed in O(1) time. That's all.