Member Avatar for nitin1

hey, i want to do a question in which i am given n line segments and i want to find the number of intersection of them. Can anyone tell me the most efficient way i can do it ? I have got some links on google and also from books but i am not getting it. I am not asking for code or something like that and neither it is my homework. So please help me if you can. thanks

  • 4 Contributors
  • 4 Replies
  • 89 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by rithish
Member Avatar for nitin1

thanks you ! but i have implemented for 2 lines. but i am not getting for n line segments. thanks

Member Avatar for np complete

Suppose I have 1 line, its doesn't has any intersection so p(1) = 0
Now introducing another line, it cuts p(1) at atmost 1 point so p(2) = 1
Again introduce another line, it will intersect above 2 lines in atmost 2 points, but we already have one intersection point so p(3) = 3

Thus we have a recurrsion

p(x) = p(x - 1) + x - 1

Its a mathematical treatment. Hope it works.

commented: great +0
Member Avatar for rithish

can i know how ur implementing this in c ???r u using graphics.h to draw a line???

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.