16 replies to this topic

[FatalSleep]

So I have a few collision with point functions... what they do is check if a point: x1,y1 are within a figure: triangle, circle, rectangle, and quadrilateral.
However I did not make the triangle and quadrilateral scripts.

Here they are:

Spoiler

//Point Collision Triangle
var x1, y1, x2, y2, x3, y3, x4, y4, a, b, c;
x1 = argument0; y1 = argument1; x2 = argument2;
y2 = argument3; x3 = argument4; y3 = argument5;
x4 = argument6; y4 = argument7;
a = (x2 - x1)*(y3 - y1) - (x3 - x1)*(y2 - y1);
b = (x3 - x1)*(y4 - y1) - (x4 - x1)*(y3 - y1);
c = (x4 - x1)*(y2 - y1) - (x2 - x1)*(y4 - y1);
return (sign(a) == sign(b) && sign(b) == sign(c));

//Point Collision Quadrilateral

var a, b, c, d;
a = (argument[8] - argument[0])*(argument[3] - argument[1]) - (argument[2] - argument[0])*(argument[9] - argument[1]);
b = (argument[2] - argument[0])*(argument[5] - argument[1]) - (argument[4] - argument[0])*(argument[3] - argument[1]);
c = (argument[4] - argument[0])*(argument[7] - argument[1]) - (argument[6] - argument[0])*(argument[5] - argument[1]);
d = (argument[6] - argument[0])*(argument[9] - argument[1]) - (argument[8] - argument[0])*(argument[7] - argument[1]);return (sign(a) == sign(b) && sign(b) == sign(c) && sign(c) == sign(d));

I am only presenting these because I did not make them, and I am guessing the general idea for a collision
with polygon code would be similar in the way these are done. So how exactly would I code this problem?

Edited by FatalSleep, 20 September 2012 - 10:01 AM.

[Experimenator]

The only idea I can think of is to check whether every point of the polygon is in another polygon, and again but from 2nd to 1st polygon.

Scripts:

Spoiler

/* I'm lazy enough to not create my own and use GMLscripts.com's script - Experimenator
**
**  Usage:
**      point_in_polygon(x,y,polygon);
**
**  Arguments:
**      x,y        a test point, real
**      polygon    ds_list containing XY coordinate pairs defining
**                 the shape of a polygon
**
**  Returns:
**      TRUE if the point is inside the polygon,
**      FALSE otherwise
**
**  GMLscripts.com
*/
{
    var x0,y0,polygon,inside;
    var n,i,poly_x,poly_y,x1,x2,y1,y2,m,b,ix,iy;
    x0 = argument0;
    y0 = argument1;
    polygon = argument2;
    inside = false;
    n = ds_list_size(polygon) div 2;
    i = 0;
    repeat (n) {
        poly_x[i] = ds_list_find_value(polygon, 2*i);
        poly_y[i] = ds_list_find_value(polygon, 2*i+1);
        i += 1;
    }
    poly_x[n] = poly_x[0];
    poly_y[n] = poly_y[0];
    i = 0;
    repeat (n) {
        x1 = poly_x[i];
        y1 = poly_y[i];
        x2 = poly_x[i+1];
        y2 = poly_y[i+1];
        if (((y1 <= y0) && (y2 > y0)) || ((y1 > y0) && (y2 <= y0))) {
            if (x1 == x2) {
                if (x1 > x0) inside = !inside;
            }else{
                m = (y2 - y1) / (x2 - x1);
                b = y1 - m * x1;
                ix = (y0 - b) / m;
                iy = y0;
                if (ix > x0) inside = !inside;
            }
        }
        i += 1;
    }
    return inside;
}

/*
**  Usage:
**      polygon_intersects(polygon1,polygon2);
**  Arguments:
**      polygon1   first polygon stored into a ds_list
**      polygon2   second polygon
**
**  Returns:
**      TRUE if the 2 polygons intersect
**      FALSE else
**
**  Experimenator
*/
{
    var i,p1,p2,xon,yon,ret;
    p1 = argument0;
    p2 = argument1;
    for (i=0;i<ds_list_size(p1);i+=2){
        xon = ds_list_find_value(p1,i);
        yon = ds_list_find_value(p1,i+1);
        ret = point_in_polygon(xon,yon,p2);
        if (ret) return ret;
    }
    for (i=0;i<ds_list_size(p2);i+=2){
        xon = ds_list_find_value(p2,i);
        yon = ds_list_find_value(p2,i+1);
        ret = point_in_polygon(xon,yon,p1);
        if (ret) return ret;
    }
    return 0;
}

I haven't tested it, but I suppose it would work.
I can't guarantee the best performance but You can also try checking if every side of the polygon intersects another polygon which might be faster.

I would suggest you to read this: http://www.mathopenr...coordintro.html
So you can get a better understanding how those stuff work.

EDIT: Someone moved this topic to 3D Game Techniques. idk why but this is pure 2D

Edited by Experimenator, 20 September 2012 - 11:31 AM.

[FatalSleep]

Well after editing the other scripts I cam up with this 5 sided polygon:

Spoiler

//This script was used for debugging: 32simple_ext 5.0.1.2
var a, b, c, d, e;
a = (argument[10] - argument[0])*(argument[3] - argument[1]) - (argument[2] - argument[0])*(argument[11] - argument[1]);
b = (argument[2] - argument[0])*(argument[5] - argument[1]) - (argument[4] - argument[0])*(argument[3] - argument[1]);
c = (argument[4] - argument[0])*(argument[7] - argument[1]) - (argument[6] - argument[0])*(argument[5] - argument[1]);
d = (argument[6] - argument[0])*(argument[9] - argument[1]) - (argument[8] - argument[0])*(argument[7] - argument[1]);
e = (argument[8] - argument[0])*(argument[11] - argument[1]) - (argument[10] - argument[0])*(argument[9] - argument[1]);
return (sign(a) == sign(b) && sign(b) == sign(c) && sign(c) == sign(d) && sign(d) == sign(e));

So I guess I understand this script, so I'll see if I can convert it to a polygon that can have an infinite number of sides using
a for loop.

Edited by FatalSleep, 20 September 2012 - 02:38 PM.

[Experimenator]

Now I don't understand what are you trying.
Why are you making your own point_in_polygon when that script already exists?
(look at the first script in my 1st post)
And also, are you looking for polygon-polygon or point-polygon collision?

[FatalSleep]

This is because using an entire data structure for one polygon is extremely inefficient.
Why would I use data structures when it can be done without it?

Anyways I've made multiple scripts for different sided polygons: pentagon, hexagon, heptagon.
All without data structures.

[Experimenator]

You know, a Personal Computer usually has 2GB memory and 1.6GHz Processor which means it can do a billion operations in a second. a tiny Data Structure, like this, (+-32 elements) is so tiny that it will NEVER affect the performance of the program. My own computer, weaker than the standard, can do 30000 elementAdds without any performance problem.
And you think those minute 10-20 elements
DataStructures are not performance-consumers. They are made to kill that.

Also it is even more inefficient using scripts because whenever you call a script, all 16 arguments have to be rewritten to use a script. And you cannot do n-sided because Game Maker can have 16 arguments at max.

If you were going to say that on http://stackoverflow.com/ you would have got tones of down votes because they absolutely hate when people are concentrating to maximum performance instead of focusing on the main issues.
Unfortunately, this isn't stackoverflow.

Why did you ask the question at all when you don't want to hear the answers, and replying how you are able to create those by yourself?

Edited by Experimenator, 21 September 2012 - 11:54 AM.

[FatalSleep]

A personal computer can do that. However Game Maker cannot, so if I say had a full fledged game with particles and 3d and data structure I'd have to be worried about performance so I don't drop the games fps and make the game unplayable. So why would I waste extra memory to preform an action that I can do in about 1/4 of that extra memory. Its not a matter of maximum performance, its a matter of being efficient and concise! Besides here I am focusing on efficiency and the main issue itself not only on maximum performance.

The only reason I said I could do it is because I realize a pattern. A pattern in the scripts allowing me to easily alter the scripts to make larger polygons. I didn't realize this until after you posted your scripts. I am sorry to have caused you trouble having you present those scripts and then me rejecting them. However I though it would be better if I found an easier way to create polygon collisions so as to where I could understand how those collisions were handled.

In a way you helped me quite a bit. I disliked how your scripts were handling those collisions so that pushed me even further into trying to figure it out myself. See I am a person that likes to learn. So if I can take a script as small as the ones I had and be able to expand them to make them more useful then that's what I am going to do. For me this is all a learning experience so I want to be able to do things myself to make myself a better programmer. If I simply just took your scripts and accepted them I wouldn't have learned anything since those scripts already can have as large of a size of polygon as I wanted.

Edited by FatalSleep, 21 September 2012 - 01:37 PM.

[Experimenator]

If you want to learn I already have said, read this: http://www.mathopenr...coordintro.html
Afterwards you'll be able to do everything with geometry, even create your own algorithms and scripts.

You should stop being afraid of data structures. If you would have seen how they are made and how they internally I believe you would too agree that they are very efficient.
Try this script for example:

var ds,i;
ds = ds_list_create();
for (i=0;i<50000;i+=1)
   ds_list_add(ds,0);

I can guarantee that it won't last a second.
Unless you have more than 1000 elemnts ds_list will take almost none of CPU power.
There is nothing to "efficianate" there.

The point-polygon script uses even-odd rule which is widely use among those like algorithms.

Also, it isn't fair because, I +1 your original post before, and -1 one of your posts later which basecally means I gave you no change in reputation while you downvoted me.
All because I was trying to help you.

[FatalSleep]

Haha. Well then. I am not afraid of data structures I know every well what they can do. Oh I have no trouble with geometry really, I just have trouble mixing the math I learn in with Game Maker.
Thats why i was manipulating the scripts I presented. Btw I think a ds_list can only have up to 32,000 entries.

Anyways thanks for the help(I've learned quite a bit here).

Edited by FatalSleep, 21 September 2012 - 03:16 PM.

[Experimenator]

Btw I think a ds_list can only have up to 32,000 entries.

They go all through the infinity

Edited by Experimenator, 21 September 2012 - 03:32 PM.

[FatalSleep]

Btw I think a ds_list can only have up to 32,000 entries.

They go all through the infinity

Heh, if they can make ds_lists do that, I wonder why they can't do that with arrays...

[Experimenator]

When I was making my own language it was very easy to make an array to contain any number and even a string.
just making a variable name string made like this "variableName+arrayValue+]" and you then you can make any array you want even multidimensional and infinite.

idk why can't it be done here.

[FatalSleep]

Heh Game Maker is weak thats why. I can't wait till YoYo starts fixing all these small stupid things in Game Maker.

[Experimenator]

It is weak indeed. >_>
But maybe things are fixed up in studio.
I don't have it so idk.

[brac37]

The red cross is made of two overlapping red rectangles without polygon points in the other polygon.

Edit: here is an algorithm.
http://content.gpwik...lygon_Collision
Edit edit: only convex polygons.

With non-convex polygons, you can test whether there are crossing edges. If this is the case, then there is intersection.

If not, then take an arbitrary point of polygon 1 and test whether is in polygon 2. If this is the case, then there is intersection.

If not, then take an arbitrary point of polygon 2 and test whether is in polygon 1. If this is the case, then there is intersection. If this is not the case, then there is no intersection.

You can test whether a point is inside a polygon by making an artificial edge from the point to a very far point, and compute the parity of the number of intersections with edges of the polygon, see
http://paulbourke.ne...try/insidepoly/

Edited by brac37, 21 September 2012 - 08:14 PM.

[gmx0]

If hasn't been done or said already, all polygons can be split into triangles, so just repeat the triangle collision function for three different points until it returns true?

[Gamer3D]

If hasn't been done or said already, all polygons can be split into triangles, so just repeat the triangle collision function for three different points until it returns true?

That would be inefficient, and it would only work properly for convex polygons.

One method is to count the number of line segments intersecting with a ray going from x,y to the right (or in any other direction, so long as it's consistent). If the number is even, you're outside. If odd, you're inside.
Note that you need to be careful not to count vertexes twice.

Also, you probably didn't need to revive a post from September....