Cumincad : CUMINCAD Papers : Search Results

CumInCAD is a Cumulative Index about publications in Computer Aided Architectural Design
supported by the sibling associations ACADIA, CAADRIA, eCAADe, SIGraDi, ASCAAD and CAAD futures

PDF papers
References

Hits 1 to 2 of 2

Reformat results as: short short into frame detailed detailed into frame

_id	2415
authors	Nievergelt, J. and Preparata, Franco P.
year	1982
title	Plane-Sweep Algorithms for Intersecting Geometric Figures
source	Communications of the ACM. October, 1982. vol. 25: pp. 739-747 : ill. includes bibliography
summary	Algorithms in computational geometry are of increasing importance in computer-aided design, for example, in the layout of integrated circuits. The efficient computation of the intersection of several superimposed figures is a basic problem. Plane figures defined by points connected by straight line segments are considered, for example, polygons (not necessarily simple) and maps (embedded planar graphs). The regions into which the plane is partitioned by these intersecting figures are to be processed in various ways such as listing the boundary of each region in cyclic order or sweeping the interior of each region. Let m be the total number of points of all the figures involved and s be the total number of intersections of all line segments. A two plane-sweep algorithm that solves the problems above is presented; in the general case (non convexity) in time O((n+s)log-n) and space O(n+s); when the regions of each given figure are convex, the same can be achieved in time O(n log n +s) and space O(n)
keywords	computational geometry, algorithms, intersection, mapping, polygons, data structures, analysis
series	CADline
last changed	2003/06/02 10:24

_id	8c27
authors	Kalay, Yehuda E.
year	1982
title	Determining the Spatial Containment of a Point in General Polyhedra
source	Computer graphics and Image Processing. 1982. vol. 19: pp. 303-334 : ill. includes bibliography. See also criticism and improvements in Orlowski, Marian
summary	Determining the inclusion of a point in volume-enclosing polyhedra (shapes) in 3D space is, in principle, the extension of the well-known problem of determining the inclusion of a point in a polygon in 2D space. However, the extra degree of freedom makes 3D point-polyhedron containment analysis much more difficult to solve than the 2D point polygon problem, mainly because of the nonsequential ordering of the shape elements, which requires global shape data to be applied for resolving special cases. Two general O(n) algorithms for solving the problem by reducing the 3D case into the solvable 2D case are presented. The first algorithm, denoted 'the projection method,' is applicable to any planar- faced polyhedron, reducing the dimensionality by employing parallel projection to generate planar images of the shape faces, together with an image of the point being tested for inclusion. The containment relationship of these images is used to increment a global parity-counter when appropriate, representing an abstraction for counting the intersections between the surface of the shape and a halfline extending from the point to infinity. An 'inside' relationship is established when the parity-count is odd. Special cases (coincidence of the halfline with edges or vertices of the shape) are resolved by eliminating the coincidental elements and re-projecting the merged faces. The second algorithm, denoted 'the intersection method,' is applicable to any well- formed shape, including curved-surfaced ones. It reduces the dimensionality by intersecting the polygonal trace of the shape surface at the plane of intersection, which is tested for containing the trace of the point in the plane, directly establishing the overall 3D containment relationship. A particular O(n) implementation of the 2D point-in-polygon inclusion algorithm, which is used for solving the problem once reduced in dimensionality, is also presented. The presentation is complemented by discussions of the problems associated with point-polyhedron relationship determination in general, and comparative analysis of the two particular algorithms presented
keywords	geometric modeling, point inclusion, polygons, polyhedra, computational geometry, algorithms, search, B-rep
series	CADline
email
last changed	2003/06/02 10:24

No more hits.