DEEPAK.SURTI
  • Home
  • Blog
  • Mobile Apps
  • Open Source
  • Cool 3D Demos
  • About

Strawberry Fields (ITA Archived Puzzle, Analyzed)

8/19/2011

0 Comments

 
Picture
Please refer to the strawberry fields problem on this page

Analysis

Think of each strawberry as a point on an XY plane. Then we can find out the concave hull which is the smallest polygon that contains all the ponits or strawberries.


Picture
Assume for some given strawberry field, the concave hull is something like this

Picture
Now walk through the vertices of the concave hull in succsession. For each pair of successive vertexes, find the point of intersection that is outside the concave hull. This will now result in an updated polygon as shown.

Picture
Finally pick the largest edge and from the two edges, one of which succeeds the largest edge and the other which precedes it, pick the larger one. Form a rectangle between the largest edge and the selected succeessive or preceding edge. This is depicted here.

Picture
Now choose all points of the concave polygon that lie outside the rectangle that we just derived. Add to this set of points, a point that would have been derived as a result of deriving the rectangle. Repeat the process of forming the rectangle till all points of concave polygon are covered. For the sample, the final result is shown.

Algorithm

The steps of the algorithm are enumerated below.
  • Assuming the lowest row of the starwberry field as the X axis and the left most column as the Y axis, read the starwberries as points on XY plane.
  • Find out the concave hull of the strawberry points.
  • For the largest edge of the concave hull, pair it with the larger of the edge that succeeds or precedes it. Build a rectangle from this pair. Add a point that might have been generated as a part of building the rectangle to the set of points S of the concave hull that lie outside the built rectangle.
  • Repeate the process in the previous step for the set of points S of the concave hull that are yet to be covered till no more points remain.
0 Comments

Your comment will be posted after it is approved.


Leave a Reply.

    Picture

    Me

    I am a 3D graphics software engineer.

    profile for dmsurti at Stack Overflow, Q&A for professional and enthusiast programmers

    Archives

    December 2011
    November 2011
    October 2011
    September 2011
    August 2011
    July 2011
    June 2011
    May 2011
    April 2011
    August 2010
    January 2010
    December 2009
    September 2009
    August 2009

    Categories

    All
    Automator
    Books
    Code
    Continuations
    Css
    Drakma
    Education
    Express Card
    External Drive
    Html
    Ita
    Learning
    Life
    Lisp
    Mac
    Macros
    Mercurial
    Productivity
    Puzzle
    Reading
    Rss
    Simplicity
    Sudoku
    Work

    RSS Feed

    Picture
    me @ delicious
Powered by Create your own unique website with customizable templates.
  • Home
  • Blog
  • Mobile Apps
  • Open Source
  • Cool 3D Demos
  • About