Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
Functions
geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc File Reference
#include "geom_algorithms_test_common.h"
#include <random>
#include <cmath>
Include dependency graph for geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc:

Go to the source code of this file.

Functions

 TEST_F (GeomAlgorithmsTest, ClosestPairEmptyInputThrows)
 
 TEST_F (GeomAlgorithmsTest, ClosestPairSinglePointThrows)
 
 TEST_F (GeomAlgorithmsTest, ClosestPairAllDuplicates)
 
 TEST_F (GeomAlgorithmsTest, TriangulateTwoVerticesThrows)
 
 TEST_F (GeomAlgorithmsTest, RotatingCalipersOpenSingleVertexThrows)
 
 TEST_F (GeomAlgorithmsTest, PointInPolygonTwoVerticesThrows)
 
 TEST_F (GeomAlgorithmsTest, AndrewMonotonicChainTwoPoints)
 
 TEST_F (GeomAlgorithmsTest, AndrewMonotonicChainEmptyInput)
 
 TEST_F (GeomAlgorithmsTest, AndrewMonotonicChainSinglePoint)
 
 TEST_F (GeomAlgorithmsTest, AndrewMonotonicChainAllDuplicates)
 
 TEST_F (GeomAlgorithmsTest, GrahamScanEmptyInput)
 
 TEST_F (GeomAlgorithmsTest, GrahamScanSinglePoint)
 
 TEST_F (GeomAlgorithmsTest, GrahamScanTwoPoints)
 
 TEST_F (GeomAlgorithmsTest, GrahamScanAllDuplicates)
 
 TEST_F (GeomAlgorithmsTest, AllHullAlgorithmsAgreeOnRandomInput)
 
 TEST_F (GeomAlgorithmsTest, DelaunayAsTrianglesProducesValidTriangles)
 
 TEST_F (GeomAlgorithmsTest, SegmentSegmentIntersectionNoIntersection)
 
 TEST_F (GeomAlgorithmsTest, SegmentSegmentIntersectionProperCross)
 
 TEST_F (GeomAlgorithmsTest, SegmentSegmentIntersectionEndpointTouch)
 
 TEST_F (GeomAlgorithmsTest, SegmentSegmentIntersectionCollinearOverlap)
 
 TEST_F (GeomAlgorithmsTest, SegmentSegmentIntersectionVerticalOverlap)
 
 TEST_F (GeomAlgorithmsTest, SegmentSegmentIntersectionDegeneratePointOnSegment)
 
 TEST_F (GeomAlgorithmsTest, SegmentSegmentIntersectionDegenerateIdenticalPoints)
 
 TEST_F (GeomAlgorithmsTest, SegmentSegmentIntersectionDegenerateDisjointPoints)
 
 TEST_F (GeomAlgorithmsTest, SegmentSegmentIntersectionCollinearTouchPoint)
 
 TEST_F (GeomAlgorithmsTest, SegmentSegmentIntersectionFreeFunction)
 
 TEST_F (GeomAlgorithmsTest, SweepLineNoSegments)
 
 TEST_F (GeomAlgorithmsTest, SweepLineSingleSegment)
 
 TEST_F (GeomAlgorithmsTest, SweepLineParallelNoIntersection)
 
 TEST_F (GeomAlgorithmsTest, SweepLineSimpleCross)
 
 TEST_F (GeomAlgorithmsTest, SweepLineMultipleIntersections)
 
 TEST_F (GeomAlgorithmsTest, SweepLineDisjointSegments)
 
 TEST_F (GeomAlgorithmsTest, SweepLineTShapedIntersection)
 
 TEST_F (GeomAlgorithmsTest, SweepLineDegenerateSegmentThrows)
 
 TEST_F (GeomAlgorithmsTest, SweepLineFourSegmentsStar)
 
 TEST_F (GeomAlgorithmsTest, MonotoneTriangulateTriangle)
 
 TEST_F (GeomAlgorithmsTest, MonotoneTriangulateSquare)
 
 TEST_F (GeomAlgorithmsTest, MonotoneTriangulateSquareCW)
 
 TEST_F (GeomAlgorithmsTest, MonotoneTriangulatePentagon)
 
 TEST_F (GeomAlgorithmsTest, MonotoneTriangulateHexagon)
 
 TEST_F (GeomAlgorithmsTest, MonotoneTriangulateOpenThrows)
 
 TEST_F (GeomAlgorithmsTest, MonotoneTriangulateDegenerateThrows)
 
 TEST_F (GeomAlgorithmsTest, MonotoneTriangulateCountMatchesCuttingEars)
 
 TEST_F (GeomAlgorithmsTest, MinkowskiSumTwoSquares)
 
 TEST_F (GeomAlgorithmsTest, MinkowskiSumSquareAndTriangle)
 
 TEST_F (GeomAlgorithmsTest, MinkowskiSumCWInputsNormalized)
 
 TEST_F (GeomAlgorithmsTest, MinkowskiSumNonConvexThrows)
 
 TEST_F (GeomAlgorithmsTest, MinkowskiSumOpenPolygonThrows)
 
 TEST_F (GeomAlgorithmsTest, MinkowskiSumIsConvex)
 
static Point first_vertex_of (const Polygon &poly)
 
static Geom_Number brute_convex_distance_squared (const Polygon &p, const Polygon &q, Point &out_p, Point &out_q)
 
 TEST_F (GeomAlgorithmsTest, ConvexPolygonDistanceGJKSeparatedSquares)
 
 TEST_F (GeomAlgorithmsTest, ConvexPolygonDistanceGJKOverlapping)
 
 TEST_F (GeomAlgorithmsTest, ConvexPolygonDistanceGJKTouchingEdge)
 
 TEST_F (GeomAlgorithmsTest, ConvexPolygonDistanceGJKSymmetry)
 
 TEST_F (GeomAlgorithmsTest, ConvexPolygonDistanceGJKInvalidInputThrows)
 
 TEST_F (GeomAlgorithmsTest, ConvexPolygonDistanceGJKMatchesBruteBaseline)
 
 TEST_F (GeomAlgorithmsTest, KDTreeInsertAndContains)
 
 TEST_F (GeomAlgorithmsTest, KDTreeNearest)
 
 TEST_F (GeomAlgorithmsTest, KDTreeNearestEmpty)
 
 TEST_F (GeomAlgorithmsTest, KDTreeBuildBalanced)
 
 TEST_F (GeomAlgorithmsTest, KDTreeRange)
 
 TEST_F (GeomAlgorithmsTest, KDTreeForEach)
 
 TEST_F (GeomAlgorithmsTest, KDTreeDebugSnapshotHasPartitions)
 
static Geom_Number dist2 (const Point &a, const Point &b)
 
static Array< Point > sorted_hull_vertices (const Polygon &p)
 
 TEST_F (GeomAlgorithmsTest, DelaunayEmptyCircumcircleProperty)
 
 TEST_F (GeomAlgorithmsTest, DelaunayEmptyCircumcircleGridPoints)
 
 TEST_F (GeomAlgorithmsTest, VoronoiVerticesEquidistantToSites)
 
 TEST_F (GeomAlgorithmsTest, VoronoiBoundedEdgeSitesAreEquidistantToEndpoints)
 
 TEST_F (GeomAlgorithmsTest, RobustnessNearCollinearDelaunay)
 
 TEST_F (GeomAlgorithmsTest, RobustnessNearCollinearConvexHull)
 
 TEST_F (GeomAlgorithmsTest, RobustnessNearParallelSegments)
 
 TEST_F (GeomAlgorithmsTest, RobustnessNearParallelSegmentsConverging)
 
 TEST_F (GeomAlgorithmsTest, RobustnessExtremeCoordinates)
 
 TEST_F (GeomAlgorithmsTest, RobustnessVerySmallCoordinates)
 
 TEST_F (GeomAlgorithmsTest, RobustnessCocircularPoints)
 
 TEST_F (GeomAlgorithmsTest, DeterminismDelaunayPermutedInputs)
 
 TEST_F (GeomAlgorithmsTest, DeterminismConvexHullPermutedInputs)
 
 TEST_F (GeomAlgorithmsTest, DeterminismClosestPairPermutedInputs)
 
 TEST_F (GeomAlgorithmsTest, PerformanceConvexHull10KPoints)
 
 TEST_F (GeomAlgorithmsTest, PerformanceClosestPair5KPoints)
 
 TEST_F (GeomAlgorithmsTest, PerformanceDelaunay500Points)
 
 TEST_F (GeomAlgorithmsTest, PerformanceTriangulation100Vertices)
 
 TEST_F (GeomAlgorithmsTest, CrossAlgorithmConvexHullSimple)
 
 TEST_F (GeomAlgorithmsTest, CrossAlgorithmConvexHullLargerSet)
 
 TEST_F (GeomAlgorithmsTest, CrossAlgorithmConvexHullCollinearBoundary)
 
 TEST_F (GeomAlgorithmsTest, CrossAlgorithmConvexHullTrianglePoints)
 
 TEST_F (GeomAlgorithmsTest, DelaunayIncrementalBasicSquare)
 
 TEST_F (GeomAlgorithmsTest, DelaunayIncrementalEmptyCircumcircle)
 
 TEST_F (GeomAlgorithmsTest, DelaunayIncrementalMatchesBowyerWatson)
 
 TEST_F (GeomAlgorithmsTest, DelaunayIncrementalSingleTriangle)
 
 TEST_F (GeomAlgorithmsTest, DelaunayIncrementalCollinear)
 
 TEST_F (GeomAlgorithmsTest, DelaunayIncrementalDuplicates)
 
 TEST_F (GeomAlgorithmsTest, DelaunayIncrementalGrid)
 
 TEST_F (GeomAlgorithmsTest, VoronoiFortuneFourPoints)
 
 TEST_F (GeomAlgorithmsTest, VoronoiFortuneEquidistance)
 
 TEST_F (GeomAlgorithmsTest, VoronoiFortuneClippedCells)
 
 TEST_F (GeomAlgorithmsTest, VoronoiFortuneKeepsDualImplementationAvailable)
 
 TEST_F (GeomAlgorithmsTest, ConvexDecompTriangle)
 
 TEST_F (GeomAlgorithmsTest, SweepLineCollinearOverlapping)
 
 TEST_F (GeomAlgorithmsTest, SweepLineManySegmentsAtOnePoint)
 
 TEST_F (GeomAlgorithmsTest, SweepLineVerticalSegments)
 
 TEST_F (GeomAlgorithmsTest, SweepLineStress10K)
 

Function Documentation

◆ brute_convex_distance_squared()

static Geom_Number brute_convex_distance_squared ( const Polygon &  p,
const Polygon &  q,
Point &  out_p,
Point &  out_q 
)
static

Definition at line 829 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::PointInPolygonWinding::contains(), Aleph::divide_and_conquer_partition_dp(), Aleph::GeomPolygonUtils::extract_vertices(), first_vertex_of(), Aleph::Polygon::Segment_Iterator::has_curr(), and Aleph::Segment::project().

Referenced by TEST_F().

◆ dist2()

static Geom_Number dist2 ( const Point &  a,
const Point &  b 
)
static

Definition at line 1191 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Point::distance_squared_to().

Referenced by TEST(), TEST(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ first_vertex_of()

static Point first_vertex_of ( const Polygon &  poly)
static

Definition at line 822 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Dlink::Iterator::has_curr().

Referenced by brute_convex_distance_squared().

◆ sorted_hull_vertices()

static Array< Point > sorted_hull_vertices ( const Polygon &  p)
static

Definition at line 1201 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Array< T >::append(), Aleph::Point::get_x(), Aleph::Point::get_y(), Aleph::Dlink::Iterator::has_curr(), and Aleph::quicksort_op().

Referenced by TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ TEST_F() [1/100]

TEST_F ( GeomAlgorithmsTest  ,
AllHullAlgorithmsAgreeOnRandomInput   
)

Definition at line 188 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::DynList< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::Dlink::Iterator::has_curr(), seed, and y.

◆ TEST_F() [2/100]

TEST_F ( GeomAlgorithmsTest  ,
AndrewMonotonicChainAllDuplicates   
)

Definition at line 128 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::DynList< T >::append(), and Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [3/100]

TEST_F ( GeomAlgorithmsTest  ,
AndrewMonotonicChainEmptyInput   
)

Definition at line 109 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::size().

◆ TEST_F() [4/100]

TEST_F ( GeomAlgorithmsTest  ,
AndrewMonotonicChainSinglePoint   
)

Definition at line 117 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::DynList< T >::append(), and Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [5/100]

TEST_F ( GeomAlgorithmsTest  ,
AndrewMonotonicChainTwoPoints   
)

Definition at line 92 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::DynList< T >::append(), and Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [6/100]

TEST_F ( GeomAlgorithmsTest  ,
ClosestPairAllDuplicates   
)

Definition at line 25 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::DynList< T >::append(), and Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [7/100]

TEST_F ( GeomAlgorithmsTest  ,
ClosestPairEmptyInputThrows   
)

Definition at line 8 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [8/100]

TEST_F ( GeomAlgorithmsTest  ,
ClosestPairSinglePointThrows   
)

Definition at line 16 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::DynList< T >::append(), and Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [9/100]

TEST_F ( GeomAlgorithmsTest  ,
ConvexDecompTriangle   
)

Definition at line 2214 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Polygon::add_vertex(), Aleph::Polygon::close(), and Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [10/100]

TEST_F ( GeomAlgorithmsTest  ,
ConvexPolygonDistanceGJKInvalidInputThrows   
)

Definition at line 990 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Polygon::add_vertex(), and Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [11/100]

TEST_F ( GeomAlgorithmsTest  ,
ConvexPolygonDistanceGJKMatchesBruteBaseline   
)

Definition at line 1019 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::DynList< T >::append(), brute_convex_distance_squared(), Aleph::divide_and_conquer_partition_dp(), r, seed, Aleph::Polygon::size(), and y.

◆ TEST_F() [12/100]

TEST_F ( GeomAlgorithmsTest  ,
ConvexPolygonDistanceGJKOverlapping   
)

Definition at line 919 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Polygon::add_vertex(), Aleph::Polygon::close(), Aleph::divide_and_conquer_partition_dp(), and r.

◆ TEST_F() [13/100]

TEST_F ( GeomAlgorithmsTest  ,
ConvexPolygonDistanceGJKSeparatedSquares   
)

Definition at line 893 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Polygon::add_vertex(), Aleph::Polygon::close(), Aleph::divide_and_conquer_partition_dp(), and r.

◆ TEST_F() [14/100]

TEST_F ( GeomAlgorithmsTest  ,
ConvexPolygonDistanceGJKSymmetry   
)

Definition at line 966 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Polygon::add_vertex(), Aleph::Polygon::close(), and Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [15/100]

TEST_F ( GeomAlgorithmsTest  ,
ConvexPolygonDistanceGJKTouchingEdge   
)

Definition at line 943 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Polygon::add_vertex(), Aleph::Polygon::close(), Aleph::divide_and_conquer_partition_dp(), and r.

◆ TEST_F() [16/100]

TEST_F ( GeomAlgorithmsTest  ,
CrossAlgorithmConvexHullCollinearBoundary   
)

Definition at line 1904 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::DynList< T >::append(), Aleph::divide_and_conquer_partition_dp(), and sorted_hull_vertices().

◆ TEST_F() [17/100]

TEST_F ( GeomAlgorithmsTest  ,
CrossAlgorithmConvexHullLargerSet   
)

Definition at line 1858 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::DynList< T >::append(), Aleph::divide_and_conquer_partition_dp(), sorted_hull_vertices(), and y.

◆ TEST_F() [18/100]

TEST_F ( GeomAlgorithmsTest  ,
CrossAlgorithmConvexHullSimple   
)

Definition at line 1804 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::DynList< T >::append(), Aleph::divide_and_conquer_partition_dp(), and sorted_hull_vertices().

◆ TEST_F() [19/100]

TEST_F ( GeomAlgorithmsTest  ,
CrossAlgorithmConvexHullTrianglePoints   
)

Definition at line 1947 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::DynList< T >::append(), Aleph::divide_and_conquer_partition_dp(), and sorted_hull_vertices().

◆ TEST_F() [20/100]

TEST_F ( GeomAlgorithmsTest  ,
DelaunayAsTrianglesProducesValidTriangles   
)

Definition at line 234 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::DelaunayTriangulationBowyerWatson::as_triangles(), Aleph::count(), Aleph::divide_and_conquer_partition_dp(), Aleph::HTList::Iterator::has_curr(), and r.

◆ TEST_F() [21/100]

TEST_F ( GeomAlgorithmsTest  ,
DelaunayEmptyCircumcircleGridPoints   
)

Definition at line 1264 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::DynList< T >::append(), dist2(), Aleph::divide_and_conquer_partition_dp(), r, and y.

◆ TEST_F() [22/100]

TEST_F ( GeomAlgorithmsTest  ,
DelaunayEmptyCircumcircleProperty   
)

Definition at line 1228 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References dist2(), Aleph::divide_and_conquer_partition_dp(), and r.

◆ TEST_F() [23/100]

TEST_F ( GeomAlgorithmsTest  ,
DelaunayIncrementalBasicSquare   
)

Definition at line 1989 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::DynList< T >::append(), Aleph::divide_and_conquer_partition_dp(), and r.

◆ TEST_F() [24/100]

TEST_F ( GeomAlgorithmsTest  ,
DelaunayIncrementalCollinear   
)

Definition at line 2070 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::DynList< T >::append(), Aleph::divide_and_conquer_partition_dp(), and r.

◆ TEST_F() [25/100]

TEST_F ( GeomAlgorithmsTest  ,
DelaunayIncrementalDuplicates   
)

Definition at line 2085 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::DynList< T >::append(), Aleph::divide_and_conquer_partition_dp(), and r.

◆ TEST_F() [26/100]

TEST_F ( GeomAlgorithmsTest  ,
DelaunayIncrementalEmptyCircumcircle   
)

Definition at line 2005 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::DynList< T >::append(), dist2(), Aleph::divide_and_conquer_partition_dp(), and r.

◆ TEST_F() [27/100]

TEST_F ( GeomAlgorithmsTest  ,
DelaunayIncrementalGrid   
)

Definition at line 2101 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::DynList< T >::append(), dist2(), Aleph::divide_and_conquer_partition_dp(), r, and y.

◆ TEST_F() [28/100]

TEST_F ( GeomAlgorithmsTest  ,
DelaunayIncrementalMatchesBowyerWatson   
)

Definition at line 2038 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::DynList< T >::append(), and Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [29/100]

TEST_F ( GeomAlgorithmsTest  ,
DelaunayIncrementalSingleTriangle   
)

Definition at line 2061 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::divide_and_conquer_partition_dp(), and r.

◆ TEST_F() [30/100]

TEST_F ( GeomAlgorithmsTest  ,
DeterminismClosestPairPermutedInputs   
)

Definition at line 1679 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::DynList< T >::append(), and Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [31/100]

TEST_F ( GeomAlgorithmsTest  ,
DeterminismConvexHullPermutedInputs   
)

Definition at line 1650 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::DynList< T >::append(), Aleph::divide_and_conquer_partition_dp(), and sorted_hull_vertices().

◆ TEST_F() [32/100]

TEST_F ( GeomAlgorithmsTest  ,
DeterminismDelaunayPermutedInputs   
)

Definition at line 1595 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::DynList< T >::append(), and Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [33/100]

TEST_F ( GeomAlgorithmsTest  ,
GrahamScanAllDuplicates   
)

Definition at line 173 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::DynList< T >::append(), and Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [34/100]

TEST_F ( GeomAlgorithmsTest  ,
GrahamScanEmptyInput   
)

Definition at line 141 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::size().

◆ TEST_F() [35/100]

TEST_F ( GeomAlgorithmsTest  ,
GrahamScanSinglePoint   
)

Definition at line 149 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::DynList< T >::append(), and Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [36/100]

TEST_F ( GeomAlgorithmsTest  ,
GrahamScanTwoPoints   
)

Definition at line 159 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::DynList< T >::append(), and Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [37/100]

TEST_F ( GeomAlgorithmsTest  ,
KDTreeBuildBalanced   
)

Definition at line 1109 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Array< T >::append(), Aleph::KDTreePointSearch::build(), Aleph::divide_and_conquer_partition_dp(), and y.

◆ TEST_F() [38/100]

TEST_F ( GeomAlgorithmsTest  ,
KDTreeDebugSnapshotHasPartitions   
)

Definition at line 1160 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [39/100]

TEST_F ( GeomAlgorithmsTest  ,
KDTreeForEach   
)

Definition at line 1148 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [40/100]

TEST_F ( GeomAlgorithmsTest  ,
KDTreeInsertAndContains   
)

Definition at line 1068 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [41/100]

TEST_F ( GeomAlgorithmsTest  ,
KDTreeNearest   
)

Definition at line 1084 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [42/100]

TEST_F ( GeomAlgorithmsTest  ,
KDTreeNearestEmpty   
)

Definition at line 1101 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [43/100]

TEST_F ( GeomAlgorithmsTest  ,
KDTreeRange   
)

Definition at line 1130 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::count(), Aleph::divide_and_conquer_partition_dp(), and Aleph::HTList::Iterator::has_curr().

◆ TEST_F() [44/100]

TEST_F ( GeomAlgorithmsTest  ,
MinkowskiSumCWInputsNormalized   
)

Definition at line 719 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Polygon::add_vertex(), Aleph::divide_and_conquer_partition_dp(), Aleph::Polygon::is_closed(), and Aleph::Polygon::size().

◆ TEST_F() [45/100]

TEST_F ( GeomAlgorithmsTest  ,
MinkowskiSumIsConvex   
)

Definition at line 782 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Polygon::add_vertex(), Aleph::Array< T >::append(), Aleph::area_of_parallelogram(), Aleph::Polygon::close(), Aleph::divide_and_conquer_partition_dp(), Aleph::Dlink::Iterator::has_curr(), Aleph::Polygon::is_closed(), and Aleph::Polygon::size().

◆ TEST_F() [46/100]

TEST_F ( GeomAlgorithmsTest  ,
MinkowskiSumNonConvexThrows   
)

Definition at line 741 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Polygon::add_vertex(), and Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [47/100]

TEST_F ( GeomAlgorithmsTest  ,
MinkowskiSumOpenPolygonThrows   
)

Definition at line 764 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Polygon::add_vertex(), Aleph::Polygon::close(), and Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [48/100]

TEST_F ( GeomAlgorithmsTest  ,
MinkowskiSumSquareAndTriangle   
)

Definition at line 689 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Polygon::add_vertex(), Aleph::Polygon::close(), Aleph::divide_and_conquer_partition_dp(), Aleph::Polygon::is_closed(), and Aleph::Polygon::size().

◆ TEST_F() [49/100]

TEST_F ( GeomAlgorithmsTest  ,
MinkowskiSumTwoSquares   
)

Definition at line 667 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Polygon::add_vertex(), Aleph::Polygon::close(), Aleph::divide_and_conquer_partition_dp(), Aleph::Polygon::is_closed(), and Aleph::Polygon::size().

◆ TEST_F() [50/100]

TEST_F ( GeomAlgorithmsTest  ,
MonotoneTriangulateCountMatchesCuttingEars   
)

Definition at line 634 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Polygon::add_vertex(), Aleph::Polygon::close(), Aleph::divide_and_conquer_partition_dp(), and Aleph::HTList::Iterator::has_curr().

◆ TEST_F() [51/100]

TEST_F ( GeomAlgorithmsTest  ,
MonotoneTriangulateDegenerateThrows   
)

Definition at line 616 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Polygon::add_vertex(), Aleph::Polygon::close(), and Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [52/100]

TEST_F ( GeomAlgorithmsTest  ,
MonotoneTriangulateHexagon   
)

Definition at line 583 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Polygon::add_vertex(), Aleph::Polygon::close(), Aleph::count(), Aleph::divide_and_conquer_partition_dp(), and Aleph::HTList::Iterator::has_curr().

◆ TEST_F() [53/100]

TEST_F ( GeomAlgorithmsTest  ,
MonotoneTriangulateOpenThrows   
)

Definition at line 604 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Polygon::add_vertex(), and Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [54/100]

TEST_F ( GeomAlgorithmsTest  ,
MonotoneTriangulatePentagon   
)

Definition at line 563 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Polygon::add_vertex(), Aleph::Polygon::close(), Aleph::count(), Aleph::divide_and_conquer_partition_dp(), and Aleph::HTList::Iterator::has_curr().

◆ TEST_F() [55/100]

TEST_F ( GeomAlgorithmsTest  ,
MonotoneTriangulateSquare   
)

Definition at line 525 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Polygon::add_vertex(), Aleph::Polygon::close(), Aleph::count(), Aleph::divide_and_conquer_partition_dp(), and Aleph::HTList::Iterator::has_curr().

◆ TEST_F() [56/100]

TEST_F ( GeomAlgorithmsTest  ,
MonotoneTriangulateSquareCW   
)

Definition at line 544 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Polygon::add_vertex(), Aleph::Polygon::close(), Aleph::count(), Aleph::divide_and_conquer_partition_dp(), and Aleph::HTList::Iterator::has_curr().

◆ TEST_F() [57/100]

TEST_F ( GeomAlgorithmsTest  ,
MonotoneTriangulateTriangle   
)

Definition at line 507 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Polygon::add_vertex(), Aleph::Polygon::close(), Aleph::count(), Aleph::divide_and_conquer_partition_dp(), and Aleph::HTList::Iterator::has_curr().

◆ TEST_F() [58/100]

TEST_F ( GeomAlgorithmsTest  ,
PerformanceClosestPair5KPoints   
)

Definition at line 1726 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::DynList< T >::append(), Aleph::divide_and_conquer_partition_dp(), r, and y.

◆ TEST_F() [59/100]

TEST_F ( GeomAlgorithmsTest  ,
PerformanceConvexHull10KPoints   
)

Definition at line 1705 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::DynList< T >::append(), Aleph::divide_and_conquer_partition_dp(), and y.

◆ TEST_F() [60/100]

TEST_F ( GeomAlgorithmsTest  ,
PerformanceDelaunay500Points   
)

Definition at line 1741 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::DynList< T >::append(), dist2(), Aleph::divide_and_conquer_partition_dp(), r, and y.

◆ TEST_F() [61/100]

TEST_F ( GeomAlgorithmsTest  ,
PerformanceTriangulation100Vertices   
)

Definition at line 1772 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Polygon::add_vertex(), Aleph::Polygon::close(), Aleph::count(), Aleph::divide_and_conquer_partition_dp(), Aleph::HTList::Iterator::has_curr(), and Aleph::Polygon::size().

◆ TEST_F() [62/100]

TEST_F ( GeomAlgorithmsTest  ,
PointInPolygonTwoVerticesThrows   
)

Definition at line 75 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Polygon::add_vertex(), Aleph::Polygon::close(), and Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [63/100]

TEST_F ( GeomAlgorithmsTest  ,
RobustnessCocircularPoints   
)

Definition at line 1546 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Array< T >::append(), Aleph::DynList< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::TestVisual::emit_case_svg(), Aleph::HTList::Iterator::has_curr(), Aleph::TestVisual::SvgScene::points, and r.

◆ TEST_F() [64/100]

TEST_F ( GeomAlgorithmsTest  ,
RobustnessExtremeCoordinates   
)

Definition at line 1494 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::DynList< T >::append(), dist2(), Aleph::divide_and_conquer_partition_dp(), and r.

◆ TEST_F() [65/100]

TEST_F ( GeomAlgorithmsTest  ,
RobustnessNearCollinearConvexHull   
)

Definition at line 1411 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::TestVisual::add_polygon_vertices(), Aleph::Array< T >::append(), Aleph::DynList< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::TestVisual::emit_case_svg(), Aleph::HTList::Iterator::has_curr(), and Aleph::TestVisual::SvgScene::points.

◆ TEST_F() [66/100]

TEST_F ( GeomAlgorithmsTest  ,
RobustnessNearCollinearDelaunay   
)

Definition at line 1359 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Array< T >::append(), Aleph::DynList< T >::append(), dist2(), Aleph::divide_and_conquer_partition_dp(), Aleph::TestVisual::emit_case_svg(), Aleph::HTList::Iterator::has_curr(), Aleph::TestVisual::SvgScene::points, and r.

◆ TEST_F() [67/100]

TEST_F ( GeomAlgorithmsTest  ,
RobustnessNearParallelSegments   
)

Definition at line 1448 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Array< T >::append(), and Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [68/100]

TEST_F ( GeomAlgorithmsTest  ,
RobustnessNearParallelSegmentsConverging   
)

Definition at line 1465 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::TestVisual::emit_case_svg(), and Aleph::TestVisual::SvgScene::segments.

◆ TEST_F() [69/100]

TEST_F ( GeomAlgorithmsTest  ,
RobustnessVerySmallCoordinates   
)

Definition at line 1527 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::DynList< T >::append(), Aleph::divide_and_conquer_partition_dp(), and r.

◆ TEST_F() [70/100]

TEST_F ( GeomAlgorithmsTest  ,
RotatingCalipersOpenSingleVertexThrows   
)

Definition at line 61 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Polygon::add_vertex(), and Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [71/100]

TEST_F ( GeomAlgorithmsTest  ,
SegmentSegmentIntersectionCollinearOverlap   
)

Definition at line 290 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::TestVisual::emit_case_svg(), and Aleph::TestVisual::SvgScene::segments.

◆ TEST_F() [72/100]

TEST_F ( GeomAlgorithmsTest  ,
SegmentSegmentIntersectionCollinearTouchPoint   
)

Definition at line 357 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [73/100]

TEST_F ( GeomAlgorithmsTest  ,
SegmentSegmentIntersectionDegenerateDisjointPoints   
)

Definition at line 346 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [74/100]

TEST_F ( GeomAlgorithmsTest  ,
SegmentSegmentIntersectionDegenerateIdenticalPoints   
)

Definition at line 335 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [75/100]

TEST_F ( GeomAlgorithmsTest  ,
SegmentSegmentIntersectionDegeneratePointOnSegment   
)

Definition at line 324 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [76/100]

TEST_F ( GeomAlgorithmsTest  ,
SegmentSegmentIntersectionEndpointTouch   
)

Definition at line 279 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [77/100]

TEST_F ( GeomAlgorithmsTest  ,
SegmentSegmentIntersectionFreeFunction   
)

Definition at line 368 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::segment_segment_intersection().

◆ TEST_F() [78/100]

TEST_F ( GeomAlgorithmsTest  ,
SegmentSegmentIntersectionNoIntersection   
)

Definition at line 256 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [79/100]

TEST_F ( GeomAlgorithmsTest  ,
SegmentSegmentIntersectionProperCross   
)

Definition at line 267 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [80/100]

TEST_F ( GeomAlgorithmsTest  ,
SegmentSegmentIntersectionVerticalOverlap   
)

Definition at line 312 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [81/100]

TEST_F ( GeomAlgorithmsTest  ,
SweepLineCollinearOverlapping   
)

Definition at line 2232 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Array< T >::append(), and Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [82/100]

TEST_F ( GeomAlgorithmsTest  ,
SweepLineDegenerateSegmentThrows   
)

Definition at line 476 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Array< T >::append(), and Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [83/100]

TEST_F ( GeomAlgorithmsTest  ,
SweepLineDisjointSegments   
)

Definition at line 453 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Array< T >::append(), and Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [84/100]

TEST_F ( GeomAlgorithmsTest  ,
SweepLineFourSegmentsStar   
)

Definition at line 486 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Array< T >::append(), and Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [85/100]

TEST_F ( GeomAlgorithmsTest  ,
SweepLineManySegmentsAtOnePoint   
)

Definition at line 2249 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References cos(), Aleph::divide_and_conquer_partition_dp(), N, and sin().

◆ TEST_F() [86/100]

TEST_F ( GeomAlgorithmsTest  ,
SweepLineMultipleIntersections   
)

Definition at line 424 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::TestVisual::emit_case_svg(), and Aleph::TestVisual::SvgScene::segments.

◆ TEST_F() [87/100]

TEST_F ( GeomAlgorithmsTest  ,
SweepLineNoSegments   
)

Definition at line 380 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [88/100]

TEST_F ( GeomAlgorithmsTest  ,
SweepLineParallelNoIntersection   
)

Definition at line 399 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Array< T >::append(), and Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [89/100]

TEST_F ( GeomAlgorithmsTest  ,
SweepLineSimpleCross   
)

Definition at line 410 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Array< T >::append(), and Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [90/100]

TEST_F ( GeomAlgorithmsTest  ,
SweepLineSingleSegment   
)

Definition at line 389 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Array< T >::append(), and Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [91/100]

TEST_F ( GeomAlgorithmsTest  ,
SweepLineStress10K   
)

Definition at line 2293 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::and, check(), Aleph::divide_and_conquer_partition_dp(), N, rng, and y.

◆ TEST_F() [92/100]

TEST_F ( GeomAlgorithmsTest  ,
SweepLineTShapedIntersection   
)

Definition at line 464 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Array< T >::append(), and Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [93/100]

TEST_F ( GeomAlgorithmsTest  ,
SweepLineVerticalSegments   
)

Definition at line 2273 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Array< T >::append(), and Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [94/100]

TEST_F ( GeomAlgorithmsTest  ,
TriangulateTwoVerticesThrows   
)

Definition at line 44 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Polygon::add_vertex(), Aleph::Polygon::close(), and Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [95/100]

TEST_F ( GeomAlgorithmsTest  ,
VoronoiBoundedEdgeSitesAreEquidistantToEndpoints   
)

Definition at line 1326 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References dist2(), Aleph::divide_and_conquer_partition_dp(), and r.

◆ TEST_F() [96/100]

TEST_F ( GeomAlgorithmsTest  ,
VoronoiFortuneClippedCells   
)

Definition at line 2167 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Polygon::add_vertex(), Aleph::DynList< T >::append(), Aleph::VoronoiDiagramFortune::clipped_cells(), and Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [97/100]

TEST_F ( GeomAlgorithmsTest  ,
VoronoiFortuneEquidistance   
)

Definition at line 2143 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::DynList< T >::append(), dist2(), Aleph::divide_and_conquer_partition_dp(), and r.

◆ TEST_F() [98/100]

TEST_F ( GeomAlgorithmsTest  ,
VoronoiFortuneFourPoints   
)

Definition at line 2132 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::divide_and_conquer_partition_dp(), and r.

◆ TEST_F() [99/100]

TEST_F ( GeomAlgorithmsTest  ,
VoronoiFortuneKeepsDualImplementationAvailable   
)

Definition at line 2190 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::DynList< T >::append(), and Aleph::divide_and_conquer_partition_dp().

◆ TEST_F() [100/100]

TEST_F ( GeomAlgorithmsTest  ,
VoronoiVerticesEquidistantToSites   
)

Definition at line 1298 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References dist2(), and Aleph::divide_and_conquer_partition_dp().