Intersections

[GhostWolf]

Polygons are defined as a position (x, y) and a set of vertices (x, y), with each vertex being an offset of the position (AKA object space).

A square, located at (50, 25) with a radii (half-radius for rectangles) of 10 could be defined as following:

local real x = 50
local real y = 25
local integer size = 8
local real array data

// left top
set data[0] = -10 // x
set data[1] =  10 // y
// right top
set data[2] =  10
set data[3] =  10
// right bottom
set data[4] =  10
set data[5] = -10
// left bottom
set data[6] = -10
set data[7] = -10

And too the skeptics, having the code named "x" and "y" doesn't reflect on which plane this exists, you can input whatever you want (it's named like this because in any other sane environment Z is depth, not height).

library PolygonIntersecion

globals
	real array x_data
	real array y_data
	
	real array x_normals
	real array y_normals
	
	integer x_size
	integer y_size
	
	real x_segment_x
	real x_segment_y
	real y_segment_x
	real y_segment_y
endglobals

function ProjectX takes real axis_x, real axis_y returns nothing
	local integer i = 2
	
	local real d
	
	set x_segment_x = x_data[0] * axis_x + x_data[1] * axis_y
	set x_segment_y = x_segment_x
	
	loop
		exitwhen i == size
		
		set d = x_data[i] * axis_x + x_data[i+1] * axis_y
		
		if d < x_segment_x then
			set x_segment_x = d
		endif
		
		if d > x_segment_y then
			set x_segment_y = d
		endif
		
		set i = i + 2
	endloop
endfunction

function ProjectY takes real axis_x, real axis_y returns nothing
	local integer i = 2
	
	local real d
	
	set y_segment_x = y_data[0] * axis_x + y_data[1] * axis_y
	set y_segment_y = y_segment_x
	
	loop
		exitwhen i == size
		
		set d = y_data[i] * axis_x + y_data[i+1] * axis_y
		
		if d < y_segment_x then
			set y_segment_x = d
		endif
		
		if d > y_segment_y then
			set y_segment_y = d
		endif
		
		set i = i + 2
	endloop
endfunction

function InitializeX takes real array x, integer size returns nothing
	local integer i = 0
	
	local real edge_x
	local real edge_y
	
	local real d
	
	// if size % 2 != 0 then
	//     set size = size - 1
	// endif
	
	loop
		exitwhen i == size
		
		set x_data[i] = x[i]
		set x_data[i+1] = x[i+1]
		
		set edge_x = x[(i + 2 + 1) % size] - x[i];
		set edge_y = x[(i + 2 + 2) % size] - x[i + 1]
		
		set d = 1.0 / SquareRoot(edge_x * edge_x + edge_y * edge_y)
		
		set edge_x = edge_x * d
		set edge_y = edge_y * d
		
		set x_normals[i] = edge_x
		set x_normals[i+1] = edge_y
		
		set i = i + 2
	endloop
	
	set x_size = size
endfunction

function InitializeY takes real array y, integer size returns nothing
	local integer i = 0
	
	local real edge_x
	local real edge_y
	
	local real d
	
	// if size % 2 != 0 then
	//     set size = size - 1
	// endif
	
	loop
		exitwhen i == size
		
		set y_data[i] = y[i]
		set y_data[i+1] = y[i+1]
		
		set edge_x = y[(i + 2 + 1) % size] - y[i];
		set edge_y = y[(i + 2 + 2) % size] - y[i + 1]
		
		set d = 1.0 / SquareRoot(edge_x * edge_x + edge_y * edge_y)
		
		set edge_x = edge_x * d
		set edge_y = edge_y * d
		
		set y_normals[i] = edge_x
		set y_normals[i+1] = edge_y
		
		set i = i + 2
	endloop
	
	set y_size = size
endfunction

function ArePolysIntersectingGlobal takes real x_pos_x, real x_pos_y, real y_pos_x, real y_pos_y returns boolean
	local real offset_x = x_pos_x - y_pos_x
	local real offset_y = x_pos_y - y_pos_y
	
	local int i = 0
	
	local real shift
	
	local real x_length
	local real y_length
	
	local real x_center
	local real y_center
	
	local real overlap
	
	loop
		exitwhen i == x_size - 1
		
		call ProjectPolygonX(x_normals[i], x_normals[i+1])
		call ProjectPolygonY(x_normals[i], x_normals[i+1])
		
		set shift = x_normals[i] * offset_x + x_normals[i+1] * offset_y
		
		set x_segment_x = x_segment_x + shift
		set x_segment_y = x_segment_y + shift
		
		set x_length = (x_segment_y - x_segment_x) * 0.5
		set y_length = (y_segment_y - y_segment_x) * 0.5
		
		set x_center = x_segment_x + x_length
		set y_center = y_segment_x + y_length
		
		set overlap = (x_length + y_length) - RAbsBJ(x_center - y_center)
		
		if overlap <= 0.0 then
			return false
		endif
		
		set i = i + 2
	endloop
	
	set offset_x = y_pos_x - x_pos_x
	set offset_y = y_pos_y - x_pos_y
	
	set i = 0
	
	loop
		exitwhen i == y_size - 1
		
		call ProjectPolygonX(y_normals[i], y_normals[i+1])
		call ProjectPolygonY(y_normals[i], y_normals[i+1])
		
		set shift = y_normals[i] * offset_x + y_normals[i+1] * offset_y
		
		set y_segment_x = y_segment_x + shift
		set y_segment_y = y_segment_y + shift
		
		set x_length = (x_segment_y - x_segment_x) * 0.5
		set y_length = (y_segment_y - y_segment_x) * 0.5
		
		set x_center = x_segment_x + x_length
		set y_center = y_segment_x + y_length
		
		set overlap = (x_length + y_length) - RAbsBJ(x_center - y_center)
		
		if overlap <= 0.0 then
			return false
		endif
		
		set i = i + 2
	endloop
	
	return true
endfunction

function ArePolysIntersecting takes real x_pos_x, real x_pos_y, real array x, integer x_size, real y_pos_x, real y_pos_y, real array y, integer y_size returns boolean
	call InitializeX(x, x_size)
	call InitializeY(y, y_size)
	
	return ArePolysIntersectingGlobal(x_pos_x, x_pos_y, y_pos_x, y_pos_y)
endfunction

endlibrary

 

[D4RK_G4ND4LF]

I had big performance issues with local arrays once
maybe you should make them private globals

edit:
benchmarked it
it really is worth it to switch to a global array

also some functions would return true even if the objects don't intersect but are inside of each other (just change the function name

your rects are all perpendicular to the ground which might be a problem

and RectIntersectsCircle could be IsPointInRect(bounds+radius)

and Nestharus made a function for IsPointInRect for any angles

 

[GhostWolf]

Done.

Also optimized the RectIntersectsCircle a little by letting it do a simple Rect-Rect intersection when possible.

 

[Nestharus]

all your rectnagle stuff is buggy... the rectangles may be rotated, unless you are taking a minX, minY, etc, in which case your little function will only be usable in very rare circumstances >.>.

You should be taking the coordinates of the four corners of the rectangle. Check out IsPointInRectangle by me to see how I handled it for your rectangle intersections with circles/triangles/rectangles/ellipses/etc : ).

And this submission is kind of a collection of snippets (the same as a collection of systems or a collection of maps, which is frowned upon), plus some of them have already been done.

Also it'd be nice if you could have functions that retrieved the intersection of 2 shapes in terms of % (how much of the area of shape2 is overlapping shape1)

 

[GhostWolf]

AABBs.

edit:

By the way, it's really easy to make this to any shape, but it will be very ugly without some simple classes (a Vector majorly).

SAT is pretty good for intersections of convex shapes (would probably be too slow for wc3 with many vertices per shape though).

 

[Nestharus]

edit
I'm an idiot : P

 

[GhostWolf]

Look at the first word of my previous post.

Should I make a generic poly-poly intersection?

 

[Nestharus]

Oh I see : D.

It still won't work since you're missing rotation, but just take the coordinates of 4 corners instead to make it easier to understand and easier to use.

 

[GhostWolf]

You really don't want to read what I write :/

AABB as in Axis Aligned Bounding Box. As in a rectangle (since this is 2D) which is axis aligned, like the original Wc3 Rects (Regions).

 

[Nestharus]

The only thing I could figure AABB meant was side A and side B in a rectangle, lol.

Anyways, I don't think that's very useful considering that most of the time you'll be dealing with rotated rectangles :\... in an earlier post (edited now), I said that'd only happen in very rare circumstances.

Anyways, I think you need to split this up into the various snippets... a collection of snippets is the same as a collection of systems, and I've never seen multiple systems that do different things in one submission get approved before.

 

[GhostWolf]

Changed it to a very lame version of my C++ Poly-Poly intersection test.

Can't figure how to do it correctly without classes, hench the double functions.
And since arrays in JASS suck (no dynamic arrays), I also separated the whole process into "building the polygons" and "testing".
This way you can build them, and then move them and check without building again.

So, you can either call ArePolysIntersecting and have more freedom, or build the polygons alone and call ArePolysIntersectingGlobal instead for speed.

Of course, this is limited to only two polygons at the same time, which is very lame.

You guys have ideas how to make it more JASS'y?

Also, what is the modulo function in JASS?

looks better in C++ :(

vector<Vect> GenerateNormals(const vector<Vect>& x)
{
	vector<Vect> normals;
	int size = (int)x.size();
	
	for (int i = 0; i < size; i++)
	{
		Vect edge = x[(i + 1) % size] - x[i];
		normals.push_back(normalize((edge)));
	}
	
	return normals;
}

Vect ProjectPoly (const vector<Vect>& x, const Vect& axis)
{
	float min = dot(x[0], axis);
	float max = min;

	for (int i = 1; i < (int)x.size(); i++)
	{
		const float d = dot(x[i], axis);

		if (d < min)
			min = d;

		if (d > max)
			max = d;
	}

	return Vect(min, max);
}

bool IsPolyIntersect(const Vect& x_pos, const vector<Vect>& x, const Vect& y_pos, const vector<Vect>& y)
{
	vector<Vect> x_norms = GenerateNormals(x);
	vector<Vect> y_norms = GenerateNormals(y);
	Vect offset = x_pos - y_pos;
	
	for (int i = 0; i < (int)x_norms.size(); i++)
	{
		Vect x_segment = ProjectPoly(x, x_norms[i]);
		Vect y_segment = ProjectPoly(y, x_norms[i]);
	
		const float shift = dot(x_norms[i], offset);
		
		x_segment += Vect(shift, shift);
		
		const float x_length = (x_segment.m_y - x_segment.m_x) * 0.5f;
		const float y_length = (y_segment.m_y - y_segment.m_x) * 0.5f;
		
		const float x_center = x_segment.m_x + x_length;
		const float y_center = y_segment.m_x + y_length;

		const float overlap = (x_length + y_length) - fabs();

		if (0.0 >= overlap)
		{
			return false;
		}
	}
	
	offset = y_pos - x_pos;
	
	for (int i = 0; i < (int)y_norms.size(); i++)
	{
		Vect y_segment = ProjectPoly(y, y_norms[i]);
		Vect x_segment = ProjectPoly(x, y_norms[i]);
		
		const float shift = dot(y_norms[i], offset);
		
		y_segment += Vect(shift, shift);
		
		const float y_length = (y_segment.m_y - y_segment.m_x) * 0.5f;
		const float x_length = (x_segment.m_y - x_segment.m_x) * 0.5f;
		
		const float y_center = y_segment.m_x + y_length;
		const float x_center = x_segment.m_x + x_length;

		const float overlap = (y_length + x_length) - fabs(y_center - x_center);

		if (0.0 >= overlap)
		{
			return false;
		}
	}
	
	return true;
}

 

[Nestharus]

If you're working with polygons, you need a polygon struct with a linked list of vertexes at this point.

So, since I don't have time to look it over, I have 1 question. Did you set it up properly to work with rotations?

->Also, what is the modulo function in JASS?
remainders in division. 5/2 = 2r1, 5%2 (% is normal modulo sign) = 1 (the remainder). If you still don't understand, google it : ).

 

[YourNameHere]

        set edge_x = x[(i + 2 + 1) % size] - x[i];
        set edge_y = x[(i + 2 + 2) % size] - x[i + 1]

You know, this is JASS, we have to use a bad BJ to use Modulo

 

[GhostWolf]

If you're working with polygons, you need a polygon struct with a linked list of vertexes at this point.

Yes, but JASS has no classes (and vJass worked bad with arrays back at the time when I used it).

So, since I don't have time to look it over, I have 1 question. Did you set it up properly to work with rotations?

These are polygons, there is no sense of rotation - the vertices are wherever you want them to be.

->Also, what is the modulo function in JASS?
remainders in division. 5/2 = 2r1, 5%2 (% is normal modulo sign) = 1 (the remainder). If you still don't understand, google it : ).

No, no, how is it called in JASS?


On another note, I googled some stuff and randomly came upon a cute looking function to check intersections between a circle and an AABB, without comparing distances like I do (I wonder if it can be used to get the translation vector).
I'll see if I can find it here again.

edit: found it, converting to JASS

function RectCircleOverlap takes real x0, real y0, real w0, real h0, real cx, real cy, real r returns boolean
	local real testX = cx
	local real testY = cy

	if testX < x0 then
		set testX = x0
	endif
	
	if testX > x0 + w0 then
		set testX = x0 + w0
	endif
	
	if testY < y0 then
		set testY = y0
	endif
	
	if testY > y0 + h0 then
		set testY = y0 + h0
	endif
	
	return ((cx - testX) * (cx - testX) + (cy - testY) * (cy - testY)) < r * r
endfunction

Ah, ok, it simply checks for the distance against the 4 corners. Don't think you can get the vector from it, since you need to take also the half-points of the rectangle (the center of each edge) into consideration.
Still a pretty fast solution if you only need to check for intersections.

 

[Bribe]

This is currently not working, has syntax errors. local variable names in JASS should never have underscores, only camelCasing. None of this is private, and if you intend these functions to be publicly-accessible you have chosen extremely generic names (ProjectX could be a million things).

 

[Bribe]

Graveyarded.