About Me

My photo
Northglenn, Colorado, United States
I'm primarily a BI Developer on the Microsoft stack. I do sometimes touch upon other Microsoft stacks ( web development, application development, and sql server development).

Tuesday, August 21, 2007

Interview question: What structure would you use to represent shapes in a database?

OK, A few months ago, my friend told me of an interview question that I found interesting. The question that was given to him, paraphrasing: "If you had to set up a database to hold shapes, what would your table structure look like?". The point of the question was for him to convert the concept of a class shape that might be used in an object oriented language to be converted to a database structure. Which is why I was stuck on this question, with no simple straight forward solution.

I then started thinking about this question, again. The idea of the question was to see what tables and columns would you set up to make this feasible. I wanted an easy solution with minimal work, so I avoided the polymorphism concept and went to a simpler definition of a shape (polygon).

I figure I would make 1 table called SHAPE with 2 columns and make the assumption that the shapes are defined as "simple polygons":

ID int, COORDINATES varchar

The ID is obviously the primary key for each shape.

The Coordinates is a order list of Cartesian coordinates going counter-clockwise.

Now, given a shape, the most common questions asked would be what is the perimeter and area of said shape. I could easily make 2 store procedures to find the perimeter and area.

To figure out the perimeter, I just need to add up the distance from each point, simple enough.

To figure out the area of the polygon, I knew there had to be a formula that would do this for me, and thanks to wikipedia I found one:

"The formula was described by Meister in 1769 and by Gauss in 1795. It can be verified by dividing the polygon into triangles".

I was looking around, to see if others seen this question. I did find something similar at http://lists.mysql.com/mysql/207823

If I needed to query the table for certain shapes, then it would be good to add an additional column called: Points int

So, if I needed to query the table for triangles only then I can do a search on points = 3.

No comments: