Let P be a simple polygon with n sides. This paper shows how to preprocess the polygon so that, given twoquery points p and g inside P, the length of the shortest path inside the polygon from p to q can be found intim...
详细信息
We present algebraic algorithms to generate the boundary of configuration space obstacles arising from the translatory motion of objects amongst obstacles. In particular we consider obtaining compliant motion pathswhe...
详细信息
While the race towards higher-resolution bitmap displays is still on, many grayscale displays have appeared on the scene. To fully utilize their capabilities, grayscale fonts are needed, and these can be produced by f...
详细信息
ISBN:
(纸本)0897912276
While the race towards higher-resolution bitmap displays is still on, many grayscale displays have appeared on the scene. To fully utilize their capabilities, grayscale fonts are needed, and these can be produced by filtering bi-level masters. Most of the efficient filtering techniques cannot directly be applied. For example, prefiltering is impractical, due to the number of character masters and the requirement of sub-pixel positioning. Furthermore, we would like to impose as few restrictions as possible on the characteristics of the filter, in order to facilitate exploration into the quality of various filters. We describe a fast filtering technique especially adapted to this task. The characters are decomposed into rectangles, and a summed-area representation of the filter is efficiently convolved with each individual rectangle to construct the grayscale character. For a given filter, the number of operations is 0(linear size of the grayscale character), which is optimal. We give an analysis of the efficiency of this technique, and examples of its implementation applied to various families of fonts and point sizes. The performance of the implementation is such that filtering characters for grayscale displays is feasible in realtime on personal workstations.
Let P be a given simple polygon with n sides. The visibility graph of P has an edge between every pair of polygon vertices that can be connected by an open segment in the interior of P. We describe an algorithm that f...
详细信息
作者：
Franklin, Wm. RandolphElectrical
Computer and Systems Engineering Dept. 6026 J.E.C. Rensselaer Polytechnic Institute TroyNY12180 United States
Calculating properties of polyhedra given only the set of the locations and neighborhoods of the verticesis easy. Possible properties include volume, surface area, and point containment testing. No global topological ...
详细信息
This conference proceedings contains 34 papers. The main subjects are computergraphics animation, ray tracing techniques and algorithms, graphics systems surface rendering, curve and surface algorithms, volumetric mo...
详细信息
ISBN:
(纸本)0897912276
This conference proceedings contains 34 papers. The main subjects are computergraphics animation, ray tracing techniques and algorithms, graphics systems surface rendering, curve and surface algorithms, volumetric modeling, computergraphics hardware algorithms, dynamic constraints modeling and simulation, two dimensional graphics algorithms, texturing and shadowing, and lighting models.
This paper summarizes two results in motion planning, the details of which are in two technical *** first establishes an ω[n4) lower bound on moving a ladder (a line segment) in threedimensions in the presence of pol...
详细信息
Given a set of n vertices in the plane together with a set of noncrossing edges, the constrained Delaunay triangulation (CDT) is the triangulation of the vertices with the following properties: (1) the prespecified ed...
详细信息
Algorithms are developed for determining if a set of polyhedral objects in R3 can be intersected by a common transversal (stabbing) line. It can be determined in O (n ) time if a set of n lines in space has a line tra...
We present an O(nlogn) time and 0{n) space algorithm for the following problem in a simple polygon P withn vertices: For each vertex u al P, find another vertex φ(u) that is furthest from u , where the distancebetwee...
详细信息
暂无评论