Related Research Articles
In geometry, a polyhedron is a solid in three dimensions with flat polygonal faces, straight edges and sharp corners or vertices. The word polyhedron comes from the Classical Greek πολύεδρον, as poly- + -hedron.
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node and explores as far as possible along each branch before backtracking.
This is a glossary of graph theory terms. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by edges.
In 3D computer graphics, shown-surface determination is the process used to determine which surfaces and parts of surfaces are not visible from a certain viewpoint. A hidden-surface determination algorithm is a solution to the visibility problem, which was one of the first major problems in the field of 3D computer graphics. The process of hidden-surface determination is sometimes called hiding, and such an algorithm is sometimes called a hider. The analogue for line rendering is hidden-line removal. Hidden-surface determination is necessary to render an image correctly, so that one may not view features hidden behind the model itself, allowing only the naturally viewable portion of the graphic to be visible.
In computational geometry, the point-in-polygon (PIP) problem asks whether a given point in the plane lies inside, outside, or on the boundary of a polygon. It is a special case of point location problems and finds applications in areas that deal with processing geometrical data, such as computer graphics, computer vision, geographical information systems (GIS), motion planning, and CAD.
In computer science, a graph is an abstract data type that is meant to implement the undirected graph and directed graph concepts from mathematics; specifically, the field of graph theory.
In computational geometry, polygon triangulation is the decomposition of a polygonal area P into a set of triangles, i.e., finding a set of triangles with pairwise non-intersecting interiors whose union is P.
A polygon mesh is a collection of vertices, edges and faces that defines the shape of a polyhedral object in 3D computer graphics and solid modeling. The faces usually consist of triangles, quadrilaterals (quads), or other simple convex polygons (n-gons), since this simplifies rendering, but may also be more generally composed of concave polygons, or even polygons with holes.
In geometry, a simple polygon is a polygon that does not intersect itself and has no holes. That is, it is a flat shape consisting of straight, non-intersecting line segments or "sides" that are joined pairwise to form a single closed path. If the sides intersect then the polygon is not simple. The qualifier "simple" is frequently omitted, with the above definition then being understood to define a polygon in general.
The Weiler–Atherton is a polygon-clipping algorithm. It is used in areas like computer graphics and games development where clipping of polygons is needed. It allows clipping of a subject or candidate polygon by an arbitrarily shaped clipping polygon/area/region.
Clipping, in the context of computer graphics, is a method to selectively enable or disable rendering operations within a defined region of interest. Mathematically, clipping can be described using the terminology of constructive geometry. A rendering algorithm only draws pixels in the intersection between the clip region and the scene model. Lines and surfaces outside the view volume are removed.
In computer graphics, line clipping is the process of removing lines or portions of lines outside an area of interest. Typically, any line or part thereof which is outside of the viewing area is removed.
In mathematics, a normal surface is a surface inside a triangulated 3-manifold that intersects each tetrahedron so that each component of intersection is a triangle or a quad. A triangle cuts off a vertex of the tetrahedron while a quad separates pairs of vertices. A normal surface may have many components of intersection, called normal disks, with one tetrahedron, but no two normal disks can be quads that separate different pairs of vertices since that would lead to the surface self-intersecting.
In computer science, Kosaraju's algorithm is a linear time algorithm to find the strongly connected components of a directed graph. Aho, Hopcroft and Ullman credit it to S. Rao Kosaraju and Micha Sharir. Kosaraju suggested it in 1978 but did not publish it, while Sharir independently discovered it and published it in 1981. It makes use of the fact that the transpose graph has exactly the same strongly connected components as the original graph.
Boolean operations on polygons are a set of Boolean operations operating on one or more sets of polygons in computer graphics. These sets of operations are widely used in computer graphics, CAD, and in EDA.
The Sutherland–Hodgman algorithm is a algorithm used for clipping polygons. It works by extending each line of the convex clip polygon in turn and selecting only vertices from the subject polygon that are on the visible side.
Algorithms that construct convex hulls of various objects have a broad range of applications in mathematics and computer science.
The doubly connected edge list (DCEL), also known as half-edge data structure, is a data structure to represent an embedding of a planar graph in the plane, and polytopes in 3D. This data structure provides efficient manipulation of the topological information associated with the objects in question. It is used in many algorithms of computational geometry to handle polygonal subdivisions of the plane, commonly called planar straight-line graphs (PSLG). For example, a Voronoi diagram is commonly represented by a DCEL inside a bounding box.
The Vatti clipping algorithm is used in computer graphics. It allows clipping of any number of arbitrarily shaped subject polygons by any number of arbitrarily shaped clip polygons. Unlike the Sutherland–Hodgman and Weiler–Atherton polygon clipping algorithms, the Vatti algorithm does not restrict the types of polygons that can be used as subjects or clips. Even complex (self-intersecting) polygons, and polygons with holes can be processed. The algorithm is generally applicable only in 2D space.
Nef polygons and Nef polyhedra are the sets of polygons which can be obtained from a finite set of halfplanes (halfspaces) by Boolean operations of set intersection and set complement. The objects are named after the Swiss mathematician Walter Nef (1919–2013), who introduced them in his 1978 book on polyhedra.
References
- ↑ Greiner, Günther; Kai Hormann (1998). "Efficient clipping of arbitrary polygons". ACM Transactions on Graphics. 17 (2): 71–83. doi:10.1145/274363.274364.
- ↑ Ionel Daniel Stroe. "Efficient Clipping of Arbitrary Polygons" . Retrieved 2014-05-17.
