Polygon/Line Intersection Problem

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

Recommended Posts

hi all i have a rather straightforward problem(i think) ahead of me and just wanted to get reactions on better or different solutions. ill start off with the image below:(warning, i am not the best paint drawer) [smile] image the blue box represents a general shape. lets say that this shape is behind some data. in this example lets say this shape represents 200 people. what i would like to find out is how many people are in the green box that intersects the blue box. my thought was to take the area of the blue box, take the area of the green box and then take that percentage of the blue box to get an accurate number but i am not sure if that would be the best way or if there would be a better way to get a better answer. the green box could be non uniform shapes too like convex or just basic irregular shapes. this problem gets more complicated but i wanted to start with just this first. thanks!

Share on other sites
if all your data is inside the blue box, then the portions of the green box outside the blue box wont matter, as they will be empty anyway.

Else, if these are convex polygons, you can do the basic polygon clipping algo, to find the intersecting area, and find what is inside that area.

Share on other sites
as a matter of fact, you can shortcut the problem easily, if both areas are convex polygons. You only need to consider sample points inside all of the half- planes defined by the edges of both polygons.

// cull points outside a point list forming a convex area. void Cull(list<Vector>& samples, const Vector* vertices, int count){	// detect if polygon is clockwise or anti-clockwise	float winding = (vertices[2] - vertices[1]).crossProduct(vertices[0] - vertices[1]);	float sign = (winding < 0.0f)? 1.0f ; -1.0f;	for(int i = 0, j = count-1; i < count; j = i, i ++)	{		// edge, and the normal of the edge		Vector edge = (vertices[j] - vertices);		Vector normal(-edge.y, edge.x);		// iterate through the list		list<Vector>::iterator it = samples.begin(); 		// remove points outside the polygon edges planes		while(it != samples.end())		{			// caluclate signed distance of point from edge plane			Vector delta = (*(it) - vertices);			float dist = delta.dotProduct(normal);			bool outside = (dist * sign > 0.0f);			// if outside, remove point, else check next point in the list			if (outside)				samples.remove(it); //?			else				it++;		}	}}void GetIntersection(list<Vector>& samples, const Polygon& A, const Polygon& B){	Cull(samples, A.vertices, A.numVertices);	Cull(samples, B.vertices, B.numVertices);}

Share on other sites
Quote:
 Original post by oliiiif all your data is inside the blue box, then the portions of the green box outside the blue box wont matter, as they will be empty anyway. Else, if these are convex polygons, you can do the basic polygon clipping algo, to find the intersecting area, and find what is inside that area.

hey oliii, sorry just now getting back to you. thanks for the code and response. ill get to work on this and test it out with what i have so far. thanks again

• What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 17
• 14
• 10
• 9
• 11
• Forum Statistics

• Total Topics
634096
• Total Posts
3015503
×