1. mathmatical question.. - Reply

Lee woo seob wrote:

> Can anyone give me nice answer over the problem below;
> Assumes the polygon with arbitrary numbers of points is drawn on the
> pixel-graphics screen, for example;

> polygon(RED,1,{{100,200},{200,200},......,}

> Problem is:
> How can I know whether the mouse pointer is INSIDE the polygon or not,
> at the time the mouse button is pressed?


I am not sure I can give you a nice answer, but I thought it was interesting
enough problem. I am assuming you already know how to get the mouse pointer
coordinates - if not, please ask again.

There are several possible approaches to this problem, I simply coded the first
one that occurred to me: imagine a straight line through the point. In a
non-trivial case, the line will intersect with one or more sides of the
polygon. Now, travel from the given point in one or the other direction and
count the intersections. If the total is odd, you obviously started inside the
polygon and vice versa. - Incidentally, I chose a horizontal line in the
function inside() below, sequence p is x,y coordinates of the point, and P is
the polygon sequence. Jiri

Sorry, this is almost as long as some of Ralf's messages...


-- inpoly.ex -------------------------------------------------------------------
-- j.babor at gns.cri.nz
--------------------------------------------------------------------------------

include graphics.e
include get.e

object junk
sequence s,p1,p2,p3
integer key

function inside(sequence p, sequence P)
   atom x
   integer count,n
   n=length(P)
   P=append(P,P[1])
   count=0
   for i=1 to n do
      if (P[i][2]<p[2] and P[i+1][2]>p[2]) or
         (P[i][2]>p[2] and P[i+1][2]<p[2]) then
         x=P[i][1]+(p[2]-P[i][2])*(P[i+1][1]-P[i][1])/(P[i+1][2]-P[i][2])
         if x<p[1] then count=count+1 end if
      end if
   end for
   return remainder(count,2)  -- return 1 (true) if count is odd
end function

-- main ------------------------------------------------------------------------

junk=graphics_mode(18)

p1={30,250}
p2={80,250}
p3={200,250}

polygon(12,1,s)
pixel(15,p1)
pixel(14,p2)
pixel(9,p3)
print(1,{inside(p1,s),inside(p2,s),inside(p3,s)})
--printf(1,"%d",inside(p1,s))
key = wait_key()
junk=graphics_mode(-1)

new topic     » topic index » view message » categorize

2. Re: mathmatical question.. - Reply

> Sorry, this is almost as long as some of Ralf's messages...
        Gee, funny!

        If he doesn't use all of his colors, make the above 128 entries of
the pallete the same as the 128 under, and simple remove the
mousecursor, check the color, if it's above 128 it's inside, if it's
under 128 it's outside!!!
        If this is needed very deperate tell me and i'll write a routine
which checks give coordinates, and returns which polygons (plurar if
they can overlap each other) the mouse has clicked on

--> See how short it is...

new topic     » goto parent     » topic index » view message » categorize

3. Re: mathmatical question.. - Reply

Lucius L Hilley III wrote:

> Jiri's Reply has SOME merit mathmatically.
> However it is only 50% accurate.

50%? - If I were you I would go back to my math teacher and demand a refund.

Lee woo seob posed a mathematical problem (his words, not mine), he can do
palette shuffling and/or pixel color detection well enough on his own - see his
snow poem program on The Official Euphoria Page. He also emphasized "INSIDE the
polygon" (his capitals, not mine!), and that is why my routine would not even
detect your boundary (vertex) point. (Btw, *odd* count indicates the point *is*
inside - can't you even read?)
And how is triangulation going to help anything? Pure magic? Jiri

new topic     » goto parent     » topic index » view message » categorize

4. Re: mathmatical question.. - Reply

On Fri, 30 May 1997 11:23:34 +1200 "BABOR, JIRI" <J.Babor at GNS.CRI.NZ>
writes:
>---------------------- Information from the mail header
>
>Lee woo seob posed a mathematical problem (his words, not mine), he
>can do
>palette shuffling and/or pixel color detection well enough on his own
>- see his
>snow poem program on The Official Euphoria Page. He also emphasized
>"INSIDE the
>polygon" (his capitals, not mine!), and that is why my routine would
>not even
>detect your boundary (vertex) point. (Btw, *odd* count indicates the
>point *is* inside)
>And how is triangulation going to help anything? Pure magic? Jiri

not triangulaion.
Triangulation is finding a point by using three reference points.

I propose cutting the image into triangles because a triangle
is the fewest sided polygon. It can't a concave shape.
       ____
 /\   \    /
/__\  /____\

As this image shows even a 4 sided figure can have a concave
shape giving the possibility of an inaccurate COUNT.
and BTW My thought of going in opposite directions doesn't
work either for the same reason your count won't.

 ____
|    |  the dot is where the click was made.
|    |
| /\.|
|/  \|
  ____
 |    |  this line gives a count of 4.
 |    |
_|_/\_|_
 |/  \|


 ____
|    |  the dot is where the click was made.
|   .|
| /\ |
|/  \|
  ____
 |    |
_|____|_  this line gives a count of 3.
 | /\ |   BOTH clicks are inside.
 |/  \|

new topic     » goto parent     » topic index » view message » categorize

Search



Quick Links

User menu

Not signed in.

Misc Menu