#### Archived

This topic is now archived and is closed to further replies.

# polygon line intersection test

This topic is 5717 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Maybe the question has been asked a dozen time, sorry for that I''m writing a pinball game, and i''ll describe objects in polygons (array with coords). I can detect if a point lies in a polygon, but when the ball has a high speed, it can jump through walls. So i must not check if a point lies in a polygon, but if a line (oldpostitionvector ball, newpositionvector ball) crosses a polygonline. I need: - the exact point of intersection - the two points (which forms a polygon line) the intersectionpoint lies between, so then i can calculate with the dot product the angle. (function has been made already). Can anyone explain it to me as simple as possible?? Thanks in advance, Kind regards, Spikey

##### Share on other sites
There is literally _loads_ of info on "line-triangle-interstion-tests". Try either GameDev''s search or go to Google.

##### Share on other sites
Did i said "explain as simple plz??"

Oh yes, I did

I don''t get all the "experienced" tutorials. So i''d like to have a good explaination otherwise i didn''t had to post here

##### Share on other sites
You have to try the intersection between the line segment of the ball, and every line segment of the polygon, one by one.

It''s quite easy, really.
y = ax + b ->First line
y = cx + d ->Second line

ax + b = cx + d
x = (d - b) / (a - c)

Now you check if x is between x0 and x1 for the first line segment, then the second line segment.

HTH,

Cédric

##### Share on other sites
If you use bounding spheres for the objects in your game, you can use a ray to sphere test which I have. It also returns a point of intersection.

  //// Ray to sphere collision test//	http://www.cs.unc.edu/~rademach/xroads-RT/RTarticle.html//const bool Util::RaySphereTest( D3DXVECTOR3* vPofI, const D3DXVECTOR3* vSpherePos, const float fRadius, 								const D3DXVECTOR3* vRayStartPos, const D3DXVECTOR3* vRayEndPos ){	// Ray''s direction	D3DXVECTOR3 vRayNormal = *vRayEndPos - *vRayStartPos;	Normalize( &vRayNormal, &vRayNormal );	// Get distance of a vector from ray origin to sphere''s center pos projected on the ray	D3DXVECTOR3 vRaySphere = *vSpherePos - *vRayStartPos;	float dist = DotProd( &vRaySphere, &vRayNormal );	// Find distance from point of intersection to vector perpendicular to ray and goes through sphere''s 	//	center (that''s the idea anyway)	float disc = (fRadius * fRadius) - (DotProd( &vRaySphere, &vRaySphere ) - (dist * dist) );	if( disc < 0.0f ) 		return false;	// No intersection	// They intersect	if( vPofI )	{		// Find point of intersection		float d = (float)sqrt( disc );		*vPofI = *vRayStartPos + ((dist - d) * vRayNormal);	}	return true;}

##### Share on other sites
how did u test whether a point is inside a polygon or not ? Did u use the method of angle calculation which checks whether the sum of the angles is 360 or not ? Well... this method applies pretty well for convave polygons but fails in non-cocave ones. Not to mention, angle-calculation method is also very slow.

I''m looking for somone who has tried the line-intersection method and got it to work successfully, specially with the corners of the polygon. Anyone ?

• 10
• 17
• 9
• 13
• 41