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 838 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::PointInPolygonWinding::contains(), 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 1200 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 831 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 1210 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::blossom_maximum_cardinality_matching(), 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::blossom_maximum_cardinality_matching().

TEST_F() [3/100]

TEST_F	(	GeomAlgorithmsTest	,
		AndrewMonotonicChainEmptyInput
	)

Definition at line 109 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::blossom_maximum_cardinality_matching(), 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::blossom_maximum_cardinality_matching().

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::blossom_maximum_cardinality_matching().

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::blossom_maximum_cardinality_matching().

TEST_F() [7/100]

TEST_F	(	GeomAlgorithmsTest	,
		ClosestPairEmptyInputThrows
	)

Definition at line 8 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::blossom_maximum_cardinality_matching().

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::blossom_maximum_cardinality_matching().

TEST_F() [9/100]

TEST_F	(	GeomAlgorithmsTest	,
		ConvexDecompTriangle
	)

Definition at line 2223 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [10/100]

TEST_F	(	GeomAlgorithmsTest	,
		ConvexPolygonDistanceGJKInvalidInputThrows
	)

Definition at line 999 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [11/100]

TEST_F	(	GeomAlgorithmsTest	,
		ConvexPolygonDistanceGJKMatchesBruteBaseline
	)

Definition at line 1028 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [12/100]

TEST_F	(	GeomAlgorithmsTest	,
		ConvexPolygonDistanceGJKOverlapping
	)

Definition at line 928 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [13/100]

TEST_F	(	GeomAlgorithmsTest	,
		ConvexPolygonDistanceGJKSeparatedSquares
	)

Definition at line 902 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [14/100]

TEST_F	(	GeomAlgorithmsTest	,
		ConvexPolygonDistanceGJKSymmetry
	)

Definition at line 975 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [15/100]

TEST_F	(	GeomAlgorithmsTest	,
		ConvexPolygonDistanceGJKTouchingEdge
	)

Definition at line 952 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [16/100]

TEST_F	(	GeomAlgorithmsTest	,
		CrossAlgorithmConvexHullCollinearBoundary
	)

Definition at line 1913 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [17/100]

TEST_F	(	GeomAlgorithmsTest	,
		CrossAlgorithmConvexHullLargerSet
	)

Definition at line 1867 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [18/100]

TEST_F	(	GeomAlgorithmsTest	,
		CrossAlgorithmConvexHullSimple
	)

Definition at line 1813 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [19/100]

TEST_F	(	GeomAlgorithmsTest	,
		CrossAlgorithmConvexHullTrianglePoints
	)

Definition at line 1956 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [20/100]

TEST_F	(	GeomAlgorithmsTest	,
		DelaunayAsTrianglesProducesValidTriangles
	)

Definition at line 243 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [21/100]

TEST_F	(	GeomAlgorithmsTest	,
		DelaunayEmptyCircumcircleGridPoints
	)

Definition at line 1273 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [22/100]

TEST_F	(	GeomAlgorithmsTest	,
		DelaunayEmptyCircumcircleProperty
	)

Definition at line 1237 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [23/100]

TEST_F	(	GeomAlgorithmsTest	,
		DelaunayIncrementalBasicSquare
	)

Definition at line 1998 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [24/100]

TEST_F	(	GeomAlgorithmsTest	,
		DelaunayIncrementalCollinear
	)

Definition at line 2079 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [25/100]

TEST_F	(	GeomAlgorithmsTest	,
		DelaunayIncrementalDuplicates
	)

Definition at line 2094 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [26/100]

TEST_F	(	GeomAlgorithmsTest	,
		DelaunayIncrementalEmptyCircumcircle
	)

Definition at line 2014 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [27/100]

TEST_F	(	GeomAlgorithmsTest	,
		DelaunayIncrementalGrid
	)

Definition at line 2110 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [28/100]

TEST_F	(	GeomAlgorithmsTest	,
		DelaunayIncrementalMatchesBowyerWatson
	)

Definition at line 2047 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [29/100]

TEST_F	(	GeomAlgorithmsTest	,
		DelaunayIncrementalSingleTriangle
	)

Definition at line 2070 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::blossom_maximum_cardinality_matching(), and r.

TEST_F() [30/100]

TEST_F	(	GeomAlgorithmsTest	,
		DeterminismClosestPairPermutedInputs
	)

Definition at line 1688 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [31/100]

TEST_F	(	GeomAlgorithmsTest	,
		DeterminismConvexHullPermutedInputs
	)

Definition at line 1659 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [32/100]

TEST_F	(	GeomAlgorithmsTest	,
		DeterminismDelaunayPermutedInputs
	)

Definition at line 1604 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

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::blossom_maximum_cardinality_matching().

TEST_F() [34/100]

TEST_F	(	GeomAlgorithmsTest	,
		GrahamScanEmptyInput
	)

Definition at line 141 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::blossom_maximum_cardinality_matching(), 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::blossom_maximum_cardinality_matching().

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::blossom_maximum_cardinality_matching().

TEST_F() [37/100]

TEST_F	(	GeomAlgorithmsTest	,
		KDTreeBuildBalanced
	)

Definition at line 1118 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [38/100]

TEST_F	(	GeomAlgorithmsTest	,
		KDTreeDebugSnapshotHasPartitions
	)

Definition at line 1169 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [39/100]

TEST_F	(	GeomAlgorithmsTest	,
		KDTreeForEach
	)

Definition at line 1157 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [40/100]

TEST_F	(	GeomAlgorithmsTest	,
		KDTreeInsertAndContains
	)

Definition at line 1077 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [41/100]

TEST_F	(	GeomAlgorithmsTest	,
		KDTreeNearest
	)

Definition at line 1093 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [42/100]

TEST_F	(	GeomAlgorithmsTest	,
		KDTreeNearestEmpty
	)

Definition at line 1110 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [43/100]

TEST_F	(	GeomAlgorithmsTest	,
		KDTreeRange
	)

Definition at line 1139 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [44/100]

TEST_F	(	GeomAlgorithmsTest	,
		MinkowskiSumCWInputsNormalized
	)

Definition at line 728 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [45/100]

TEST_F	(	GeomAlgorithmsTest	,
		MinkowskiSumIsConvex
	)

Definition at line 791 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [46/100]

TEST_F	(	GeomAlgorithmsTest	,
		MinkowskiSumNonConvexThrows
	)

Definition at line 750 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [47/100]

TEST_F	(	GeomAlgorithmsTest	,
		MinkowskiSumOpenPolygonThrows
	)

Definition at line 773 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [48/100]

TEST_F	(	GeomAlgorithmsTest	,
		MinkowskiSumSquareAndTriangle
	)

Definition at line 698 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [49/100]

TEST_F	(	GeomAlgorithmsTest	,
		MinkowskiSumTwoSquares
	)

Definition at line 676 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [50/100]

TEST_F	(	GeomAlgorithmsTest	,
		MonotoneTriangulateCountMatchesCuttingEars
	)

Definition at line 643 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [51/100]

TEST_F	(	GeomAlgorithmsTest	,
		MonotoneTriangulateDegenerateThrows
	)

Definition at line 625 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [52/100]

TEST_F	(	GeomAlgorithmsTest	,
		MonotoneTriangulateHexagon
	)

Definition at line 592 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [53/100]

TEST_F	(	GeomAlgorithmsTest	,
		MonotoneTriangulateOpenThrows
	)

Definition at line 613 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [54/100]

TEST_F	(	GeomAlgorithmsTest	,
		MonotoneTriangulatePentagon
	)

Definition at line 572 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [55/100]

TEST_F	(	GeomAlgorithmsTest	,
		MonotoneTriangulateSquare
	)

Definition at line 534 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [56/100]

TEST_F	(	GeomAlgorithmsTest	,
		MonotoneTriangulateSquareCW
	)

Definition at line 553 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [57/100]

TEST_F	(	GeomAlgorithmsTest	,
		MonotoneTriangulateTriangle
	)

Definition at line 516 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [58/100]

TEST_F	(	GeomAlgorithmsTest	,
		PerformanceClosestPair5KPoints
	)

Definition at line 1735 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [59/100]

TEST_F	(	GeomAlgorithmsTest	,
		PerformanceConvexHull10KPoints
	)

Definition at line 1714 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [60/100]

TEST_F	(	GeomAlgorithmsTest	,
		PerformanceDelaunay500Points
	)

Definition at line 1750 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [61/100]

TEST_F	(	GeomAlgorithmsTest	,
		PerformanceTriangulation100Vertices
	)

Definition at line 1781 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Polygon::add_vertex(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Polygon::close(), Aleph::count(), 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::blossom_maximum_cardinality_matching(), and Aleph::Polygon::close().

TEST_F() [63/100]

TEST_F	(	GeomAlgorithmsTest	,
		RobustnessCocircularPoints
	)

Definition at line 1555 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Array< T >::append(), Aleph::DynList< T >::append(), Aleph::blossom_maximum_cardinality_matching(), 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 1503 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [65/100]

TEST_F	(	GeomAlgorithmsTest	,
		RobustnessNearCollinearConvexHull
	)

Definition at line 1420 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::blossom_maximum_cardinality_matching(), 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 1368 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::Array< T >::append(), Aleph::DynList< T >::append(), Aleph::blossom_maximum_cardinality_matching(), dist2(), 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 1457 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [68/100]

TEST_F	(	GeomAlgorithmsTest	,
		RobustnessNearParallelSegmentsConverging
	)

Definition at line 1474 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [69/100]

TEST_F	(	GeomAlgorithmsTest	,
		RobustnessVerySmallCoordinates
	)

Definition at line 1536 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::DynList< T >::append(), Aleph::blossom_maximum_cardinality_matching(), 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::blossom_maximum_cardinality_matching().

TEST_F() [71/100]

TEST_F	(	GeomAlgorithmsTest	,
		SegmentSegmentIntersectionCollinearOverlap
	)

Definition at line 299 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [72/100]

TEST_F	(	GeomAlgorithmsTest	,
		SegmentSegmentIntersectionCollinearTouchPoint
	)

Definition at line 366 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [73/100]

TEST_F	(	GeomAlgorithmsTest	,
		SegmentSegmentIntersectionDegenerateDisjointPoints
	)

Definition at line 355 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [74/100]

TEST_F	(	GeomAlgorithmsTest	,
		SegmentSegmentIntersectionDegenerateIdenticalPoints
	)

Definition at line 344 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [75/100]

TEST_F	(	GeomAlgorithmsTest	,
		SegmentSegmentIntersectionDegeneratePointOnSegment
	)

Definition at line 333 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [76/100]

TEST_F	(	GeomAlgorithmsTest	,
		SegmentSegmentIntersectionEndpointTouch
	)

Definition at line 288 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [77/100]

TEST_F	(	GeomAlgorithmsTest	,
		SegmentSegmentIntersectionFreeFunction
	)

Definition at line 377 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [78/100]

TEST_F	(	GeomAlgorithmsTest	,
		SegmentSegmentIntersectionNoIntersection
	)

Definition at line 265 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [79/100]

TEST_F	(	GeomAlgorithmsTest	,
		SegmentSegmentIntersectionProperCross
	)

Definition at line 276 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [80/100]

TEST_F	(	GeomAlgorithmsTest	,
		SegmentSegmentIntersectionVerticalOverlap
	)

Definition at line 321 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [81/100]

TEST_F	(	GeomAlgorithmsTest	,
		SweepLineCollinearOverlapping
	)

Definition at line 2241 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [82/100]

TEST_F	(	GeomAlgorithmsTest	,
		SweepLineDegenerateSegmentThrows
	)

Definition at line 485 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [83/100]

TEST_F	(	GeomAlgorithmsTest	,
		SweepLineDisjointSegments
	)

Definition at line 462 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [84/100]

TEST_F	(	GeomAlgorithmsTest	,
		SweepLineFourSegmentsStar
	)

Definition at line 495 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [85/100]

TEST_F	(	GeomAlgorithmsTest	,
		SweepLineManySegmentsAtOnePoint
	)

Definition at line 2258 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [86/100]

TEST_F	(	GeomAlgorithmsTest	,
		SweepLineMultipleIntersections
	)

Definition at line 433 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [87/100]

TEST_F	(	GeomAlgorithmsTest	,
		SweepLineNoSegments
	)

Definition at line 389 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [88/100]

TEST_F	(	GeomAlgorithmsTest	,
		SweepLineParallelNoIntersection
	)

Definition at line 408 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [89/100]

TEST_F	(	GeomAlgorithmsTest	,
		SweepLineSimpleCross
	)

Definition at line 419 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [90/100]

TEST_F	(	GeomAlgorithmsTest	,
		SweepLineSingleSegment
	)

Definition at line 398 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [91/100]

TEST_F	(	GeomAlgorithmsTest	,
		SweepLineStress10K
	)

Definition at line 2302 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [92/100]

TEST_F	(	GeomAlgorithmsTest	,
		SweepLineTShapedIntersection
	)

Definition at line 473 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [93/100]

TEST_F	(	GeomAlgorithmsTest	,
		SweepLineVerticalSegments
	)

Definition at line 2282 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

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::blossom_maximum_cardinality_matching(), and Aleph::Polygon::close().

TEST_F() [95/100]

TEST_F	(	GeomAlgorithmsTest	,
		VoronoiBoundedEdgeSitesAreEquidistantToEndpoints
	)

Definition at line 1335 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [96/100]

TEST_F	(	GeomAlgorithmsTest	,
		VoronoiFortuneClippedCells
	)

Definition at line 2176 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [97/100]

TEST_F	(	GeomAlgorithmsTest	,
		VoronoiFortuneEquidistance
	)

Definition at line 2152 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [98/100]

TEST_F	(	GeomAlgorithmsTest	,
		VoronoiFortuneFourPoints
	)

Definition at line 2141 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

References Aleph::blossom_maximum_cardinality_matching(), and r.

TEST_F() [99/100]

TEST_F	(	GeomAlgorithmsTest	,
		VoronoiFortuneKeepsDualImplementationAvailable
	)

Definition at line 2199 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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

TEST_F() [100/100]

TEST_F	(	GeomAlgorithmsTest	,
		VoronoiVerticesEquidistantToSites
	)

Definition at line 1307 of file geom_algorithms_test_edgecases_sweepline_minkowski_kdtree.cc.

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