user3002473 user3002473 - 1 year ago 46
Python Question

How can I test if a line is intersecting with an arbitrary amount of other, unknown lines in python?

I want to test if a point is inside a polygon, and to do that I am using the ray-casting algorithm, where I send a line from the point to the origin of the screen and test how many intersections it makes (if it makes an odd number of intersections then the point is inside a polygon, otherwise it's outside). The problem is in calculating whether or not the ray intersects. Is the only way of calculating intersections through knowing the start and end coordinates of every line segment onscreen and calculating intersections with those lines? Or is there another method (regardless of it's complexity)?

If this is the only way of finding intersections of lines, then what would be the fastest way of calculating intersections?

At times there may be around 500 lines onscreen, all of which would need to be checked for collisions. How taxing on one's system would an algorithm be to test collisions with all of those lines in real time?

Answer Source

You probably want to use the Shapely package. The manual documents a method called contains() (scroll down to section 'Binary predicates') which seems to fit your needs.

As for performance considerations see the manual sections: 'Performance' and 'Prepared geometries'.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download