Fun, Games and Teaching

Recently in my first year Physics class I posed a problem to my students:

What is the most efficient way of determining if a given point lies inside a given polygon?

At the end of the context, I give the code my students sent me. And a game one of them created!!!

This is a real and living research problem. For me the context  is this: in the Finite Element mesh I construct, sometimes we want to move one of the nodes in a mesh element so that the photonic structure/boundary is better represented. The trouble is determining which node to move out of all the nodes in the element. Since you may have to do this for a large mesh with close to 100,000 elements, it must be fast, accurate and reliable.

So the students sent me this:

  1. Python code (by Riad Ibadulla) :

n=int(input(“Enter the size of polygon: “))
#input——————————————
x=[]
y=[]
z=0
j=0
print(“Enter the coordinates of polygon: “)
for i in range(n):
x.append(int(input(“x=”)))
y.append(int(input(“y=”)))
print(“Enter the coordiantes of the point: “)
x0=input(“x=”)
y0=input(“y=”)
#checking————————————–
for i in range(n):
z=(x0-x[i])*(y[i-(n-1)]-y[i])-(y0-y[i])*(x[i-(n-1)]-x[i])
if z>0:
j+=1
if j==n:
print(“belongs to polygon”)
else:
print(“out of the polygon”)

2. A game, Galactic Waste Man (by Kenneth Evbuomwan) that uses logic that is central to the problem posed. The code is available here: GameController.

So can your algorithm match/beat what my first years have done?

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s