Unit enumeration within an arbitrary shape

[BlueMirage]

Well, as understood from the title (psyche), if I have several points which form a shape, how can I pick all units inside it?

I'ma go draw a picture in paint. brb

Alright, I think I have a solution. Kind of.

Assume that your unit is centered on Origo. 1 is the first point of your shape, and 2 or 3 are the second (Two examples).

For the first example, make a line between 1 and 2, and create the function (y=f(x)) for it. For this example, if the point where Y = 0 is on this line, then the unit is inside the first line of your shape. If it however is not, then the unit is not inside the shape at all.

The line between 1 and 3 would generate a line that would not hit the point where Y = 0, so the unit is outside the shape.

If two points are in the same quadrant, the unit being checked passes and is inside the line being checked.

Obviously, if you check for either X or Y depends on which quadrant the first point is in.

Loop this for each point in your shape, and you should get if the unit is inside or not. Note that each point must have a number so that you can pick them in the correct order.

It might not be the most effective method, but it's the only one I can come up with.

 

[The Undaddy]

Ok find a function and a bunch of checks and it's done.

Actually I understood little to nothing form what you said.

>and create the function (y=f(x))

Do you mean to literally, having y = f(x) = ax + b, find a and b?

Secondly I think you got your 2s and 3s wrong

>The line between 1 and 3(sic) would generate a line that would not hit the point where Y = 0, so the unit is outside the shape.

But if my figure is 123 it's a triangle and (0,0) is within it's boundaries?How is the unit magically outside of it.

>each point must have a number so that you can pick them in the correct order.

Well they do, but I would need more explanation on the first part

Thanks

 

[SineCosine]

Points A. B and C

......A......
..............
..............
.B........C.

set AB = Atan2(By - Ay, Bx - Ax)
set AC = Atan2(Cy - Ay, Cx - Ax)
set CB = Atan2(By - Cy, Bx - Cy)

set AD = Atan2(Dy - Ay, Dx - Ax)
set CD = Atan2(Dy - Cy, Dx - Cx)

if AD > AB and AD < AC and CD < CB then

        //Do Stuff

endif

Something like that? o.0

 

[The Undaddy]

@SineCosine

[del]I think that'll work perfectly, thanks[/del] :thup:

EDIT: I think I spoke too soon
..........B....
................
...A...........
..........D....
...............
..............C

Here AD > AC but still D is inside of the shape

 

[BlueMirage]

Wait, it's always a triangle?

 

[SineCosine]

I can explain that,

A has to always be on top
B has to always be at the bottom left
C has to always be at the bottom right

XD

Now..
......A......
..............
......D......
.B........C.
//////////////
......B......
..............
......D......
.C........A.
////////////////
......C......
..............
......D......
.A........B.
///////////////

Okay, I am going to type out something..
Give me time to give a better formula xD

[EDIT]
Okay, here goes..

//These are all the things we need..
real Ax
real Ay
real Bx
real By
real Cx
real Cy

real Dx
real Dy

real BD
real BA
real BC
real CD
real CA

boolean Boolean1

boolean Boolean2

boolean Boolean3

//We are finding out if D is on the correct side of BA
set BD = Atan2(Dy - By, Dx - Bx)
set BA = Atan2(Ay - By, Ax - Bx)

if BA > BD then
     set Boolean1 = true
      // This is because we have shown that as long as A, B and C are always the same, you can orientate it however you want, but if D is within ABC, then in the result of BD and BA, BA will always be larger than BD
endif

//We are finding out if D is on the correct side of BC
set BD = Atan2(Dy - By, Dx - Bx)
set BC = Atan2(Cy - By, Cx - Bx)

if BD > BC then
     set Boolean2 = true
      // This is because we have shown that as long as A, B and C are always the same, you can orientate it however you want, but if D is within ABC, then in the result of BD and BC, BD will always be larger than BC
endif

//We are finding out if D is on the correct side of CA
set CD = Atan2(Dy - Cy, Dx - Cx)
set CA = Atan2(Cy - Ay, Cx - Ax)

if CD > CA then
     set Boolean3 = true
      // This is because we have shown that as long as A, B and C are always the same, you can orientate it however you want, but if D is within ABC, then in the result of CD and CA, CD will always be larger than CA
endif

//Tada!!

if Boolean1 == true and Boolean2 == true and Boolean3 == true then
     call BJDebugMsg("I AM INSIDE THE TRIANGLE")
endif

Just make sure you don't change your A, B and C the moment you set them, lol
I would upload an image explaining my logic, but..
I am a bit lazy =x

I won't guarantee it works..
But you can try xD

 

[The Undaddy]

Wait, it's always a triangle?

No, but in your example it is

 

[BlueMirage]

Actually, in my example it's only a part of a bigger shape, disregarding which. In my example, the part is one of that shape's lines.

 

[SineCosine]

You can make it apply to other shapes, arbitrary shapes.

Just decide on a path.

..A...................
...................B..
.............Z........
.D....................
.......................
...................C..

Just make sure you go one way, I suppose.

//Something
AB = Atan2(By - Ay, Bx - Ax)
AZ = Atan2(Zy - Ay, Zx - Ax)

AB > AZ then return true

//Something
BC = Atan2(Cy - By, Cx - Bx)
BZ = Atan2(Zy - By, Zx - Bx)

BC > BZ then return true

//Something
CD = Atan2(Dy - Cy, Dx - Cx)
CZ = Atan2(Zy - Cy, Zx - Cx)

CD > CZ then return true

//Something
DA = Atan2(Ay - Dy, Ax - Dx)
DZ = Atan2(Zy - Dy, Zx - Dx)

DA > DZ then return true

If all of the above == true then
 //It IS inside that shape xD
endif

//I think..