The heuristic is based on the idea of a convex quadrilateral, which is formed by four points with the lowest and highest x / y coordinates. Any point that lies inside this quadrilateral can not be part of the convex hull and can thus be safely discarded before generating the convex hull itself.
The complexity of the operation is O(n), and may greatly improve the time it takes to construct the convex hull afterwards, depending on the point distribution.
| Access | Constructor and Description |
|---|---|
| private |
| Modifier and Type | Method and Description |
|---|---|
| private static List | Returns: the quadrilateralthe respective points with min/max x/y coordinate points)Build the convex quadrilateral with the found corner points (with min/max x/y coordinates). |
| private static boolean | Returns: true if the point is inside the quadrilateral, false otherwisethe point to check point, final List<Vector2D> the convex quadrilateral, represented by 4 points quadrilateralPoints)Checks if the given point is located within the convex quadrilateral. |
| public static Collection | Returns: a reduced point set, useful as input for convex hull algorithmsthe original point set points)Returns a point set that is reduced by all points for which it is safe to assume that they are not part of the convex hull. |
| AklToussaintHeuristic | back to summary |
|---|---|
| private AklToussaintHeuristic() Hide utility constructor. | |
| buildQuadrilateral | back to summary |
|---|---|
| private static List Build the convex quadrilateral with the found corner points (with min/max x/y coordinates). | |
| insideQuadrilateral | back to summary |
|---|---|
| private static boolean insideQuadrilateral(final Vector2D point, final List<Vector2D> quadrilateralPoints) Checks if the given point is located within the convex quadrilateral. | |
| reducePoints | back to summary |
|---|---|
| public static Collection Returns a point set that is reduced by all points for which it is safe to assume that they are not part of the convex hull.
| |