DUTCH - Computational Geometry

DUTCH is an implementation of some of the computational geometry routines from the reference.

Reference:

de Berg, van Kreveld, Overmars and Schwarzkopf,
Computational Geometry,
Springer, 2000.

Web site:

http://www.cs.uu.nl/geobook/.

Files you may copy include:

• DUTCH.F90, the source code.
• DUTCH_PRB.F90, a sample problem.
• DUTCH_PRB.OUT, sample problem output.

The list of routines includes:

• ANGLE_DEG_2D returns the angle swept out between two rays in 2D.
• ANGLE_RAD_2D returns the angle swept out between two rays in 2D.
• CIRCLE_DIA2IMP_2D converts a diameter to an implicit circle in 2D.
• CIRCLE_EXP2IMP_2D converts a circle from explicit to implicit form in 2D.
• CIRCLE_IMP_CONTAINS_POINT_2D determines if an implicit circle contains a point in 2D.
• CROSS0_2D finds the cross product of (P1-P0) and (P2-P0) in 2D.
• ENORM0_2D computes the Euclidean norm of (P1-P0) in 2D.
• ENORMSQ0_2D computes the square of the Euclidean norm of (P1-P0) in 2D.
• I_MODP returns the nonnegative remainder of integer division.
• I_RANDOM returns a random integer in a given range.
• I_SWAP swaps two integer values.
• I_WRAP forces an integer to lie between given limits by wrapping.
• IJ_NEXT returns the next matrix index.
• IJ_NEXT_GT returns the next matrix index, with the constraint that I < J.
• IMAT_PRINT prints an integer matrix.
• IVEC_FRAC searches for the K-th smallest element in an N-vector.
• IVEC_HEAP_D reorders an array of integers into an descending heap.
• IVEC_HEAP_D_EXTRACT extracts the maximum value from a descending heap.
• IVEC_HEAP_D_INSERT inserts a new value into a descending heap.
• IVEC_HEAP_D_MAX returns the maximum value in a descending heap of integers.
• IVEC_IDENTITY sets an integer vector to the identity vector A(I)=I.
• IVEC_MEDIAN returns the median of an unsorted integer vector.
• IVEC_POP pops an integer vector off of a stack.
• IVEC_PRINT prints an integer vector.
• IVEC_PUSH pushes an integer vector onto a stack.
• IVEC_REVERSE reverses the elements of an integer vector.
• IVEC_SPLIT_UNSORT "splits" an unsorted vector based on a splitting value.
• LINE_EXP2IMP_2D converts an explicit line to implicit form in 2D.
• LINE_EXP_POINT_DIST_2D: distance ( explicit line, point ) in 2D.
• LINE_EXP_POINT_DIST_SIGNED_2D: signed distance ( explicit line, point ) in 2D.
• LINE_SEG_CONTAINS_POINT_2D reports if a line segment contains a point in 2D.
• LINE_SEG_VEC_INT_2D computes intersections of a set of line segments.
• LINES_EXP_INT_2D determines where two explicit lines intersect in 2D.
• LINES_IMP_INT_2D determines where two implicit lines intersect in 2D.
• LINES_SEG_DIST_2D computes the distance of two line segments in 2D.
• LINES_SEG_INT_1D computes the intersection of two line segments in 1D.
• LINES_SEG_INT_2D computes the intersection of two line segments in 2D.
• PERM_PRINT prints a permutation.
• PERM_RANDOM returns a random permutation.
• PI returns the value of pi.
• POINTS_CONVEX_HULL_CUBIC_2D computes the convex hull of 2D points.
• POINTS_CONVEX_HULL_NLOGH_2D computes the convex hull of 2D points.
• POINTS_CONVEX_HULL_NLOGN_2D computes the convex hull of 2D points.
• POINTS_MINIDISC1_2D finds the smallest circle through Q containing points P.
• POINTS_MINIDISC2_2D finds the smallest circle through Q1 and Q2 containing points P.
• POINTS_MINIDISC_2D finds the smallest circle containing points P.
• POLY_TRIANGULATE_2D returns a triangulation of a polygon.
• POLY_REORDER_NODES reorders nodes of a polygon so node 1 is leftest lowest.
• POLYCON_MINKOWSKI_SUM_LINEAR computes the Minkowski sum of two convex polygons.
• POLYCON_MINKOWSKI_SUM_N2LOGN2 Minkowski sums two convex polygons.
• R_SWAP swaps two real values.
• RADIANS_TO_DEGREES converts an angle from radians to degrees.
• RECT_INT_2D computes the intersection of two rectangles in 2D.
• RMAT_PRINT prints a real matrix.
• RMAT_SOLVE uses Gauss-Jordan elimination to solve an N by N linear system.
• RMAT2_INVERSE inverts a 2 by 2 real matrix using Cramer's rule.
• RVEC2_COMPARE compares pairs of reals stored in two vectors.
• RVEC2_PRINT prints a pair of real vectors.
• RVEC2_SORT_A ascending sorts a vector of pairs of integers.
• RVEC_REVERSE reverses the elements of a real vector.
• SORT_HEAP_EXTERNAL externally sorts a list of items into linear order.
• TIMESTAMP prints the current YMDHMS date as a time stamp.
• TRIANGLE_CONTAINS_POINT_2D finds if a point is inside a triangle in 2D.
• TRIANGULATE_TRICOLOR three-colors the nodes of a triangulated polygon.
• TRIANGULATE_COLOR_PUSH pushes a side of a colored triangle onto the stack.
• TRIANGULATE_COLOR_POP pops a side of a colored triangle from the stack.
• TRIANGULATE_COMMON_EDGE seeks the other triangle that shares an edge.
• TRIANGULATION_BOUNDARY_COUNT returns the number of boundary edges.

Return to the FORTRAN software page.