finding where does a line touches a polygon

[Rishavs]

Hi

i have a polygon made up of x1, y1, x2, y2, ... xn, yn vertices.

there is a line
y = mx + a

which goes through the polygon. How can i find the points where the line touches the polygon?

I was planning on using the physics module and the Shape:testSegment function.
But it looks like its been deprecated.

Am i supposed to use the raycast function insetad?
I tried to go through it but was unsable to understand it.

Can someone help me with a snippet or alternate implementation?

EDIT: currently, i am breaking the polygon into individual lines and then doing a slope intersection check for each side.

[Trebgarta]

May be helpful: http://www.realtimerendering.com/intersections.html

[marco.lizza]

For any pair of point defining a segment you can

1) deduce the line formula,
2) solve the simple linear system (which is, in fact, a closed-formula) to find the intersection point, then
3) test if the intersection point is between the point enclosing the segment.

You should iterate these steps for each segment. This, I guess, it's what you are currently doing.

As an optimization, you can implement a sweeping algorithm. How many polygons/segments you need to handle?

[ivan]

Rishavs, this is a classic problem in computational geometry.
First of all you need a good segment vs segment intersection test.
http://2dengine.com/doc/gs_intersection.html
To find the exact point of intersection you have to change the "segment_vs_segment" function:

Code: Select all

return t1*dx1 + x1, t1*dy1 + y1

Then you have to iterate all edges in the polygon and check each one.

Super-duper industrial strength algorithms partition the polygon vertices,
but for everyday purposes you should be fine with the link above.

[pgimeno]

[wiki]Shape:rayCast[/wiki] seems to do what you want, but the API is indeed confusing. However, there's an example in the wiki that is quite clarifying.

In Box2D, shapes are independent of bodies, and bodies usually hold the position and rotation within the world. Therefore if you want to intersect a line (ray) with a shape, you need to specify the shape's position and rotation, because there's no associated body. That's what tx, ty, tr are. If you have a body associated, you can obtain that info from the body.

maxFraction seems to be a scale factor of the second point with respect to the first. The example uses 1 and that seems fine; that apparently means that the ray casting will end exactly at x2, y2.

childIndex seems to apply only to [wiki]ChainShape[/wiki]'s.

As for the results, it returns a normal vector, which you can ignore if you don't need it, and the fraction between your two points. The intersection point can be calculated as: x1 + (x2 - x1)*fraction, y1 + (y2 - y1)*fraction.

[Rishavs]

Thanks everyone.
My current implementation does works but I was wondering if using the Shape object will be much faster.