IMPORTANT: All updated code is in the Java folder, others are out of date, but I leave them as they are for now. Maybe remove then in the future.
I plan to update this Repository as follows:
Add two Convex Hull algorithms: Brute force and Graham's Scan, as well as visualization.Add visualization to Bentley Ottmann's algrithom, that is, Geometric Intersection.Reconstruct the visualization program in the triangluation program, make it aligned to the one taking advantage of normalization in graphics, which is the one other programs use as well.- And there is also a web-based teaching program for the triangulation algorithm, which is more interactive than Java implementation.
Add Point Location ( Trapezoid Map and Search structure ), as well as visualization.- Four Animation algorithms, implemented with three.js;
- DFS in Haskell;
Only support 2-dimensional scenario.
| Description | Entry method |
|---|---|
| toLeft test | boolean toLeft( Vector base1, Vector base2, Vector point ) |
| inCircle test | double inCircle( Vector a, Vector b, Vector c, Vector p ) |
| Description | Entry method\File |
|---|---|
| Graham's Scan | List<Vector> grahamScan( List<Vector> points ) |
| Brute force | List<Vector> slowConvexHull( List<Vector> points ) |
| Program ( including visualization ) | Programming Assignment 1 - Convex Hull |
| Description | Entry method\File |
|---|---|
| Line and line | Vector lineIntersect( Line line1, Line line2 ) |
| Line and Circle | Line lineCircleIntersect( Line line, Circle cycle ) |
| Bentley Ottmann's algrithom( Intersection Of segment, ray, line and Circle ) | List<EventPoint2D> findIntersection( List<IntersectionShape> shapes ) |
| Program ( including visualization ) | CG2017 PA1-2 Crossroad |
| Description | Entry method\File |
|---|---|
| Partionting monotone polygons | List<Face> makeMonotone( List<Vertex> vertices ) |
| Triangulation | List<Face> preprocessMonotonePolygon( List<Face> monotonePolygons ) |
| BFS in a dual graph | void BFS( int sizeOfGraph, DualVertex start, DualVertex end ) |
| Funnel algorithm | List<Vector> Funnel( DualVertex startTriangle, Vector startPoint, Vector endPoint ) |
| Program ( including visualization ) | CG2017 PA2-1 Shortest Path in The Room |
| Description | Entry method\File |
|---|---|
| Build trapezoidal Map and search structure | SearchStructure trapezoidalMap( List<Line> lines, SearchVertex box ) |
| Point Locatoin | public SearchVertex get( Line line ) |
| Program ( including visualization ) | Programming Assignment 3 - Trapezoidal Map and Planar Point Location |
| Problem | Description | Entry File |
|---|---|---|
| Subsequence(ID 3061) | Two approaches, binary search and ruler | Subsequence.java |
| Face The Right Way(ID 3276) | One approach, switch | FaceTheRightWay.java |
| Description | Entry method\File |
|---|---|
| Counting sort | void countingSort( List<NumberRadix> numbers, ... ) |
| Radix sort | List<NumberRadix> radixSort( long[] arr, int radix ) |
| Insertion sort | void insertionSort( List<E> arrayToSort ) |
| Merge sort | List<E> mergeSort( List<E> arrayToSort ) |
| Bucket sort | void bucketSort( List<Double> arrayToSort ) |
| Description | Entry method\File |
|---|---|
| Breath First Search, BFS | void BFS( int sizeOfGraph, Vertex start, Vertex end ) |
| Depth Frist Search, DFS | public int DFS( Vertex vertex, boolean[] visited ) |
| Bellman Ford( Constricted to make only one edge of progress at a given step) | void constrictedBellmanFord( Graph<ShortestVertex> aGraph ... ) |
| Find the max flow in a internet flow | int findMaxFlow( InternetFlowVertex start ) |
| Get all matching from a bipartite matching | public List<List<InternetFlowVertex>> getAllMatching() |
| Description | Entry File |
|---|---|
| Binary Search Tree ( put(), deleteMin(), deleteMax(), delete(), min(), max(), etc.) | BinarySearchTree.java |
| Red Black Tree ( put(), deleteMin(), deleteMax(), delete(), min(), max(), etc. ) | RedBlackTree.java |
| Segment Tree ( Range maximum and minimum Query ) | SegmentTree.java |
| Priority Queue | MyPriorityQueue.java |
| Description | Entry File |
|---|---|
| Graph | Graph.java |
| Strongly connected component, SCC | SCC.java |
| Directed acyclic graph, DAG | DAG.java |
| Minimum spanning tree, MST. | MST.java |
| Union Find | UnionFind.java |
| Internet Flow | InternetFlow.java |
| Bipartite Matching | BipartiteMatching.java |
Only support 2-dimensional scenario.
| Description | Entry File/Package |
|---|---|
| Doubly-connected edge list | DCEL |
| Get all incident edges of the vertex | List<HalfEdge> allIncidentEdges( Vertex vertex ) |
| Walk around all halfEdges, starting at face and get visited vertices | List<Vertex> walkAroundVertex( Face face ) |
| Find the first ClockWise Edge with two vertices destination and origin | HalfEdge firstClockWiseEdge( Vertex destination, Vertex origin ) |
| Find the first CounterClockWise Edge with two vertices destination and origin | HalfEdge firstCounterClockWiseEdge( Vertex origin, Vertex destination ) |
| Description | Entry File/Package |
|---|---|
| Trapezoidal Map | public class Trapezoid |
| Search Structure( Tree-like DAG ) | public class SearchStructure |