Polygon filling algorithm

Polygon filling algorithm.

Authors

Nadezhda Dencheva, Mihai Cara

License

LICENSE

class stsci.skypac.region.Edge(name=None, start=None, stop=None, next=None)

Edge representation

An edge has a “start” and “stop” (x, y) vertices and an entry in the GET table of a polygon. The GET entry is a list of these values:

[ymax, x_at_ymin, delta_x/delta_y]

compute_AET_entry(edge)

Compute the entry for an edge in the current Active Edge Table

[ymax, x_intersect, 1/m] note: currently 1/m is not used

compute_GET_entry()

Compute the entry in the Global Edge Table

[ymax, x@ymin, 1/m]

class stsci.skypac.region.Polygon(rid, vertices, coord_system='Cartesian')

Represents a 2D polygon region with multiple vertices

Parameters

rid: string

polygon id

vertices: list of (x,y) tuples or lists

The list is ordered in such a way that when traversed in a counterclockwise direction, the enclosed area is the polygon. The last vertex must coincide with the first vertex, minimum 4 vertices are needed to define a triangle.

coord_system: string

coordinate system

get_edges()

Create a list of Edge objects from vertices

scan(data)

This is the main function which scans the polygon and creates the mask

Parameters

data: array

the mask array it has all zeros initially, elements within a region are set to the region’s ID

Notes

Algorithm summary:

• Set the Global Edge Table (GET)

• Set y to be the smallest y coordinate that has an entry in GET

• Initialize the Active Edge Table (AET) to be empty

• For each scan line:

  1. Add edges from GET to AET for which ymin==y

  2. Remove edges from AET fro which ymax==y

  3. Compute the intersection of the current scan line with all edges in the AET

  4. Sort on X of intersection point

  5. Set elements between pairs of X in the AET to the Edge’s ID

update_AET(y, AET)

Update the Active Edge Table (AET)

Add edges from GET to AET for which ymin of the edge is equal to the y of the scan line. Remove edges from AET for which ymax of the edge is equal to y of the scan line.

class stsci.skypac.region.Region(rid, coordinate_system)

Base class for regions.

Parameters

rid: int or string

region ID

coordinate_system: astropy.wcs.CoordinateSystem instance or a string

in the context of WCS this would be an instance of wcs.CoordinateSysem

scan(mask)

Sets mask values to region id for all pixels within the region. Subclasses must define this method.

Parameters

mask: ndarray

a byte array with the shape of the observation to be used as a mask

Returns

mask: array where the value of the elements is the region ID or 0 (for

pixels which are not included in any region).