A problem with connected points and determining geometry figures based on points' location analysis

Question

In school we have a really hard problem, and still no one from the students has solved it yet. Take a look at the picture below:

http://d.imagehost.org/0422/mreza.gif

That's a kind of a network of connected points, which doesn't end and each point has its own number representing it. Let say the numbers are like this: 1-23-456-78910-etc. etc.. (You can't see the number 5 or 8,9... on the picture but they are there and their position is obvious, the point in middle of 4 and 6 is 5 and so on).

1 is connected to 2 and 3, 2 is connected to 1,3,5 and 4 etc.

The numbers 1-2-3 indicate they represent a triangle on the picture, but the numbers 1-4-6 do not because 4 is not directly connected with 6.

Let's look at 2-3-4-5, that's a parallelogram (you know why), but 4-6-7-9 is NOT a parallelogram because the in this problem there's a rule which says all the sides must be equal for all the figures - triangles and parallelograms.

Also there are hexagons, for ex. 4-5-7-9-13-12 is a hexagon - all sides must be equal here too.

12345 - that doesn't represent anything, so we ignore it.

I think i explained the problem well. The actual problem which is given to us by using an input of numbers like above to determine if that's a triangle/parallelogram/hexagon(according to the described rules).

For ex:

1 2 3 - triangle
11 13 24 26 -parallelogram
1 2 3 4 5 - nothing
11 23 13 25 - nothing
3 2 5 - triangle

I was reading computational geometry in order to solve this, but i gave up quickly, nothing seems to help here. One friend told me this site so i decided to give it a try.

If you have any ideas about how to solve this, please reply, you can use pseudo code or c++ whatever. Thank you very much.

Answer 1

Let's order the points like this:

1
2  3
4  5  6
7  8  9  10
11 12 13 14 15
16 17 18 19 20 21
22 23 24 25 26 27 28

You can store this in a matrix. Now let row[i] = the row number i is on and col[i] = the column number i is on. These can be computed more or less efficiently for each i.

First, sort your given numbers ascendingly. You will need exactly 3 points for a triangle, 4 for a parallelogram and 6 for a hexagon - anything else and you can dismiss it as no-figure.

Notice that we can only have right-angled triangles in this matrix, according to your rules. Label the three points A, B, C. You can check if these form a triangle by iterating from row[A] to row[B], then from col[B] to col[C] and then diagonally from row[C] to row[A] and checking to see if the distances are the same and if you get to the right positions. You can terminate this early, for example if B is 8 and A is 1, then you can tell you won't find it once you hit 11 on column 1.

For parallelograms a similar reasoning can be made. Label the 4 points A, B, C, D and remember to sort them ascendingly (remember, your points here are actually numbers). See if you can get from col[A] to col[B] on the same line, then from col[C] to col[D] on the same line and then diagonally or vertically-down from row[A] to row[C] and then (in the same direction you went the previous diagonal!) from row[B] to row[D].

Hexagons are also have a specific format you must test for. Here's how hexagons look like in this representation:

1
2 3
4 5 6
7 8 9 10
11 12 13 14 15
16 17 18 19 20 21
22 23 24 25 26 27 28

1
2 3
4 5 6
7 8 9 10
11 12 13 14 15
16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31 32 33 34 35 36

You can notice that every two pairs of points share the same column, and that the horizontal distance between the two middle points is twice the vertical distance between any two points and also twice the horizontal distance between any other two points.

You will also want to consider rotations, so you'll need to do more tests for each case.

You don't even really need the row and col arrays unless you plan on computing them efficiently. Just walk over your matrix until you identify the first point in sorted order and try to get to the others while following each of the rules.

Not exactly a nice way, but you will only need a 256x256 matrix for this, so while this does result in quite a lot of code, it's pretty efficient. I hope I made myself clear, if not please say what isn't clear. Anyway, maybe someone else will post a better solution, so wait a while longer if you can..