Thursday, March 8, 2012

polygon self intersecting - two line segements intersecting...

This week I was working on how to find the polygon is self intersecting or not.   I have gone through various logics, algorithms etc.,  but nothing worked fine..

Finally, I found this site, this is simple way to find whether two line segments are intersecting..

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=geometry2

Based on this logic, i developed few lines of code to find two segments intersection..

for example:  points are  (0,0) (5,5), (0,5)(-3, 6)(-3, 3)
the above sample will create a polygon with five sides.   So here we should be careful, how to iterate the lines with other lines (not the immediate next one)...  and also, it should not redo the same set of sides....

(0,0) - (5,5) - side1
(5,5) - (0,5) - side2
(0,5) -(-3,6) - side3
(-3,6) - (-3,3) - side4
(-3,3)-(0,0) - side5

so, side1 should be compared with side3, side4  (but not with side2, side5, since those are closer)

then side2 should be compared with side4, side 5 (but not with side3, side1)
....






No comments:

Post a Comment

Andrew Ng machine learning course

Hi, I was failing in the week 2 quiz - Machine learning course in Coursera.org, especially in one of the question which has multiple opti...