Optimal way of working out if a polygon overlaps, is contained by, is contained in, or totally separate from another polygon

Performance Tuning
#1

Hi

I am trying to come up with an algorithm to work out if a polygon is completely inside another polygon, overlapping a polygon or totally separate from the polygon.

My current plan is take all the points in the polygon’s in draw order (or sequential to the polygon) and to create an edge formed of the current point and the next point.

I then take one of the polygons and iterate through the edges and work out if each edge crosses an edge in the test polygon. (Using boundary testing and line segment intersection testing).

If there is an edge intersection then there is overlapping of sorts, if there is no edge intersection then the polygon is either inside the other, the other is inside it or they are totally separate.

For the last 3 cases take a random point from both and do a ray intersection test to see if the point is inside or outside (using even off intersection test) the other polygon. Even for both says they are totally separate, odd for one and not the other means the polygon with the odd number of crossings for the point test is inside the other.

Is this the best way of doing this or is there a better way?

#2

Hi,
I assume that you’re talking about 2D.
Yes that’s how I do it. It’s quite fast. Rendering will still be way slower than doing these line-to-line tests.
You can also do a AABB or circle radius closeness test before doing the above to speed things up.
Cheers,
Keith

#3

Here’s a method I used, originally made by Franklin Antonio, to test for line (x1,y1) to (x2,y2) intersection with a polygon that has ArrayList points.

public boolean intersectsLine(double x1, double y1, double x2, double y2){
//		// pretty much just does the following, but with some optimisations by
//		// caching some values normally recalculated in the KPoint.linesIntersect method:
//		KPoint pointIBefore = points.get(points.size()-1);
//		for (int i = 0; i < points.size(); i++){
//			KPoint pointI = points.get(i);
//			if (KPoint.linesIntersect(x1, y1, x2, y2, pointIBefore.x, pointIBefore.y, pointI.x, pointI.y)){
//				return true;
//			}
//			pointIBefore = pointI;
//		}
//		return false;

		// Sometimes this method fails if the 'lines'
		// start and end on the same point, so here we check for that.
		if (x1 == x2 && y1 == y2){
			return false;
		}
		double ax = x2-x1;
		double ay = y2-y1;
		KPoint pointIBefore = points.get(points.size()-1);
		for (int i = 0; i < points.size(); i++){
			KPoint pointI = points.get(i);
			double x3 = pointIBefore.x;
			double y3 = pointIBefore.y;
			double x4 = pointI.x;
			double y4 = pointI.y;

			double bx = x3-x4;
			double by = y3-y4;
			double cx = x1-x3;
			double cy = y1-y3;

			double alphaNumerator = by*cx - bx*cy;
			double commonDenominator = ay*bx - ax*by;
			if (commonDenominator > 0){
				if (alphaNumerator < 0 || alphaNumerator > commonDenominator){
					pointIBefore = pointI;
					continue;
				}
			}else if (commonDenominator < 0){
				if (alphaNumerator > 0 || alphaNumerator < commonDenominator){
					pointIBefore = pointI;
					continue;
				}
			}
			double betaNumerator = ax*cy - ay*cx;
			if (commonDenominator > 0){
				if (betaNumerator < 0 || betaNumerator > commonDenominator){
					pointIBefore = pointI;
					continue;
				}
			}else if (commonDenominator < 0){
				if (betaNumerator > 0 || betaNumerator < commonDenominator){
					pointIBefore = pointI;
					continue;
				}
			}
			if (commonDenominator == 0){
				// This code wasn't in Franklin Antonio's method. It was added by Keith Woodward.
				// The lines are parallel.
				// Check if they're collinear.
				double collinearityTestForP3 = x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2);	// see http://mathworld.wolfram.com/Collinear.html
				// If p3 is collinear with p1 and p2 then p4 will also be collinear, since p1-p2 is parallel with p3-p4
				if (collinearityTestForP3 == 0){
					// The lines are collinear. Now check if they overlap.
					if (x1 >= x3 && x1 <= x4 || x1 <= x3 && x1 >= x4 ||
							x2 >= x3 && x2 <= x4 || x2 <= x3 && x2 >= x4 ||
							x3 >= x1 && x3 <= x2 || x3 <= x1 && x3 >= x2){
						if (y1 >= y3 && y1 <= y4 || y1 <= y3 && y1 >= y4 ||
								y2 >= y3 && y2 <= y4 || y2 <= y3 && y2 >= y4 ||
								y3 >= y1 && y3 <= y2 || y3 <= y1 && y3 >= y2){
							return true;
						}
					}
				}
				pointIBefore = pointI;
				continue;
			}
			return true;
		}
		return false;
	}

This and other code is in the old StraightEdge project that I used to work on.
https://code.google.com/archive/p/straightedge/
By the way, you might be interested to check out JTS which has lots of these type of operations and more. The only ‘problem’ about it is that it focuses on precision rather than speed.


Cheers,
Keith
1 Like
#4

Thanks, I think I do something similar, I work out a couple of cross products and then check the values of those and do a dot product in the case the are colinear to differentiate the two possible cases see