Programming Contest: ConvexifyMe

Discussion in 'Java' started by Skybuck Flying, Dec 13, 2010.

  1. Skybuck's ConvexifyMe Programming Contest:

    http://www.skybuck.org/ConvexifyMe/

    Hello everybody,

    Skybuck is back with a new programming contest oh yeah ! ;) :)

    For this programming contest the mission is as follows:

    A bitmap has to be "convexified" which means the following:

    Convex polygons have to be made which describe the boundaries of the red
    pixels of the bitmap.

    The polygons must be convex.

    Further hints:

    Each pixel of the bitmap can be considered a box.

    This means the pixel's coordinate is actually turned into two x coordinates
    0 and 1.

    The pixel shares these coordinates with it's neighbours.

    So a simply polygon for a single pixel would look like:

    (0,0) -----------(1,0)

    | |

    (0,1)-------------(1,1)

    The order of the points can be clock-wise or counter-clock-wise.

    The goal is to keep the number of convex polygons as low as possible.

    The goal is also to keep the number of edges as low as possible.

    I am not yet sure which goal should get priority. Maybe goal1 automatically
    leads to goal2, or perhaps not.

    To get this contest started the same bitmap as the "BoxifyMe" contest will
    be used:

    See website.

    The output and thus the entries for this contest should look as follows:

    X, Y (starting point)

    X, Y

    X, Y

    X, Y

    X, Y (starting point one more time to indicate it's closed.)

    X, Y ( starting point of second polygon )

    X, Y

    X, Y

    X, Y ( starting point of second polygon again to indicate it's closed. )

    Example:

    0,0

    1,0

    0,1

    1,1

    0,0

    Good luck and may the convex polygons have mercy on your soul ! ;)

    Entries can be sent to

    The best entry will become the King of the Contest.

    Will you be sitting in this chair ?

    See website ;) :)

    This is your chance to become a King ! ;) :) Even if it's only for a few
    seconds, minutes or days ! ;) :)

    Hurry up and get that code cracking some output ! ;) :)

    Entries/solutions will be made publicly available for further study and
    analysis to make sure it's valid.

    Overlapping convex polygons are allowed. Though non-overlapping polygon
    entries are also welcomed.

    I will also be entering the contest.

    Goodbye, for now,

    Skybuck.
    Skybuck Flying, Dec 13, 2010
    #1
    1. Advertising

  2. I think it might be possible to describe a simple "pixel" based polygon and
    then later expand it to a boundary polygon, more suited for opengl and
    physics based stuff...

    So I might consider changing the competition a little bit to make it
    possible to simply submit a "pixel based" polygon" instead of a "boundary
    based" polygon.

    However first I would need to make sure that I have a "pixel" to "boundary"
    polygon converter to make sure that this is indeed possible.

    So stay tuned for more details coming in the next days/weeks/months.

    Christmas and New year is coming up so I understand it might be a busy weak
    for some folks out there... with all this family related stuff going on...
    so these contests will run for a long time... maybe even forever...

    I can understand if people enter later on in january or so ;) :)

    Bye,
    Skybuck ;) :)
    Skybuck Flying, Dec 13, 2010
    #2
    1. Advertising

  3. "Skybuck Flying" <> wrote in message
    news:c6b69$4d06ab33$54190f09$1.nb.home.nl...
    >I think it might be possible to describe a simple "pixel" based polygon and
    >then later expand it to a boundary polygon, more suited for opengl and
    >physics based stuff...
    >
    > So I might consider changing the competition a little bit to make it
    > possible to simply submit a "pixel based" polygon" instead of a "boundary
    > based" polygon.
    >
    > However first I would need to make sure that I have a "pixel" to
    > "boundary" polygon converter to make sure that this is indeed possible.
    >
    > So stay tuned for more details coming in the next days/weeks/months.
    >
    > Christmas and New year is coming up so I understand it might be a busy
    > weak for some folks out there... with all this family related stuff going
    > on... so these contests will run for a long time... maybe even forever...
    >
    > I can understand if people enter later on in january or so ;) :)


    If you do want to enter early make sure you state what type the
    input/output/entry is either:

    1. Boundary based.
    2. Pixel based.

    Bye,
    Skybuck.
    Skybuck Flying, Dec 13, 2010
    #3
  4. Hmmm...

    Bitmaps can probably not be converted to convex polygons because as soon as
    a pixel is one line lower it becomes concave lol ?! ;) :)

    So I am thinking about deleting this contest again...

    I will wait one day to see if anybody disgrees and then I will delete it
    again ;) :)

    Bye,
    Skybuck :)
    Skybuck Flying, Dec 14, 2010
    #4
  5. Skybuck Flying

    Thad Smith Guest

    On 12/13/2010 3:50 PM, Skybuck Flying wrote:
    > Skybuck's ConvexifyMe Programming Contest:
    >
    > http://www.skybuck.org/ConvexifyMe/
    >
    > Hello everybody,
    >
    > Skybuck is back with a new programming contest oh yeah ! ;) :)
    >
    > For this programming contest the mission is as follows:
    >
    > A bitmap has to be "convexified" which means the following:
    >
    > Convex polygons have to be made which describe the boundaries of the red
    > pixels of the bitmap.


    Define "the boundaries of the red pixels of the bitmap". Did you mean
    circumscribe or enclose the pixels instead of describe the boundaries?

    > The polygons must be convex.
    >
    > Further hints:
    >
    > Each pixel of the bitmap can be considered a box.
    >
    > This means the pixel's coordinate is actually turned into two x coordinates
    > 0 and 1.


    Huh?

    > The pixel shares these coordinates with it's neighbours.
    >
    > So a simply polygon for a single pixel would look like:
    >
    > (0,0) -----------(1,0)
    >
    > | |
    >
    > (0,1)-------------(1,1)
    >
    > The order of the points can be clock-wise or counter-clock-wise.
    >
    > The goal is to keep the number of convex polygons as low as possible.
    >
    > The goal is also to keep the number of edges as low as possible.
    >
    > I am not yet sure which goal should get priority. Maybe goal1 automatically
    > leads to goal2, or perhaps not.


    If this is the contest, you need to define a single measure (it could be based
    on both attributes, though).

    > To get this contest started the same bitmap as the "BoxifyMe" contest will
    > be used:
    >
    > See website.
    >
    > The output and thus the entries for this contest should look as follows:
    >
    > X, Y (starting point)
    >
    > X, Y
    >
    > X, Y
    >
    > X, Y
    >
    > X, Y (starting point one more time to indicate it's closed.)
    >
    > X, Y ( starting point of second polygon )
    >
    > X, Y
    >
    > X, Y
    >
    > X, Y ( starting point of second polygon again to indicate it's closed. )
    >
    > Example:
    >
    > 0,0
    >
    > 1,0
    >
    > 0,1
    >
    > 1,1
    >
    > 0,0


    That is not a convex figure.

    I recommend focusing on the details of your puzzles before you post.

    --
    Thad
    Thad Smith, Dec 14, 2010
    #5
  6. "Thad Smith" <> wrote in message
    news:4d06de59$0$65842$...
    > On 12/13/2010 3:50 PM, Skybuck Flying wrote:
    >> Skybuck's ConvexifyMe Programming Contest:
    >>
    >> http://www.skybuck.org/ConvexifyMe/
    >>
    >> Hello everybody,
    >>
    >> Skybuck is back with a new programming contest oh yeah ! ;) :)
    >>
    >> For this programming contest the mission is as follows:
    >>
    >> A bitmap has to be "convexified" which means the following:
    >>
    >> Convex polygons have to be made which describe the boundaries of the red
    >> pixels of the bitmap.

    >
    > Define "the boundaries of the red pixels of the bitmap". Did you mean
    > circumscribe or enclose the pixels instead of describe the boundaries?


    Go over/between the edges instead of over the pixels.

    So a pixel coordinate (a single point) changes to a rectangle (four points).

    So in a way the coordinate system gets +1 in vertical and horizontal
    direction:

    ..-----.-----.
    | P | P |
    ..-----.-----.

    .. = boundary coordinates (6 in ascii picture)
    P = pixel coordinates (2 in ascii picture)

    >> The polygons must be convex.
    >>
    >> Further hints:
    >>
    >> Each pixel of the bitmap can be considered a box.
    >>
    >> This means the pixel's coordinate is actually turned into two x
    >> coordinates
    >> 0 and 1.

    >
    > Huh?


    See ascii picture.


    >> The pixel shares these coordinates with it's neighbours.
    >>
    >> So a simply polygon for a single pixel would look like:
    >>
    >> (0,0) -----------(1,0)
    >>
    >> | |
    >>
    >> (0,1)-------------(1,1)
    >>
    >> The order of the points can be clock-wise or counter-clock-wise.
    >>
    >> The goal is to keep the number of convex polygons as low as possible.
    >>
    >> The goal is also to keep the number of edges as low as possible.
    >>
    >> I am not yet sure which goal should get priority. Maybe goal1
    >> automatically
    >> leads to goal2, or perhaps not.

    >
    > If this is the contest, you need to define a single measure (it could be
    > based on both attributes, though).


    Don't know yet which one is better ;)

    >> To get this contest started the same bitmap as the "BoxifyMe" contest
    >> will
    >> be used:
    >>
    >> See website.
    >>
    >> The output and thus the entries for this contest should look as follows:
    >>
    >> X, Y (starting point)
    >>
    >> X, Y
    >>
    >> X, Y
    >>
    >> X, Y
    >>
    >> X, Y (starting point one more time to indicate it's closed.)
    >>
    >> X, Y ( starting point of second polygon )
    >>
    >> X, Y
    >>
    >> X, Y
    >>
    >> X, Y ( starting point of second polygon again to indicate it's closed. )
    >>
    >> Example:
    >>
    >> 0,0
    >>
    >> 1,0
    >>
    >> 0,1
    >>
    >> 1,1
    >>
    >> 0,0

    >
    > That is not a convex figure.


    Ok mistake corrected.

    > I recommend focusing on the details of your puzzles before you post.


    Yeah I'll try to do that next time ! ;) :)

    Bye,
    Skybuck.
    Skybuck Flying, Dec 14, 2010
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Robby Findler

    2005 ICFP Programming Contest

    Robby Findler, May 29, 2005, in forum: Java
    Replies:
    0
    Views:
    377
    Robby Findler
    May 29, 2005
  2. Thaddeus L Olczyk

    Programming Contest--ICFP

    Thaddeus L Olczyk, Jun 23, 2003, in forum: C++
    Replies:
    0
    Views:
    1,283
    Thaddeus L Olczyk
    Jun 23, 2003
  3. Replies:
    0
    Views:
    345
  4. Catherine Chronaki
    Replies:
    0
    Views:
    346
    Catherine Chronaki
    Jan 2, 2004
  5. Skybuck Flying

    Programming Contest: ConvexifyMe

    Skybuck Flying, Dec 13, 2010, in forum: C Programming
    Replies:
    5
    Views:
    267
    Skybuck Flying
    Dec 14, 2010
Loading...

Share This Page