george@mnetor.UUCP (George Hart) (07/10/87)
Problem: display a filled polygon defined simply a list of (x,y) co-ordinates
defining the vertices of the polygon. The only thing that is known
is that the polygon is closed. Self-intersection (e.g. bowtie) is
a possibility; in fact, there are no bounds on the number of times
it may intersect itself. The polygon may be filled using an
arbitrary pattern.
Speed and the load on the CPU are the keys here. The graphics device
used is programmable to an extent (scratch memory is the primary
limitation). It can be programmed to pattern fill arbitrary triangles.
Does it make sense to try and triangulate the polygon and use the
capabilities of the hardware? I've noticed a reference to a triangulation
algorithm co-authored by Robert Tarjan that works in O(nloglogn) time.
We can use a scanline algorithm but this will be extremely costly
in terms of host time and space, especially with patterned fills.
Any help here would be much appreciated.
--
Regards,
George Hart, Computer X Canada Ltd.
UUCP: utzoo
>!mnetor!george
seismo
BELL: (416)475-8980