Re: [pygame] Polygon Area Calculation?

["Nirav Patel" <olpc@xxxxxxxxxxxxxx>]

Ulf Ekström's bitmask library is actually suprisingly fast for tasks
like counting pixels.  It uses one bit per pixel, so memory usage is
miniscule.  The count function is very clever as well, and doesn't
just iterate through one bit at a time.  It uses a function Donald
Gillies wrote to count ints at a time:

      return (tmp = (n) - (((n) >> 1) & 033333333333) -
	      (((n) >> 2) & 011111111111),
	      tmp = ((tmp + (tmp >> 3)) & 030707070707),
	      tmp =  (tmp + (tmp >> 6)),
	      tmp = (tmp + (tmp >> 12) + (tmp >> 24)) & 077);

In all, it takes a fraction of a millisecond to execute on a 640x480
image on my 433mhz OLPC XO.

You're right though; it is almost certainly faster to use the
trapezoid method for polygons.  I added Mask.count() to Pygame
primarily for computer vision use, where all of the objects are weird
looking.

Nirav

On Mon, Sep 29, 2008 at 5:05 PM, Ron Dippold <sizer@xxxxxxxxxx> wrote:
> That is pretty neat. My gut feeling says the trapezoid method would usually
> be faster, and much lower memory use, but I can see three cases where you'd
> prefer using mask.count():
>
>  - It can handle an infinitely weird polygon set (crossed edges, cutouts,
> etc).
>  - Will give you a 100% exact pixel count if you need it.
>  - It's just so much /cooler/ than iterating over vertexes.
>
> Ron
>
> Nirav Patel wrote:
>>
>> In Pygame SVN, there are new Mask functions.  You could turn the
>> polygon surface into a mask with mask.from_threshold() or
>> mask.from_surface(), and then get the size in pixels with
>> mask.count().
>