1.4 Geometric primitives

Geometric primitives are the building blocks of computational geometry. They include points, vectors, lines, and shapes like circles and triangles. These basic elements form the foundation for more complex geometric structures and algorithms used in spatial analysis and computer graphics.

Understanding geometric primitives is crucial for solving problems in computational geometry. From representing positions and directions to performing calculations on shapes, these fundamental concepts enable us to manipulate and analyze geometric data efficiently in various applications.

Points and vectors

• Fundamental building blocks in computational geometry form the basis for more complex geometric structures and algorithms
• Essential for representing spatial information and performing geometric calculations in 2D and 3D space
• Provide a mathematical framework for describing positions, directions, and relationships between geometric entities

Representation in 2D and 3D

Top images from around the web for Representation in 2D and 3D

• 

  Ficheiro:Cartesian coordinates 3D.svg – Wikipédia, a enciclopédia livre View original

  Is this image relevant?

• 

  Frames of Reference and Coordinate Systems – Introduction to Geomatics View original

  Is this image relevant?

• 

  Vectors and the Geometry of Space | Boundless Calculus View original

  Is this image relevant?

• 

  Ficheiro:Cartesian coordinates 3D.svg – Wikipédia, a enciclopédia livre View original

  Is this image relevant?

• 

  Frames of Reference and Coordinate Systems – Introduction to Geomatics View original

  Is this image relevant?

1 of 3

Top images from around the web for Representation in 2D and 3D

• 

  Ficheiro:Cartesian coordinates 3D.svg – Wikipédia, a enciclopédia livre View original

  Is this image relevant?

• 

  Frames of Reference and Coordinate Systems – Introduction to Geomatics View original

  Is this image relevant?

• 

  Vectors and the Geometry of Space | Boundless Calculus View original

  Is this image relevant?

• 

  Ficheiro:Cartesian coordinates 3D.svg – Wikipédia, a enciclopédia livre View original

  Is this image relevant?

• 

  Frames of Reference and Coordinate Systems – Introduction to Geomatics View original

  Is this image relevant?

1 of 3

• 2D points represented as ordered pairs $(x, y)$ in Cartesian coordinate system
• 3D points represented as ordered triples $(x, y, z)$ in Cartesian coordinate system
• Vectors defined as directed line segments with magnitude and direction
• 2D vectors represented as $(v_x, v_y)$ or $\vec{v} = (v_x, v_y)$
• 3D vectors represented as $(v_x, v_y, v_z)$ or $\vec{v} = (v_x, v_y, v_z)$

Vector operations

• Addition combines two vectors tip-to-tail resulting in a new vector
• Subtraction finds the difference between two vectors
• Scalar multiplication scales a vector's magnitude by a constant factor
• Vector normalization produces a unit vector with the same direction
• Magnitude calculation determines the length of a vector using the Pythagorean theorem

Dot product and cross product

• Dot product (scalar product) measures similarity between two vectors
  • Calculated as $\vec{a} \cdot \vec{b} = a_x b_x + a_y b_y + a_z b_z$ in 3D
  • Results in a scalar value
  • Used to find angle between vectors and project one vector onto another
• Cross product (vector product) produces a vector perpendicular to both input vectors
  • Calculated as $\vec{a} \times \vec{b} = (a_y b_z - a_z b_y, a_z b_x - a_x b_z, a_x b_y - a_y b_x)$ in 3D
  • Results in a vector perpendicular to the plane containing the input vectors
  • Used to find normal vectors and calculate areas of parallelograms

Lines and line segments

• Fundamental geometric primitives used to represent boundaries, edges, and paths in computational geometry
• Form the basis for more complex shapes and structures in geometric algorithms
• Essential for solving problems related to intersections, distances, and spatial relationships

Equations of lines

• General form of a line equation $Ax + By + C = 0$
• Slope-intercept form $y = mx + b$ where m represents slope and b represents y-intercept
• Point-slope form $(y - y_1) = m(x - x_1)$ using a point $(x_1, y_1)$ on the line and slope m
• Parametric form $(x, y) = (x_0, y_0) + t(dx, dy)$ where $(x_0, y_0)$ represents a point on the line and $(dx, dy)$ represents the direction vector

Intersection of lines

• Solve system of equations to find intersection point of two lines
• Parallel lines have no intersection or infinitely many intersections if coincident
• Perpendicular lines intersect at right angles
• Use determinants or matrix methods for efficient intersection calculations in computational geometry algorithms

Distance from point to line

• Calculate perpendicular distance from a point to a line using the formula: $d = \frac{|Ax_0 + By_0 + C|}{\sqrt{A^2 + B^2}}$
• Where $(x_0, y_0)$ represents the point and $Ax + By + C = 0$ represents the line equation
• Useful for proximity queries and collision detection in geometric algorithms

Planes

• Three-dimensional geometric primitives that extend infinitely in all directions
• Fundamental for representing flat surfaces and dividing 3D space in computational geometry
• Essential for solving problems related to 3D intersections, distances, and spatial relationships

Plane equations

• General form of a plane equation $Ax + By + Cz + D = 0$
• Point-normal form $(x - x_0, y - y_0, z - z_0) \cdot (a, b, c) = 0$ using a point $(x_0, y_0, z_0)$ on the plane and normal vector $(a, b, c)$
• Parametric form $(x, y, z) = (x_0, y_0, z_0) + s(u_x, u_y, u_z) + t(v_x, v_y, v_z)$ where $(x_0, y_0, z_0)$ represents a point on the plane and $\vec{u}$ and $\vec{v}$ are non-parallel vectors in the plane

Normal vectors

• Vectors perpendicular to the plane surface
• Determined by the coefficients of the plane equation $(A, B, C)$
• Used to calculate angles between planes and determine orientation of surfaces
• Essential for lighting calculations and surface normal estimation in computer graphics

Point-plane relationships

• Signed distance from a point to a plane calculated using the formula: $d = \frac{Ax_0 + By_0 + Cz_0 + D}{\sqrt{A^2 + B^2 + C^2}}$
• Positive distance indicates point is on one side of the plane, negative on the other
• Zero distance means the point lies on the plane
• Used for point classification and spatial partitioning in geometric algorithms

Polygons

• Closed planar figures bounded by straight line segments
• Fundamental shapes in computational geometry used to represent complex 2D objects
• Essential for algorithms involving shape analysis, collision detection, and area calculations

Simple vs complex polygons

• Simple polygons have non-intersecting edges and a well-defined interior
• Complex polygons may have self-intersecting edges or multiple interior regions
• Simple polygons classified as convex or concave
• Complex polygons require special handling in geometric algorithms (triangulation)

Convex vs concave polygons

• Convex polygons have all interior angles less than or equal to 180 degrees
• Concave polygons have at least one interior angle greater than 180 degrees
• Convex polygons allow for simpler and more efficient algorithms (convex hull)
• Concave polygons often require decomposition into convex parts for certain operations

Polygon representation

• Vertex list stores coordinates of polygon vertices in order
• Edge list represents polygon as a collection of line segments
• Half-edge data structure efficiently stores topology and adjacency information
• Polygon triangulation decomposes polygon into triangles for easier processing

Circles and spheres

• Fundamental curved geometric primitives in 2D and 3D space
• Essential for representing circular and spherical objects in computational geometry
• Used in various applications including collision detection, distance calculations, and spatial queries

Circle equations

• Standard form $(x - h)^2 + (y - k)^2 = r^2$ where $(h, k)$ represents the center and r represents the radius
• Parametric form $x = h + r \cos(t), y = k + r \sin(t)$ for $0 \leq t < 2\pi$
• General form $Ax^2 + Ay^2 + Dx + Ey + F = 0$ where $A \neq 0$
• Used for intersection tests, containment checks, and arc length calculations

Sphere equations

• Standard form $(x - h)^2 + (y - k)^2 + (z - l)^2 = r^2$ where $(h, k, l)$ represents the center and r represents the radius
• Parametric form $x = h + r \sin(\phi) \cos(\theta), y = k + r \sin(\phi) \sin(\theta), z = l + r \cos(\phi)$ for $0 \leq \phi \leq \pi$ and $0 \leq \theta < 2\pi$
• Used for 3D collision detection, volume calculations, and surface area computations

Tangent lines and planes

• Tangent line to a circle perpendicular to the radius at the point of tangency
• Equation of tangent line to circle at point $(x_1, y_1)$ given by $(x - h)(x_1 - h) + (y - k)(y_1 - k) = r^2$
• Tangent plane to a sphere perpendicular to the radius at the point of tangency
• Equation of tangent plane to sphere at point $(x_1, y_1, z_1)$ given by $(x - h)(x_1 - h) + (y - k)(y_1 - k) + (z - l)(z_1 - l) = r^2$

Triangles

• Simplest polygons with three vertices and three edges
• Fundamental building blocks in computational geometry and computer graphics
• Essential for mesh generation, terrain modeling, and polygon triangulation algorithms

Triangle properties

• Sum of interior angles always equals 180 degrees
• Pythagorean theorem relates side lengths in right triangles $a^2 + b^2 = c^2$
• Law of sines $\frac{a}{\sin A} = \frac{b}{\sin B} = \frac{c}{\sin C}$ relates side lengths to opposite angles
• Law of cosines $c^2 = a^2 + b^2 - 2ab \cos C$ generalizes Pythagorean theorem

Barycentric coordinates

• System for specifying location of a point in a triangle as a weighted sum of vertices
• Any point P in a triangle can be expressed as $P = \alpha A + \beta B + \gamma C$ where $\alpha + \beta + \gamma = 1$
• Barycentric coordinates $(\alpha, \beta, \gamma)$ uniquely determine point's position
• Used for interpolation, point-in-triangle tests, and texture mapping in computer graphics

Area calculation

• Heron's formula $A = \sqrt{s(s-a)(s-b)(s-c)}$ where s is the semi-perimeter
• Cross product method $A = \frac{1}{2}|\vec{AB} \times \vec{AC}|$ using two edge vectors
• Determinant method $A = \frac{1}{2}|x_1(y_2 - y_3) + x_2(y_3 - y_1) + x_3(y_1 - y_2)|$ using vertex coordinates
• Efficient area calculations essential for mesh processing and geometric algorithms

Coordinate systems

• Mathematical frameworks for specifying positions of points in space
• Fundamental to representing and manipulating geometric objects in computational geometry
• Different coordinate systems offer advantages for specific geometric problems and transformations

Cartesian vs polar coordinates

• Cartesian coordinates specify points using perpendicular distance from axes (x, y)
• Polar coordinates specify points using distance from origin (r) and angle from x-axis (θ)
• Conversion formulas between Cartesian and polar:
  • $x = r \cos(\theta), y = r \sin(\theta)$
  • $r = \sqrt{x^2 + y^2}, \theta = \arctan2(y, x)$
• Polar coordinates simplify certain calculations (rotations, spiral curves)

Homogeneous coordinates

• Represent points in projective space using (x, y, w) for 2D or (x, y, z, w) for 3D
• Allow representation of points at infinity when w = 0
• Simplify perspective transformations and projective geometry calculations
• Enable representation of both points and directions in a unified framework

Coordinate transformations

• Translation moves points by adding a constant vector
• Rotation turns points around a fixed center point
• Scaling changes distance of points from a fixed center
• Shear deforms shape by shifting points parallel to an axis
• Affine transformations combine translation, rotation, scaling, and shear
• Projective transformations generalize affine transformations in projective space

Geometric predicates

• Fundamental operations in computational geometry that determine geometric relationships
• Return discrete results (true/false or sign) based on geometric input
• Essential for implementing robust geometric algorithms and data structures

Orientation tests

• Determine relative orientation of three points (collinear, clockwise, counterclockwise)
• Computed using determinant of vectors formed by points
• 2D orientation test: p_x & p_y & 1 \\ q_x & q_y & 1 \\ r_x & r_y & 1 \end{vmatrix}$$
• Used in convex hull algorithms, point-in-polygon tests, and line intersection checks

In-circle and in-sphere tests

• Determine if a point lies inside, on, or outside a circle (2D) or sphere (3D)
• In-circle test computed using determinant of lifted points: a_x & a_y & a_x^2 + a_y^2 & 1 \\ b_x & b_y & b_x^2 + b_y^2 & 1 \\ c_x & c_y & c_x^2 + c_y^2 & 1 \\ d_x & d_y & d_x^2 + d_y^2 & 1 \end{vmatrix}$$
• Essential for Delaunay triangulation and Voronoi diagram construction

Convexity tests

• Determine if a polygon is convex or concave
• Check interior angles or cross products of consecutive edge vectors
• Convexity test for polygon with n vertices: $\text{isConvex} = \forall i \in [0, n-1]: \text{cross}(p_{i+1} - p_i, p_{i+2} - p_{i+1}) \geq 0$
• Used in shape analysis, collision detection, and optimization algorithms

Robustness issues

• Challenges arising from finite precision arithmetic in geometric computations
• Critical for ensuring reliability and correctness of geometric algorithms
• Address discrepancies between continuous geometric theory and discrete computer representations

Floating-point arithmetic

• Limited precision representation of real numbers in computers
• Rounding errors accumulate in geometric calculations leading to inconsistencies
• Special values (infinity, NaN) require careful handling in geometric algorithms
• Catastrophic cancellation occurs when subtracting nearly equal values

Exact geometric computation

• Perform calculations using arbitrary precision arithmetic or rational numbers
• Guarantee exact results for geometric predicates and constructions
• Implementations include CGAL (Computational Geometry Algorithms Library) and LEDA (Library of Efficient Data types and Algorithms)
• Trade-off between robustness and computational efficiency

Epsilon-based comparisons

• Use small tolerance value (epsilon) for floating-point comparisons
• Replace equality checks with approximate equality $|a - b| < \epsilon$
• Choose appropriate epsilon based on problem domain and required precision
• Can lead to inconsistencies if not applied carefully throughout the algorithm

Data structures for primitives

• Efficient organization and storage of geometric primitives
• Enable fast queries, updates, and operations on geometric data
• Essential for implementing complex geometric algorithms and applications

Point sets

• Represent collections of points in 2D or 3D space
• Data structures include arrays, linked lists, and spatial indices (kd-trees, quadtrees)
• Support operations like nearest neighbor search and range queries
• Used in clustering algorithms, spatial databases, and computer vision applications

Line segment arrangements

• Represent collections of line segments and their intersections
• Data structures include doubly-connected edge lists (DCEL) and arrangements
• Support operations like point location and line segment intersection
• Used in motion planning, visibility computations, and map overlay problems

Polygon triangulation

• Decompose polygons into triangles for easier processing
• Data structures include triangle meshes and half-edge data structures
• Algorithms include ear clipping, monotone partitioning, and Delaunay triangulation
• Used in computer graphics, finite element analysis, and terrain modeling