HolesCpp module¶

Extension written in C++ intended to help finding sets with few r-holes.

holesCpp.count_convex_rholes(points, r, mono = True)¶

Counts the r-holes in a point set.

This function counts how many convex r-holes are in points (the point set may be colored). It is an implementation of the algorithm presented in “Searching for Empty Convex Polygons” [1]

Parameters:	points : list This list represents the point set, each point is represented as a list of 3 integers: the first two are the coordinates of the point, the third one is the color. The color is optional. r : int The number of sides of the holes we want to fint in the point set. mono : boolean Determines wheter to look for monochromatic r-holes or not.
Returns:	h : int The number of r-holes in points.

Notes

The coordinates of the points should be less than or equal to \(2^{30}\) to prevent overflow on the C++ side.

Examples

The first call counts the empty quadrilaterals, disregarding the color of the points. The second call counts only monochromatic quadrilaterals.

>>> import holesCpp as holes
>>> points=[[0,2,0], [1,0,1], [2,4,0], [4,1,0], [4,3,0]]
>>> holes.count_convex_rholes(points, 4)
5
>>> holes.count_convex_rholes(points, 4, True)
1

holesCpp.report_convex_rholes(points, r, mono = True)¶

Reports the r-holes in a point set.

This function reports how many convex r-holes are in points (the point set may be colored). It is an implementation of the algorithm presented in “Searching for Empty Convex Polygons”

Parameters:	points : list This list represents the point set, each point is represented as a list of 3 integers: the first two are the coordinates of the point, the third one is the color. The color is optional. r : int The number of sides of the holes we want to fint in the point set. mono : boolean Determines wheter to look for monochromatic r-holes or not
Returns:	H : int A list containing the r-holes in points. Each r-hole is repre- sented as a list of points, in counterclockwise order. Each point is stored in the same way explained for the parameter points.

Notes

The coordinates of the points should be less than or equal to 2^30 to prevent overflow on the C++ side.

holesCpp.count_convex_rholes_p(p, points, r, mono = True)¶

Counts the r-holes in a point set with certain point as vertex and the r-gons with only that point inside them.

This function counts how many convex r-holes in points have p as a vertex and how many convex r-gons in points have only p inside them. The point set may be colored. Point p must not be contained in points.

Parameters:

p : list A list with 3 integers, representing a point in the plane. The first two are the coordinates of the point, the third one is the color. The color is optional points : list This list represents the point set, each point is represented in the same way as p. r : int The number of sides of the holes we want to fint in the point set. mono : boolean Determines wheter to look for monochromatic r-holes or not

Returns:

(a, b) : tuple a is the number of convex r-holes in points that have p as a vertex and b the number of convex r-gons in points have only p inside them.

Notes

The coordinates of the points should be less than or equal to 2^30 to prevent overflow on the C++ side. The point p must not be included in points.

holesCpp.countEmptyTriangs()¶

Counts the number of empty triangles in points.