computational-geometry

64 entries in Computational Geometry & Topology.

• Graham scanPolar-angle sortingcanonlegacy lesson ▸computational-geometry
• Andrew's monotone chainX-coordinate sortingcanoncomputational-geometry
• Jarvis marchGift-wrapping selectionstandardcomputational-geometry
• QuickhullFarthest-point partitioningstandardcomputational-geometry
• Chan's algorithmHull-size guessingspecialistcomputational-geometry
• Kirkpatrick-SeidelMarriage-before-conquest pruningspecialistcomputational-geometry
• Incremental 3D convex hullConflict-graph point insertionspecialistcomputational-geometry
• Gift wrapping 3Dstandalonespecialistcomputational-geometry
• Dynamic convex hull trickLower-envelope line insertionstandardcomputational-geometry
• Rotating calipersstandalonestandardcomputational-geometry
• Bentley-OttmannSweep-line event queuestandardcomputational-geometry
• Shamos-HoeySweep-line intersection testspecialistcomputational-geometry
• Fortune's algorithmBeach-line sweepcanoncomputational-geometry
• Bowyer-WatsonBad-triangle cavity retriangulationcanonlegacy lesson ▸computational-geometry
• Delaunay flip algorithmEmpty-circumcircle edge flipsstandardcomputational-geometry
• Divide-and-conquer DelaunayGuibas-Stolfi mergespecialistcomputational-geometry
• Incremental DelaunayRandomized point insertionstandardcomputational-geometry
• Ruppert's algorithmEncroached-segment refinementspecialistcomputational-geometry
• Chew's second algorithmstandalonespecialistcomputational-geometry
• Marching cubesEdge-intersection lookup tablestandardcomputational-geometry
• Marching squaresstandalonestandardcomputational-geometry
• Closest pair sweepStrip-check after sortcanoncomputational-geometry
• Closest pair divide and conquerMidline strip mergestandardlegacy lesson ▸computational-geometry
• Rabin's closest pairRandom grid roundsspecialistcomputational-geometry
• K-d treeMedian-split axis cyclingcanonlegacy lesson ▸computational-geometry
• K-d treeSurface-area heuristic splitsspecialistcomputational-geometry
• Ball treeBounding-sphere partitionstandardcomputational-geometry
• Vantage-point treeDistance-to-vantage splitstandardcomputational-geometry
• Cover treeNested scale levelsspecialistcomputational-geometry
• M-treestandalonespecialistcomputational-geometry
• R-treeMinimal-enlargement insertioncanoncomputational-geometry
• R*-treeForced-reinsertion overflowstandardcomputational-geometry
• R+ treeClipping into disjoint regionsspecialistcomputational-geometry
• Hilbert R-treeHilbert-curve orderingspecialistcomputational-geometry
• Bulk-loading STRSort-tile-recursive packingspecialistcomputational-geometry
• Quadtreestandalonecanoncomputational-geometry
• Octreestandalonecanoncomputational-geometry
• PR quadtreestandalonespecialistcomputational-geometry
• Bounding volume hierarchySurface-area heuristiccanoncomputational-geometry
• Point-in-polygon testRay casting paritycanoncomputational-geometry
• Point-in-polygon testWinding numberstandardcomputational-geometry
• Sutherland-Hodgmanstandalonestandardcomputational-geometry
• Weiler-Athertonstandalonespecialistcomputational-geometry
• Cohen-SutherlandRegion outcodesstandardcomputational-geometry
• Liang-BarskyParametric clip intervalsspecialistcomputational-geometry
• Ear clippingstandalonestandardcomputational-geometry
• Seidel's algorithmTrapezoidal decompositionspecialistcomputational-geometry
• Shoelace formulastandalonecanoncomputational-geometry
• Sweep-line area of unionstandalonespecialistcomputational-geometry
• Welzl's algorithmRandomized incremental basisstandardlegacy lesson ▸computational-geometry
• Ritter's algorithmTwo-pass sphere growthspecialistcomputational-geometry
• GJK algorithmSupport-mapping simplexstandardcomputational-geometry
• EPAExpanding polytope penetrationspecialistcomputational-geometry
• Separating axis theoremstandalonestandardcomputational-geometry
• Douglas-PeuckerMax-deviation recursioncanonlegacy lesson ▸computational-geometry
• Visvalingam-WhyattLeast-area point removalstandardcomputational-geometry
• Imai-Iri algorithmShortest path over tolerant chordsspecialistcomputational-geometry
• Radial distance simplificationDistance-to-last-kept filterspecialistcomputational-geometry
• Bresenham's line algorithmstandalonecanoncomputational-geometry
• Xiaolin Wu's line algorithmCoverage antialiasingspecialistcomputational-geometry
• Midpoint circle algorithmstandalonestandardcomputational-geometry
• De Casteljau's algorithmstandalonestandardcomputational-geometry
• Chaikin's algorithmCorner-cutting subdivisionspecialistcomputational-geometry
• Lloyd's relaxationCentroidal Voronoi iterationstandardcomputational-geometry