W Karas wrote:
wade wrote:
The algorithm is based on the recursive reduction:
intersections = intersections with chord with min(end - start) +
remaining intersections
It doesn't matter if the chord with min(end - start) is the shortest
chord or not.
I missed that.
After more careful consideration, the only solution
I can see is fairly complex. It is based on using
an AVL-balanced binary search tree. In each node
of the AVL tree, a count is kept of the total number
of nodes in the subtree that the node is the root of.
I think it is the case that the
W Karas wrote:
After more careful consideration, the only solution
I can see is fairly complex. It is based on using
an AVL-balanced binary search tree.
I think you are being a bit more complex than you need to be. Also,
you have a minor error in the details.
Your basic idea is:
A chord
wade wrote:
W Karas wrote:
After more careful consideration, the only solution
I can see is fairly complex. It is based on using
an AVL-balanced binary search tree.
I think you are being a bit more complex than you need to be. Also,
you have a minor error in the details.
Your basic
wade wrote:
W Karas wrote:
After more careful consideration, the only solution
I can see is fairly complex. It is based on using
an AVL-balanced binary search tree.
I think you are being a bit more complex than you need to be. Also,
you have a minor error in the details.
Your basic
W Karas wrote:
wade wrote:
wade wrote:
pramod wrote:
Karas: Can you please explain your code?
I'll try.
Sorry, I was explaining Karthik's method which seems to be correct, not
Karas's code, which seems to be incorrect.
Karas's method is to sort the endpoints in order of
pramod wrote:
Karas: Can you please explain your code?
I'll try. If you walk around the circle, you'll hit chord endpoints.
The first time you hit an endpoint, we'll call the chord started.
The second time you hit an endpoint, we'll call the chord finished.
Lets define intersect as intersect
pramod wrote:
...
Karas: Can you please explain your code?
I sort the chord endpoints based the angle of the radius it terminates
from
some origin. For each chord, I call the endpoint that comes first in
the
ordering the starting endpoint, and the other one the ending
endpoint.
(I believe the
wade wrote:
pramod wrote:
Karas: Can you please explain your code?
I'll try.
Sorry, I was explaining Karthik's method which seems to be correct, not
Karas's code, which seems to be incorrect.
Karas's method is to sort the endpoints in order of increasing angle
and then run:
for (i = 0; i
wade wrote:
wade wrote:
pramod wrote:
Karas: Can you please explain your code?
I'll try.
Sorry, I was explaining Karthik's method which seems to be correct, not
Karas's code, which seems to be incorrect.
Karas's method is to sort the endpoints in order of increasing angle
and
@pramod
Arent all the 'n' chords part of the same circle ? If they are how can
they be parallel without intersecting. If they are not of the same
circle then its a different problem.
@Karthik
The complexity is not O(n). It is O(nlg(n)), since my first step is
sorting the chords. Also you are
Dhyanesh wrote:
1 ) Radially sort the all the points of each chord (start and end both ).
2 ) Start with the first start point. Have c=1, tot=0, done[1..n]=0
3 ) Till all points are done:
a ) If its a start point then
tot = tot + c
c = c + 1
set done for this
Dhyanesh wrote:
1 ) Radially sort the all the points of each chord (start and end both ).
2 ) Start with the first start point. Have c=1, tot=0, done[1..n]=0
3 ) Till all points are done:
a ) If its a start point then
tot = tot + c
c = c + 1
set done for this
Dhyanesh:
I am failing to see your point.
Imagine a circle with origin as the center. You can very well imagine
two chords parallel to x-axis. Say one is diameter and the other is
some chord little above the diameter. These two don't intersect. How
can two parallel chords in a circle intersect?
I don't think this will work.
Suppose we have two chords which are parallel and both on the one side
of the circle. i.e., say draw a diameter parallel to X and say the
chords are above this parallel to each other.
In that case, your answer will be 1 but they are not intersecting at
all. I think
Try this variation
In the previous algorithm if i am correct the complexity is O(n), that
itself shows that an important step is missing somewhere. well this is
my guess about the algorithm. check if it works. I do not think this
is exactly the standard Bentley-Ottmann
Algorithm
The precondition
16 matches
Mail list logo
