Velocity Reviews > Java > Programming Contest: ConvexifyMe

# Programming Contest: ConvexifyMe

Skybuck Flying
Guest
Posts: n/a

 12-13-2010
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 http://www.velocityreviews.com/forums/(E-Mail Removed)

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
Guest
Posts: n/a

 12-13-2010
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
Guest
Posts: n/a

 12-13-2010

"Skybuck Flying" <(E-Mail Removed)> wrote in message
news:c6b69\$4d06ab33\$54190f09\$(E-Mail Removed)1.n b.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
Guest
Posts: n/a

 12-14-2010
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

Guest
Posts: n/a

 12-14-2010
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.

--

Skybuck Flying
Guest
Posts: n/a

 12-14-2010
"Thad Smith" <(E-Mail Removed)> wrote in message
news:4d06de59\$0\$65842\$(E-Mail Removed) anews.com...
> 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.