Investigations on star polygons with a star polygon / stellar number generator

June 30, 2010

Note 9/3/2010: Redone all of the diagrams

If you are just looking for a download link to the program, here it is. To run, save as Stellar.jar (Java is required)

As school has been over for more than a week now, I’ve had time to (among other things) study geometry. I’m just spending an hour or two every day working through various exercises in Geometry Revisited.

This blog post is long overdue; it had been sitting in my drafts section with a few sentences written since the middle of April. Maybe it’s still useful now, maybe not. Anyways.

I myself am not in IB, because of my hatred of being forced to do copious and tedious amounts of homework. Many of my friends, however, take IB math. One famous project in IB math (not only in my school, but also in other schools) is a large project known as the math portfolio. From what I’ve heard, this consists of a dozen or so pages of writeup on some extended problem.

I first heard about the existence of such a project when a few of my friends asked me for help on it. The project was related to ‘stellar numbers'; a picture of the assignment can be found here. The problem itself seems rather trivial, thus I don’t feel it necessary to discuss it in this blog post.

My investigations here, although inspired by this assignment, is only marginally related to the assignment itself. The end product to be handed in for grades was supposed to include diagrams. However, it isn’t so easy to draw diagrams of stars (see above image) either by hand or on the computer. I saw many of my friends hastily put together their diagrams of stars using Powerpoint or MS Word, using the line and circle tools and a heck lot of copy-and-pasting. The result, unsurprisingly, is messy and inexact. One friend of mine wrote a computer program to output Latex code to draw the stars; the details of how this is done is something I consider more difficult and interesting than the project itself.

Keeping along with my theme of geometry this week, it is useful to figure out the geometry of star polygons before writing programs to generate them.

Some geometric constructions

Consider the five sider star (fig.1):

We can see that the five corners of the star, ABCDE, are the same distance from the center K of the star. This means the five points lie on a circle; furthermore the distances between the corners are the same.

A similar phenomenon occurs with the five points between the corners, FGHIJ. They, too, lie on a circle centered around K.

Let us call the radius of the larger circle r, and the radius of the smaller circle i. Any star can be built around the framework of two circles. For example, our five pointed star (fig.2):

There is, however, one more characteristic present in star polygons that we neglected in the above diagram. It is that we chose the values of r and i pretty much arbitrarily.

Notice that in (fig.1), the sides EF and GB are parallel. It can be shown geometrically that if parallel, EF and GB are also concurrent. In (fig.2), EF and GB are not parallel nor concurrent.

Although any values of i and r for i<r are enough to produce a star, it is necessary to further adjust the ratio between i and r in order to produce a correct star polygon.

Let us denote n to mean the number of points of a star, and d to denote the density of a star.

What do we mean by density? In order to define density, we will take a step back and take a look at alternative ways that star polygons can be constructed.

At present we are looking at star polygons as points on two distinct circles joined together with alternating line segments. Here is a completely different way of presenting it (fig.3):

Points ABCDE are spread equally on a circle. For the five points, every two points are connected by a line. We define density to be this number: the density for this star is 2.

It is possible, perhaps easier, to implement a drawing routine this way. However, by doing this we would have to erase the lines FGHIJ, which seems straightforward but is troublesome in implementation. We are going to stick to the two circles paradigm.

If d=1 , then our ‘star’ would be degenerate; it would merely be a n-sided polygon. On the other hand, we assume that the inner circle has positive radius, thus,

d < \frac{n}{2}

For any integer n with n \geq 3 , the maximum value of d is given by:

d \leq \lfloor \frac{n-1}{2} \rfloor

Next is finding a way to express the ratio between the radii in terms of n and d.

Here we combined the previous two diagrams, and added some new lines. Since our star contains so much symmetry, what follows can be extended to all corners of the star, and also to stars with different densities and number of corners.

Let us call the angle \angle EKA to be x, which is \frac{1}{n} of the circle, or \frac{2 \pi}{n} radians.

Let y be the angle such that

x:x+y = 1:d

.. whence here d=2 , therefore x=y=72^\circ .

As \triangle EKB is isosceles, \angle BEK = \angle EBK , and \angle BEK + \angle EBK + x + y = 180^\circ ; therefore

\angle BEK = \frac{1}{2}\left[ 180-(x+y) \right] = 90-\frac{1}{2}(x+y)

.. whence here \angle BEK = 18^\circ .

Next, \angle EKL = \frac{1}{2}x , in our case 36^\circ , thus the measure of \angle EFK can be found:

\angle EFK = 180 - \left[ 90-\frac{1}{2}(x+y) \right] - \frac{1}{2}x = 90 + \frac{1}{2}y

In our case \angle EFK = 126^\circ.

By the sine law in \triangle EKF,

\frac{r}{\sin (90 + \frac{1}{2}y)} = \frac{i}{\sin \left[90-\frac{1}{2}(x+y) \right]}

Or,

i = \frac{r \sin \left[90-\frac{1}{2}(x+y) \right]}{\sin (90 + \frac{1}{2}y)}

Simplifying, we get

i = \frac{r \cos \left[ \frac{1}{2}(x+y) \right]}{\cos (\frac{1}{2}y)}

We defined that x = \frac{2 \pi}{n} and that x+y = \frac{2 \pi d}{n} , thus we write y:

y=\frac{2 \pi (d-1)}{n}

And that brings us to the final formula:

i = \frac{r \cos (\frac{\pi d}{n})}{\cos \left[ \frac{\pi (d-1)}{n} \right]}

Evaluating it for our star, we find that if r=1, then d \approx 0.38197.

Implementation in Java

Now that we have the math done, it is a fairly easy programming exercise to implement this as a java application. Here’s what I came up with after ~2 hours of hacking in Netbeans (animated gif):

This may be useful to future people doing the same assignment (if it ever gets assigned again), or with modifications it may be useful for other purposes too.

To use it, adjust the settings, take a screenshot, crop it, and it may be necessary to further edit it in photoshop.

Without further ado, here’s the application as a jar file:

(broken link removed)

Or the source as a Netbeans project:

stellar-src.zip (37kb)

Do whatever you want with them, and have fun!


A school-related computer game

June 8, 2010

My blog has been somewhat neglected for the past few days. I suppose one of the reasons is my work on a really big school project.

In place of a final exam, the Language Arts course at my school offers something called a Language Arts portfolio, consisting of three projects. The creative portion of the portfolio is quite free-form: you were to pick a novel and do pretty much anything you wanted on it.

For this project I chose the novel Siddhartha by Herman Hesse:

I chose to create a Java game for this assignment. The game was a sort of role-playing platformer, and in my own words, ‘a combination of Runescape and Maple Story’.

This project took up most of my time for the last week or so. Planning began about four weeks ago, and I began coding and writing the dialogs about three weeks before. I nevertheless scrambled to complete all of the graphics and put it all together on the weekend.

Unlike most Language Arts assignments, I actually quite enjoyed making this game, and I’m proud of my work. I’m going to release the game along with its source code:

siddhartha.zip (1.7 mb)

On windows, the game can be run by double-clicking game.bat. Java 1.5 or later is required to run this game.

Here’s what the game looks like:

I was given an opportunity to ‘present’ my project to the class today. The school laptop had a problem with some java dll’s, but a classmate had a working laptop so the presentation went fairly well. I discovered one or two bugs in the presentation that I never noticed when testing the game.

I also tried to get my girlfriend to playtest the game, which kind of failed miserably.

Technical details of the game

Before starting coding for the game, I searched for existing, similar, open source, java alternatives. Finding none, I was forced to make my own.

If anyone else ever wants to make a similar game, my work here might be useful. If I myself were to make something like this again in the future, I wouldn’t have to write the game from scratch again. Of course by then I would have forgotten how the code works; it would benefit me to write about it here to refer back to in the future.

The following section is probably too technical and would be only useful when trying to understand my code. Anyways.

The game is written in about 1300 lines of Java code (although about 60% of it was configuration so only about 600 lines of it was game logic). The images are mostly drawn in MS-Paint, since I’m not very skilled at using Photoshop. I only used Photoshop to change all of the white pixels to transparent pixels (impossible in MS-Paint).

I chose JGame for the game engine. This is a decent game engine, although I think it’s a bit buggy and very unprofessional (the sample games look like they’re from the 1980’s). It’s backed by OpenGL, not because the game uses any OpenGL features, but because the non-OpenGL version of the library has a certain bug in one of its functions that I wasn’t sure how to circumvent.

This particular bug was about the setBGImage() function, which seemed to not work on the JRE version of JGame. I asked a question on Stack Overflow, but didn’t really get an answer.

The most complicated portions of the game was handling transitions between maps, and handling dialogs. The handling of maps was done completely in Java code, while the dialogs were handled in an ad-hoc scripting language I created for this purpose.

To transition between maps, I had the idea of a portal, which would activate at certain points and replace the existing map (and all its objects) with a new map, and adjust the game state accordingly. In essence, a portal has a one-way connection to another portal. To make such a connection, a portal keeps a reference to its connecting portal, so that it can change the game accordingly when needed.

The portal has an off state, an on state (when the player is touching the portal), and an active state (when the transition between maps is taking place). If a portal has a connecting portal, it is ‘activated’ when the up key is pressed, otherwise it cannot be activated.

A map in the game takes up exactly one screen, has one background image, can have multiple portals, and at most one NPC (non player character). There are 28 maps in this game (some sharing the same background).

A NPC is a character in the game that’s not the player. A NPC has a still (non-animated) sprite, and holds a constant position in exactly one map. The same NPC appearing in different maps may have the same sprite, but are otherwise completely different. A NPC has a name, which is shown above the NPC’s head on mouse over; when clicked the player enters a conversation. A NPC has exactly one conversation attached to it.

The conversation data in the game is defined in a file: speech.dat. The first part of the file contains a sort of scripting language describing how the conversations flow, while the second part is a dump of all the actual String data to put for the dialogs. Each line in the String data section is assigned a number starting from 0, to be referred to in the rest of the game.

A conversation always starts with the player. From there, whoever is speaking can continue to speak (the same command), or the other person can start speaking (the chgspk command). Either that, or we can present the player with a list of choices (the choose command). When the conversation ends, we direct the next line to END_DIALOG, which is defined on line 0.

The flow of the conversation is contained in arrays or maps of the SpeechCode object. This object contains the line number of the source string, the line number of the target string, and the opcode. When drawing the message, we look up the String from a table using the source key, and when the player clicks the continue part, we look up the new SpeechCode using the target key, and adjust the speaker according to the opcode.

Hopefully this is enough high level documentation for the project. I don’t think I’ll be working on this game again.


Thoughts on my attempted Computer Science club

May 28, 2010

Lately I’ve been quite busy and I’ve been spending less time on blogging as I would have liked. Indeed I’ve found myself with little time for reading books (which I borrow from the library and intend to read but never do so), or even study math problems. As of now I have books on calculus, number theory, geometry, organic chemistry, game programming, as well as a few novels lying on my desk, pretty much collecting dust and soon to be collecting overdue fees.

As the year’s almost over, there’s a certain rush to complete the last few assignments (especially the Language arts portfolio assignments which are given an entire term but everyone procrastinates them until the last two days before the deadline). There’s also a lot of studying for exams, which again most people complain about but do not spend enough time on (this includes me).

Also there has been some controversy over my score in the Euclid contest earlier this year, which I dare not discuss publicly. I’ve got my first relationship which I’m really happy about; dating is fun (but very unproductive and somewhat addicting). Probably involved in too many extracurricular school clubs, so I’m quite busy.

What happened with the Computer Science club

Over the spring break, I had the idea to start a computer science club at my school. I did some planning work and found some teacher support, and held the first meeting on April 16. Six people came to the first meeting. Not really knowing what to do, I talked about a fairly easy computer science problem.

As the club progressed, it changed unpredictably. At certain times there would be a group of experienced programmers, in which we would discuss more difficult (IOI-level) computer science problems; at other times the group would consist more of people with no programming experience in which I would be forced to abandon the more difficult problems in favor of teaching some programming basics. At other times nobody would show up, forcing me to cancel the meeting. The last computer science club meeting was held on May 26.

The club was clearly not working as well as I would have hoped, although it wasn’t a complete failure. It was moderately successful, given the circumstances.

For next year, I’ve heard about a grant for the school of a pretty large sum of money to the robotics department, and my teacher suggested me to add robotics to the club.

What went wrong with the Computer Science club

There are several reasons I think that the computer science club didn’t do as well as I’d hoped. I’ve been involved in the anime club, debate club, and the environment club so I’ll compare the computer science club to other school clubs that I’m familiar with.

  1. The entry barrier is too high. In the computer science club, the most basic requirement would be proficiency with some programming language, or just knowing how to program. As my school offers no computer science courses, few people in the school can program well. Some math skills are also important for computer science, but you’d be okay if you weren’t extremely good at math. However, if you don’t know how to program there would be little point in discussing arrays, searching, data structures, etc. This is probably the biggest problem with the computer science club, and yet I don’t really have a solution for it. In comparison, the entry barrier is much lower for any other school club: even with no debate experience it is still possible to participate in mock debates or speech games; it’s possible to get up to speed in gardening basics in a few minutes for environment club. In contrast learning a programming language takes weeks at minimum.
  2. There is a very high skill discrepancy between members. Being the mostly self-taught activity computer science is, the skill discrepancies between members is very large. One group of people, a smaller group, is the group of people who can program well. A larger group is a group of people who cannot program. There aren’t many people in-between. Thus, depending on which group predominates at a meeting, we discuss difficult computer science problems or we teach programming basics. This is a problem because teaching programming basics would bore those that can already program, and discussing problems would confuse those that could not program. There is no ‘middle ground’ between the two groups like discussing simple computer science problems: that would be unbeneficial to everyone.
  3. There is little dedication in most members. People decide not to come because they have homework, they’re tired or hungry, or they just forget. This is probably a problem for every school club, while the previous two only really applied to the computer science club. So I don’t have much to say about this.
  4. I failed at adequately advertising the club. Although I advertised my club on Facebook and requested club meetings to be announced on the school bulletin and put up a poster, most people in the school probably don’t know the club exists. As of now it’s still considered ‘unofficial’ as neither the principals nor the student council know that the club exists.

Or perhaps there is just not enough interest in computer science in my school, as just five people wrote the CCC in February, and a handful of people show up to write a math contest.

Thoughts on Robotics

Since it’s been suggested that I incorporate robotics into the club in the future, I’d give my thoughts on that here as well.

The robotics club would build robots for competitions (WorldSkills and others which I don’t remember). Quite a lot of money is required for equipment, and this money is available (in comparison to computer science which can be done for free).

My biggest problem with robotics is that robotics has very little to do with computer science. Both involve some degree of programming, but that aside they are completely different. Thus, my knowledge and experience in computer science would be irrelevant for robotics, and there’s no reason I should lead a robotics club. Also because of this, the idea of combining computer science and robotics is absurd.

If there’s going to be a robotics club next year, it’s going to be very different from the computer science club. We’re predicting that a considerable amount of fundraising would be necessary to pay for the competitions. This has mixed outcomes. For one thing, there would be better dedication in members, and individuals would be more motivated to come since so much money is on the line. On the other hand, the entry barrier would be even higher: it would be very difficult if not downright impossible to join the club after it has started.

I still don’t know whether to re-attempt the computer science club next year, or attempt starting a different club, or not attempt to start anything at all.


Follow

Get every new post delivered to your Inbox.

Join 72 other followers