FBA The Creator

OK clever people here goes, a nice puzzle for Sunday evening for those not watching Spain beat Germany

Imagine drawing a line from the screen top left to the bottom right. Then draw a line from the screen top right to the bottom left. So you have drawn a big X, dividing the screen into 4 triangles. The user then taps the screen with their stylus, I need to know which 'triangle' the stylus is in.

Any ideas on the maths behind this?

Thanks in advance

Of course you only really need to know if it's in the top or bottom triangle, cos if it's not then if the X position is less than the screen width divided by 2 then its in the left triangle and if not then it's in the right.

So how can I detect whether it's in the top or bottom triangle?

_________________
http://www.boiledsweets.com

Dont need to reinvent the wheel, there'are lots of algorithm solving this problem (google for "point inside a polygon").

The one I used in one of my games use an array of point (x,y) defining a closed polyline.
I dont remember the url, I'll give a look as soon as Ill go home.

_________________
Regards,

umbiomar
[email protected]

OK, i recover that old code I used to detect point inside a polygon with 4 vertex (here named "quad"), the source is C++ because that code was written in c++

If i got some time i'll change it to lua syntax. hope this helps.

class Quad {

   public:
      //costruttori
      Quad();
      Quad(Point p0, Point p1, Point p2, Point p3);
      Quad(int x0, int y0, int x1, int y1, int x2, int y2, int x3, int y3);
      //distruttore
      ~Quad();

      Point p[4];   // array dei vertici

      virtual int dot(int x0, int y0, int x1, int y1, int x2, int y2);
      virtual bool InsideQuad(int px, int py);
      virtual bool InsideQuad(int px, int py, int x0, int y0, int x1, int y1, int x2, int y2, int x3, int y3);
   private:

};

Quad::Quad(){/* TODO:*/};

Quad::Quad(int x0, int y0, int x1, int y1, int x2, int y2, int x3, int y3) {

   this->p[0].x= x0;
   this->p[0].y= y0;
   this->p[1].x= x1;
   this->p[1].y= y1;
   this->p[2].x= x2;
   this->p[2].y= y2;
   this->p[3].x= x3;
   this->p[3].y= y3;
}

Quad::Quad(Point p0, Point p1, Point p2, Point p3) {

   this->p[0].x= p0.x;
   this->p[0].y= p0.y;
   
   this->p[1].x= p1.x;
   this->p[1].y= p1.y;

   this->p[2].x= p2.x;
   this->p[2].y= p2.y;

   this->p[3].x= p3.x;
   this->p[3].y= p3.y;
}

Quad::~Quad(){};

int Quad::dot(int x0,int y0,int x1,int y1,int x2,int y2) {
   return (x1-x0)*(y2-y1)-(x2-x1)*(y1-y0);
}

bool Quad::InsideQuad(int px, int py) {

   return InsideQuad(px, py,
         this->p[0].x, this->p[0].y,
         this->p[1].x, this->p[1].y,
         this->p[2].x, this->p[2].y,
         this->p[3].x, this->p[3].y );
}


bool Quad::InsideQuad(int px,int py,int x0,int y0,int x1,int y1,int x2,int y2,int x3,int y3) {
   bool bInside= false;
   if ( dot(x0,y0,x1,y1,px,py)>0 )
      if ( dot(x1,y1,x2,y2,px,py)>0 )
         if ( dot(x2,y2,x3,y3,px,py)>0 )
            if ( dot(x3,y3,x0,y0,px,py)>0 )
               bInside=true;
   return bInside;
}

_________________
Regards,

umbiomar
[email protected]

After searching for a while and testing a lot of different code, I came up with this function for FBA.

function pointInPolygon(x, y, polyX, polyY)
  local polySides=table.getn(polyX)
  local oddNodes=true
  local counter=0

  p1x = polyX[1]
  p1y = polyY[1]
  for i=1,polySides do
    p2x=polyX[math.fmod(i,polySides)+1]
    p2y=polyY[math.fmod(i,polySides)+1]
    if y>math.min(p1y,p2y) then
      if y<=math.max(p1y,p2y) then
        if x<=math.max(p1x,p2x) then
          if p1y~=p2y then
            xinters=(y-p1y)*(p2x-p1x)/(p2y-p1y)+p1x
            if p1x==p2x or x<=xinters then counter=counter+1 end
          end
        end
      end
    end
    p1x = p2x
    p1y = p2y
  end

  if math.fmod(counter,2)==0 then oddNodes=not oddNodes end
  
  return oddNodes
end

It should work for any polygon, complex or simple. The arguments required are the x and y coordinates to test and two arrays: the first gives the x coordinates of your polygon's vertices, and the second gives the y coordinates of your polygon's vertices.

Here is my entire test project code:

xcoords={0,239,119}
ycoords={0,0,159}
clicked="No"

function pointInPolygon(x, y, polyX, polyY)
  local polySides=table.getn(polyX)
  local oddNodes=true
  local counter=0

  p1x = polyX[1]
  p1y = polyY[1]
  for i=1,polySides do
    p2x=polyX[math.fmod(i,polySides)+1]
    p2y=polyY[math.fmod(i,polySides)+1]
    if y>math.min(p1y,p2y) then
      if y<=math.max(p1y,p2y) then
        if x<=math.max(p1x,p2x) then
          if p1y~=p2y then
            xinters=(y-p1y)*(p2x-p1x)/(p2y-p1y)+p1x
            if p1x==p2x or x<=xinters then counter=counter+1 end
          end
        end
      end
    end
    p1x = p2x
    p1y = p2y
  end

  if math.fmod(counter,2)==0 then oddNodes=not oddNodes end
  
  return oddNodes
end

function onmainloop()
  clear(0,0,0)
  line(0,0,239,319,255,255,255)
  line(239,0,0,319,255,255,255)
  print(10,150,clicked.." triangle clicked.",255,0,0)
end

function onstylusdown(x,y)
  if pointInPolygon(x,y,xcoords,ycoords) then
    clicked="Top"
  else
    clicked="No"
  end
end

_________________
Don't look at me. I'm new here.

Outstanding work!!!

I really appreciate this, demo coming soon...

_________________
http://www.boiledsweets.com

Let me suggest an alternative way to solve your problem using maps with in-memory pictures.

Two notes before you jump out of your window by happines
1 - for your case, is better to use a mathematical approach, because you can easy track points inside triangles using previous solutions; you will save memory needed by an hidden mask ! (note: memory needed for an image is <width * height * 2> bytes, so for a full screen mask you'll need 240*320*2 = 153600 bytes, lot of memory, imho !)
2 - this method could be used if you have very complex maps where you'd like to track points (i can't figure any example now btw ), in these cases, mathematical approach could be difficulty if you have lot of zones and shapes..

Actually i don't know why i posted that...just to show some different code :D

That certainly looks like a good way of check for really complex shapes. One thing, though: whenever I clicked in one of the triangles, it reported my position as the bottom until I moved my mouse again. It seems like I've read about that issue before, but I'm not sure.

_________________
Don't look at me. I'm new here.

This isn't really a bug...but how currently FBA works

This is what happens inside FBA...
When the application triggers mousedown/move/up.. FBA updates an internal variable (let's say CURRENTMOUSEX and CURRENTMOUSEY) with current mouse position..

FBA functions mousex() and mousey() return values CURRENTMOUSEX and CURRENTMOUSEY

When FBA is launched CURRENTMOUSEX and CURRENTMOUSEY are set to -1
When FBA receives the mousedown/move events, it updates CURRENTMOUSEX and CURRENTMOUSEY with current position.
When FBA receives the mouseup event, it sets CURRENTMOUSEX and CURRENTMOUSEY to -1..

I wonder if it's better to leave them as is when FBA get the mouseup event...
(My original idea was: if we aren't clicking the stylus, keeping latest CURRENTMOUSEX/Y is not correct, that's why FBA reset them to -1)

I updated the zip in my previous post with a way to avoid the "-1" weird behaviour

Implemented using phrebh maths...

Works great and seems pretty fast. I think it's a really useful exmaple that should be added to the FBA examples for the next release. I used the co-ords...

-- TABLES

top_tri_x = {1, 239, 119}
top_tri_y = {0, 0,   159}

bottom_tri_x = {119, 0,   320}
bottom_tri_y = {160, 320, 320}

right_tri_x = {240, 120, 320}
right_tri_y = {0,   119, 320}

left_tri_x = {0, 119, 0}
left_tri_y = {0, 119, 320}

_________________
http://www.boiledsweets.com

Feel free to update the showcase area with your samples/tutorials/full projects