Здравствуйте, Hybernaculum, Вы писали:
H>Есть произвольный 2D многоугольник заданный своими вершинами Xi,Yi. Известно что многоугольник замкнутый и что вершины заданы у него последовательно. Многоугольник может иметь самопересечения, быть невыпуклым и порядок обхода (по часовой или против часовой стрелки) его вершин неизвестен.
H>Нужно найти внешний контур многоугольника.

Вот, что мне ответил Gernot Hoffmann (довольно известный "Zee German" в comp.graphics.algorithms):

Maxim,

this is a well known problem, as described in the
PostScript Language Reference Manual.
Different rules deliver different results e.g. for
the star or the donut, as demonstrated.

One solution is the strict definition of an 'outer
contour', as defined by this algorithm:
1. Find a starting point on the contour which is
   not inside e.g. by searching by a scanline from
   far left (edge of bounding box).
2. Go once around in ccw direction and go always
   to the right at a bifurcation.
This delivers a contour without holes, which can be
treated by any of the standard methods.
Here it's shown for pixels:
http://www.fho-emden.de/~hoffm ann/inside.jpg

It should be possible to apply the strategy to vectors.

Any other strategy would depend on the image content.

Best regards  --Gernot Hoffmann

Для задачи нахождения внешнего контура — вполне подходит. Но у меня задача сложнее — мне нужна именно полная эмуляция правила закраски non-zero в векторном виде.