Functions | |
| def | _isPointInPolygon |
| def | _isRightTurn |
| def | _makeRandomData |
| def | _myDet |
| Helpers. | |
| def | convex_hull |
| Public interface. | |
| def | test |
| Test. | |
convexhull.py
Calculate the convex hull of a set of n 2D-points in O(n log n) time.
Taken from Berg et al., Computational Geometry, Springer-Verlag, 1997.
Prints output as EPS file.
When run from the command line it generates a random set of points
inside a square of given length and finds the convex hull for those,
printing the result as an EPS file.
Usage:
convexhull.py <numPoints> <squareLength> <outFile>
Dinu C. Gherman
| def semanticmodel.convexhull._isPointInPolygon | ( | r, | |
| P | |||
| ) | [private] |
Definition at line 53 of file convexhull.py.
| def semanticmodel.convexhull._isRightTurn | ( | p, | |
| q, | |||
| r | |||
| ) | [private] |
Definition at line 42 of file convexhull.py.
| def semanticmodel.convexhull._makeRandomData | ( | numPoints = 10, |
|
sqrLength = 100, |
|||
addCornerPoints = 0 |
|||
| ) | [private] |
Definition at line 65 of file convexhull.py.
| def semanticmodel.convexhull._myDet | ( | p, | |
| q, | |||
| r | |||
| ) | [private] |
Helpers.
Calc. determinant of a special matrix with three 2D points. The sign, "-" or "+", determines the side, right or left, respectivly, on which the point r lies, when measured against a directed vector from p to q.
Definition at line 26 of file convexhull.py.
| def semanticmodel.convexhull.convex_hull | ( | P | ) |
Public interface.
Definition at line 90 of file convexhull.py.
| def semanticmodel.convexhull.test | ( | ) |
Test.
Definition at line 124 of file convexhull.py.