Forum

> > CS2D > Scripts > Is a point (coordinate) inside or outside shape
Forums overviewCS2D overview Scripts overviewLog in to reply

English Is a point (coordinate) inside or outside shape

4 replies
To the start Previous 1 Next To the start

old Is a point (coordinate) inside or outside shape

Happy eyes
User Off Offline

Quote
Hello,

I need a function that would return true if point is inside and false if point is outside the special area. However area isn't square, nor rectangle but quadrangle. I will show you example.
IMG:https://img36.imageshack.us/img36/2434/93599334.png


All we know is the coordinates of the 4 corners and the point coordinates, as you can see clearly that in our case A is INSIDE the quadrangle BCDE, so function would return true

Parameters should be 5 tables with 1 point coordinate and 4 corners coordinates ({4,4},{1,4.5},{4,2.7},{5,4.2},{3.2,6}) (A,B,C,D,E)

old Re: Is a point (coordinate) inside or outside shape

Snake_Eater
User Off Offline

Quote
hmm if you want to do it for cs2d u only need 2 corners like this:

1
2
3
4
5
6
7
function areapoint(Pointx,Pointy,Bx,By,Dx,Dy) --the 2 corners of ur example
if (Pointx >= Bx) and (Pointy >= By) and (Pointx <= Dx) and (Pointy <= Dy) then
 return true
else
 return false
end
end

old Re: Is a point (coordinate) inside or outside shape

Flacko
User Off Offline

Quote
First, you will need a line-line collision algorithm.

The simplest approach is to take 4 points, convert them to two lines and resolve them as lineal functions. Then check if the x value we got is in range for both lines. Like this:
Quote
{-10,-5}->{10,5} = f(x) = 1*x+5
{-10,-20}->{10,20} = g(x) = 2*x

f(x) = g(x)
x+5 = 2x
x = 5
The collision is occuring at x=5. Since this value is within both lines, we assume it's OK.

Therefore, lineal functions written as a*x+b can be solved as:
(b1-b2) / (a2-a1)


You might think that there will be a problem when there's a vertical line, since it's slope would be infinite. If you rotate all the points 90° the problem should be solved and the slopes can be recalculated.
Theres another special case that is when the lines are forming a cross, but you can deal with it easily.

Here's my approach:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
local function rotatepoint(t)
	return {t[2], -t[1]+0}
end

function lineline(p1,p2,p3,p4)
	local s = { (p2[2]-p1[2])/(p2[1]-p1[1]), (p4[2]-p3[2])/(p4[1]-p3[1]) }
	for i=1,2 do
		if math.abs(s[i]) == math.huge then
			if s[3-i] == 0 then --cross
				return (p1[1] > p3[1]) == (p2[1] < p4[1]) and (p1[2] > p3[2]) == (p2[2] < p4[2])
			else
				return lineline(rotatepoint(p1), rotatepoint(p2), rotatepoint(p3), rotatepoint(p4))
			end
		end
	end
	local oo = {p1[2]-p1[1]*s[1], p3[2]-p3[1]*s[2]}
	col = (oo[2]-oo[1])/(s[1]-s[2])
	return ((col<p1[1]) == (col>p2[1])) and ((col<p3[1]) == (col>p4[1]))
end
It won't work if the slope is NaN (ie, the line's width and height are 0)

There are other more robust (and faster) approaches like this one:
http://paulbourke.net/geometry/lineline2d/

Once you've got your line-line collision detection, the rest is easy:
Cast a line that starts at your point and extends towards infinity horizontally (just to make the line-line collision run faster, but it should work vertically too)
For both of these lines, check their collisions against all four sides of your rectangle and store the number of collisions.
If the number of collisions is uneven, the point is inside the figure, otherwise it's not.
edited 1×, last 12.08.12 06:07:28 am

old Re: Is a point (coordinate) inside or outside shape

Lee
Moderator Off Offline

Quote
If you're only working with quandrangles, you can preserve the efficiency of checking if a point is within a rectangle by subtracting off the angle of one of the sides of the rectangle.

Basically, we just rotate the x and y axis such that the rectangle is no longer rotated, then applies that inverse rotation on the point we're looking for. Mathematically, suppose h,w are two sides of the rectangle, then arbitrarily setting w as the principle x-axis, we find the rotation required to fit the rectangle onto the principle axes is just

IMG:https://mathbin.net/equations/105109_0.png


Suppose that your rectangle is wound as

1
2
3
p1 - p2
|     |
p3 - p4

then, in pseudocode, the following expresses the logic encoded above

1
2
3
4
5
6
7
8
function is_in(p1,p2,p3,p4, point)
	x,  y = (point - p3)
	hx, hy = p1 - p3
	wx, wy = p4 - p3
	A = x*hy - y*hx <= wx*hy - wy*hx
	B = y*wx - x*wy <= wx*hy - wy*hx
	return A and B
end

Edit: the above is only valid when wx*hy - wy*hx is not 0 and wx*hy - wy*hx = 0 if when rectangle doesn't have right angles
edited 1×, last 12.08.12 07:50:54 am
To the start Previous 1 Next To the start
Log in to reply Scripts overviewCS2D overviewForums overview