FW: IANA time zone registration - proposal

Clive D.W. Feather clive at demon.net
Wed Jan 19 09:54:15 UTC 2005


Markus Kuhn said:
> For example, see the section "3.5 Direction of Paths" in
> 
>   Adobe Type 1 Font Format
>   http://partners.adobe.com/public/developer/en/font/T1_SPEC.PDF
> 
> Included polygons must be coded in counter-clockwise direction and
> excluded polygons clockwise.
> 
> In other words, as you draw the boundary of the polygon, "inside" is
> always "left" of the pen direction, and "outside" is always "right".
> Couldn't be simpler.

Actually, there are two common algorithms in use.

Draw a line-segment (needn't be straight, but must avoid any place the
polygon intersects itself) from point P to somewhere at infinity (in
practice, well outside the boundaries of the shape).

(1) P is "inside" if the line-segment crosses the polygon an odd number of
times.

(2) For each crossing, determine whether the polygon is going left-to-right
or right-to-left (when looking along the line-segment from P). P is "inside"
if there are different numbers of crossings of each type.

It looks like Adobe are using the second. However, I suspect the first will
be better in this use.

For an example of the difference, consider the shape:

       +---+
       |   |
   +---+---+---+
   |   | A |   |
   |   +---+---+
   |       |
   +-------+

In algorithm 1, area A is "outside". In algorithm 2, it is "inside".

-- 
Clive D.W. Feather  | Work:  <clive at demon.net>   | Tel:    +44 20 8495 6138
Internet Expert     | Home:  <clive at davros.org>  | Fax:    +44 870 051 9937
Demon Internet      | WWW: http://www.davros.org | Mobile: +44 7973 377646
Thus plc            |                            |



More information about the tz mailing list