Introduction to Algorithm Repository

0. Overview

0.1 Implementation details

1. Dictionaries/HashMaps/HashSets may not be the solution we're looking for, so I haven't used Hash Table in the current implementation. We're always exploring an alternative solution that does not rely on the expected O(1) performance of operations involving a hash table. Well, the reason behind this is simply that this is an algorithm-based repository, not project-based one. We're eager for finding a cleverer and more amazing algorithm and data structure to solve the problem.
2. For computational geometry. Java is not that good at visualizing 3D scenario, so I thinking of not using Java when digging into 3D or higher-dimensions scenario. ( but there is indeed a 3D Java library )

0.2 updating plans:

I plan to update this Repository as follows( All updated ):

1. Add two Convex Hull algorithms: Brute force and Graham's Scan, as well as visualization.
2. Add visualization to Bentley Ottmann's algrithom, that is, Geometric Intersection.
3. 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.
4. And there is also a web-based teaching program for the triangulation algorithm, which is more interactive than Java implementation.
5. Add Point Location ( Trapezoid Map and Search structure ), as well as visualization
6. Four Animation algorithms, implemented with three.js;
7. DFS in Haskell;

1. Algorithm

1.1 Computational Geometry

Only support 2-dimensional scenario.

1.1.1 Numerical Tests

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 )

1.1.2 Convex Hull

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

1.1.3 Geometric Intersection

Description	Entry method\File
Line and line	Vector lineIntersect( Line line1, Line line2 )
Line and Circle	Line lineCircleIntersect( Line line, Circle circle )
Bentley Ottmann's algrithom( Intersection Of segment, ray, line and Circle )	List<EventPoint2D> findIntersection( List<IntersectionShape> shapes )
Program ( including visualization )	CG2017 PA1-2 Crossroad

1.1.4 Triangulation

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
Pedagogical Aid Webpage	Pedagogical Aid of Triangulation

1.1.5 Point Location

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

1.2 POJ

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

1.3 Sorting

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 )

1.4 Graph

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 )
DFS in Haskell	dfs :: ( Ix i ) => Graph i -> [ Vertex i ] -> Forest ( Vertex i )
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()

1.5 Animation

1.5.1 keyframing

Description	Entry File/Link
keyframing	KeyFraming
Linear Interpolation	static LinearInterpolation
Spherical Linear Interpolation	static slerp
Animation Program	index.html
Example Video	Bilibili

1.5.2 Collision System

Description	Entry File/Link
Collision Object	CollidingObject
Detect collision and trackback to the point where the first collision happens	static detectCollision
Binary Search to find the point where the first collision happens	static __binarySearchCollision
Find collided objects( brute force )	static __isColliding
Animation Program - Billiards	index.html
Example Video	Bilibili

1.5.3 Motion Capture System

Description	Entry File/Link
Set up Articulated Figures from the Skeleton in three.js	static setupShapes
Animate Hierarchical Models	static orientBone
Animation Program	index.html
Example Video	Bilibili

1.5.4 Particle System

Description	Entry File/Link
Particle System	ParticleSystem
Get random Unit Vector3 bounded by a given Cone.	randomUnitVector3InCone
Animation Program - comet	index.html
Animation Program - Static wall and gravity applied	SaticWall.html
Example Video	Bilibili

2. Data Structure

2.1 Tree

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

2.2 Graph

Description	Entry File
Graph	Graph.java
Graph in Haskell	Graph.hs
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

2.3 Computational Geometry

Only support 2-dimensional scenario.

2.3.1 DCEL

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 )

2.3.2 Point Location

Description	Entry File/Package
Trapezoidal Map	public class Trapezoid
Search Structure( Tree-like DAG )	public class SearchStructure