#include <geometry/shape_poly_set.h>
#include <geometry/shape_line_chain.h>
#include <geometry/polygon_triangulation.h>
#include <trigo.h>
#include <thread>
#include <chrono>
#include <future>
#include <filesystem>
#include <fstream>
#include <qa_utils/geometry/geometry.h>
#include <qa_utils/numeric.h>
#include <qa_utils/wx_utils/unit_test_utils.h>
#include "geom_test_utils.h"

Classes
struct	POLYGON_TRIANGULATION_TEST_ACCESS

class	TRIANGULATION_TEST_FIXTURE

Functions
SHAPE_LINE_CHAIN	createSquare (int size=100, VECTOR2I offset=VECTOR2I(0, 0))

SHAPE_LINE_CHAIN	createTriangle (int size=100, VECTOR2I offset=VECTOR2I(0, 0))

SHAPE_LINE_CHAIN	createConcavePolygon (int size=100)

SHAPE_LINE_CHAIN	createSerpentinePolygon (int step=20000, int teeth=16)

bool	validateTriangulation (const SHAPE_POLY_SET::TRIANGULATED_POLYGON &result, const SHAPE_LINE_CHAIN &original, bool strict=true)

int	countSpikeyTriangles (const SHAPE_POLY_SET::TRIANGULATED_POLYGON &aResult)

bool	parsePolyFileForTest (const fs::path &aPath, std::vector< SHAPE_POLY_SET > &aZones)

double	computeBoardSpikeyRatio (const fs::path &aPath)

	BOOST_AUTO_TEST_CASE (BasicTriangleTriangulation)

	BOOST_AUTO_TEST_CASE (BasicSquareTriangulation)

	BOOST_AUTO_TEST_CASE (SplitFirstFracturePartitionProducesMultipleLeaves)

	BOOST_AUTO_TEST_CASE (EarLookaheadImprovesBadTriangulationCase)

	BOOST_AUTO_TEST_CASE (ConcavePolygonTriangulation)

	BOOST_AUTO_TEST_CASE (HintDataOptimization)

	BOOST_AUTO_TEST_CASE (HintDataOptimizationWithSimplifiedInput)

	BOOST_AUTO_TEST_CASE (HintDataInvalidation)

	BOOST_AUTO_TEST_CASE (DegeneratePolygons)

	BOOST_AUTO_TEST_CASE (ZeroAreaPolygon)

	BOOST_AUTO_TEST_CASE (MemoryManagement)

	BOOST_AUTO_TEST_CASE (LargePolygonStressTest)

	BOOST_AUTO_TEST_CASE (ConcurrentTriangulation)

	BOOST_AUTO_TEST_CASE (SelfIntersectingPolygon)

	BOOST_AUTO_TEST_CASE (Issue18083_SelfIntersectingPolygonArea)
	Test case for GitLab issue #18083: Self-intersecting filled shape is not completely filled.

	BOOST_AUTO_TEST_CASE (NearlyCollinearVertices)

	BOOST_AUTO_TEST_CASE (DuplicateVertices)

	BOOST_AUTO_TEST_CASE (ExtremeCoordinates)

	BOOST_AUTO_TEST_CASE (ErrorRecoveryAndCleanup)

	BOOST_AUTO_TEST_CASE (TriangulatedPolygonInterface)

	BOOST_AUTO_TEST_CASE (SourceOutlineIndexTracking)

	BOOST_AUTO_TEST_CASE (PerformanceRegression)

	BOOST_AUTO_TEST_CASE (ParallelPartitionTriangulation)
	Verify that the parallel partition triangulation path produces correct results by registering a task submitter that uses std::async and triangulating a polygon large enough to trigger balanced partitioning (>50K vertices produces 4 leaves).

Function Documentation

◆ BOOST_AUTO_TEST_CASE() [1/23]

BOOST_AUTO_TEST_CASE ( BasicSquareTriangulation )

Definition at line 279 of file test_poly_triangulation.cpp.

References BOOST_TEST(), createSquare(), TRIANGULATION_TEST_FIXTURE::CreateTriangulator(), TRIANGULATION_TEST_FIXTURE::GetResult(), SHAPE_POLY_SET::TRIANGULATED_POLYGON::GetTriangleCount(), SHAPE_POLY_SET::TRIANGULATED_POLYGON::GetVertexCount(), square(), and validateTriangulation().

◆ BOOST_AUTO_TEST_CASE() [2/23]

BOOST_AUTO_TEST_CASE ( BasicTriangleTriangulation )

Definition at line 264 of file test_poly_triangulation.cpp.

References BOOST_TEST(), createTriangle(), TRIANGULATION_TEST_FIXTURE::CreateTriangulator(), TRIANGULATION_TEST_FIXTURE::GetResult(), SHAPE_POLY_SET::TRIANGULATED_POLYGON::GetTriangleCount(), SHAPE_POLY_SET::TRIANGULATED_POLYGON::GetVertexCount(), and validateTriangulation().

◆ BOOST_AUTO_TEST_CASE() [3/23]

BOOST_AUTO_TEST_CASE ( ConcavePolygonTriangulation )

Definition at line 318 of file test_poly_triangulation.cpp.

References std::abs(), SHAPE_LINE_CHAIN::Area(), BOOST_TEST(), SHAPE_LINE_CHAIN::CPoint(), createConcavePolygon(), TRIANGULATION_TEST_FIXTURE::CreateTriangulator(), TRIANGULATION_TEST_FIXTURE::GetResult(), SHAPE_LINE_CHAIN::PointCount(), result, totalArea, validateTriangulation(), VECTOR2< T >::x, and VECTOR2< T >::y.

◆ BOOST_AUTO_TEST_CASE() [4/23]

BOOST_AUTO_TEST_CASE ( ConcurrentTriangulation )

Definition at line 585 of file test_poly_triangulation.cpp.

References BOOST_TEST(), createSquare(), TRIANGULATION_TEST_FIXTURE::CreateTriangulator(), TRIANGULATION_TEST_FIXTURE::GetResult(), and validateTriangulation().

◆ BOOST_AUTO_TEST_CASE() [5/23]

BOOST_AUTO_TEST_CASE ( DegeneratePolygons )

Definition at line 483 of file test_poly_triangulation.cpp.

References SHAPE_LINE_CHAIN::Append(), BOOST_TEST(), TRIANGULATION_TEST_FIXTURE::CreateTriangulator(), empty(), and SHAPE_LINE_CHAIN::SetClosed().

◆ BOOST_AUTO_TEST_CASE() [6/23]

BOOST_AUTO_TEST_CASE ( DuplicateVertices )

Definition at line 723 of file test_poly_triangulation.cpp.

References BOOST_TEST(), TRIANGULATION_TEST_FIXTURE::CreateTriangulator(), duplicate, TRIANGULATION_TEST_FIXTURE::GetResult(), and validateTriangulation().

◆ BOOST_AUTO_TEST_CASE() [7/23]

BOOST_AUTO_TEST_CASE ( EarLookaheadImprovesBadTriangulationCase )

Definition at line 309 of file test_poly_triangulation.cpp.

References BOOST_TEST(), and computeBoardSpikeyRatio().

◆ BOOST_AUTO_TEST_CASE() [8/23]

BOOST_AUTO_TEST_CASE ( ErrorRecoveryAndCleanup )

Definition at line 773 of file test_poly_triangulation.cpp.

References BOOST_TEST(), createSquare(), createTriangle(), TRIANGULATION_TEST_FIXTURE::CreateTriangulator(), TRIANGULATION_TEST_FIXTURE::GetResult(), and SHAPE_POLY_SET::TRIANGULATED_POLYGON::GetTriangleCount().

◆ BOOST_AUTO_TEST_CASE() [9/23]

BOOST_AUTO_TEST_CASE ( ExtremeCoordinates )

Definition at line 749 of file test_poly_triangulation.cpp.

References SHAPE_LINE_CHAIN::Append(), BOOST_TEST(), TRIANGULATION_TEST_FIXTURE::CreateTriangulator(), TRIANGULATION_TEST_FIXTURE::GetResult(), SHAPE_LINE_CHAIN::SetClosed(), and validateTriangulation().

◆ BOOST_AUTO_TEST_CASE() [10/23]

BOOST_AUTO_TEST_CASE ( HintDataInvalidation )

Definition at line 464 of file test_poly_triangulation.cpp.

References BOOST_TEST(), createSquare(), createTriangle(), TRIANGULATION_TEST_FIXTURE::CreateTriangulator(), TRIANGULATION_TEST_FIXTURE::GetResult(), square(), and validateTriangulation().

◆ BOOST_AUTO_TEST_CASE() [11/23]

BOOST_AUTO_TEST_CASE ( HintDataOptimization )

Definition at line 406 of file test_poly_triangulation.cpp.

References BOOST_TEST(), createSquare(), TRIANGULATION_TEST_FIXTURE::CreateTriangulator(), TRIANGULATION_TEST_FIXTURE::GetResult(), SHAPE_POLY_SET::TRIANGULATED_POLYGON::GetTriangleCount(), SHAPE_POLY_SET::TRIANGULATED_POLYGON::GetVertexCount(), and square().

◆ BOOST_AUTO_TEST_CASE() [12/23]

BOOST_AUTO_TEST_CASE ( HintDataOptimizationWithSimplifiedInput )

Definition at line 428 of file test_poly_triangulation.cpp.

References SHAPE_LINE_CHAIN::Append(), BOOST_TEST(), TRIANGULATION_TEST_FIXTURE::CreateTriangulator(), TRIANGULATION_TEST_FIXTURE::GetResult(), SHAPE_POLY_SET::TRIANGULATED_POLYGON::GetTriangleCount(), SHAPE_LINE_CHAIN::SetClosed(), SHAPE_POLY_SET::TRIANGULATED_POLYGON::SetTriangles(), and SHAPE_POLY_SET::TRIANGULATED_POLYGON::Triangles().

◆ BOOST_AUTO_TEST_CASE() [13/23]

BOOST_AUTO_TEST_CASE ( Issue18083_SelfIntersectingPolygonArea )

Test case for GitLab issue #18083: Self-intersecting filled shape is not completely filled.

A self-touching polygon where one vertex lies on a non-adjacent edge creates a "pinch point". The polygon appears to form a figure-8 shape that should be fully filled on both sides.

The polygon from the issue has points: (165,87), (179,87), (174,94), (169,87), (167,94) where vertex (169,87) lies on the segment from (165,87) to (179,87).

This test verifies that the triangulation correctly fills both regions of the self-touching polygon by checking that the total triangulated area equals the sum of both triangular lobes.

Definition at line 656 of file test_poly_triangulation.cpp.

References std::abs(), SHAPE_POLY_SET::AddOutline(), SHAPE_LINE_CHAIN::Append(), BOOST_TEST(), SHAPE_POLY_SET::CacheTriangulation(), SHAPE_POLY_SET::IsSelfIntersecting(), SHAPE_POLY_SET::IsTriangulationUpToDate(), SHAPE_LINE_CHAIN::SetClosed(), SHAPE_POLY_SET::TriangulatedPolyCount(), and SHAPE_POLY_SET::TriangulatedPolygon().

◆ BOOST_AUTO_TEST_CASE() [14/23]

BOOST_AUTO_TEST_CASE ( LargePolygonStressTest )

Definition at line 548 of file test_poly_triangulation.cpp.

References SHAPE_LINE_CHAIN::Append(), BOOST_TEST(), TRIANGULATION_TEST_FIXTURE::CreateTriangulator(), end, TRIANGULATION_TEST_FIXTURE::GetResult(), SHAPE_POLY_SET::TRIANGULATED_POLYGON::GetTriangleCount(), M_PI, radius, SHAPE_LINE_CHAIN::SetClosed(), and validateTriangulation().

◆ BOOST_AUTO_TEST_CASE() [15/23]

BOOST_AUTO_TEST_CASE ( MemoryManagement )

Definition at line 532 of file test_poly_triangulation.cpp.

References BOOST_TEST(), createSquare(), TRIANGULATION_TEST_FIXTURE::CreateTriangulator(), TRIANGULATION_TEST_FIXTURE::GetResult(), and validateTriangulation().

◆ BOOST_AUTO_TEST_CASE() [16/23]

BOOST_AUTO_TEST_CASE ( NearlyCollinearVertices )

Definition at line 700 of file test_poly_triangulation.cpp.

References SHAPE_LINE_CHAIN::Append(), BOOST_TEST(), TRIANGULATION_TEST_FIXTURE::CreateTriangulator(), TRIANGULATION_TEST_FIXTURE::GetResult(), SHAPE_LINE_CHAIN::SetClosed(), and validateTriangulation().

◆ BOOST_AUTO_TEST_CASE() [17/23]

BOOST_AUTO_TEST_CASE ( ParallelPartitionTriangulation )

Verify that the parallel partition triangulation path produces correct results by registering a task submitter that uses std::async and triangulating a polygon large enough to trigger balanced partitioning (>50K vertices produces 4 leaves).

Definition at line 908 of file test_poly_triangulation.cpp.

References std::abs(), SHAPE_POLY_SET::AddOutline(), SHAPE_LINE_CHAIN::Append(), SHAPE_LINE_CHAIN::Area(), BOOST_TEST(), SHAPE_POLY_SET::CacheTriangulation(), SHAPE_POLY_SET::IsTriangulationUpToDate(), M_PI, radius, SHAPE_LINE_CHAIN::SetClosed(), SHAPE_POLY_SET::TriangulatedPolyCount(), and SHAPE_POLY_SET::TriangulatedPolygon().