Sign in to follow this  
OpenGL_Guru

Polygon/Line Intersection Problem

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 this post


Link to post
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 this post


Link to post
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[i]);
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[i]);

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 this post


Link to post
Share on other sites
Quote:
Original post by oliii
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.


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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this