Robust free space construction for a polyhedron with planar motion
| Autor: | Victor Milenkovic, Elisha Sacks, Nabeel Butt |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Discrete mathematics
0209 industrial biotechnology Polynomial Plane (geometry) Boundary (topology) Motion (geometry) 020207 software engineering 02 engineering and technology Topology Computer Graphics and Computer-Aided Design Industrial and Manufacturing Engineering Computer Science Applications law.invention Polyhedron 020901 industrial engineering & automation Robustness (computer science) law TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY 0202 electrical engineering electronic engineering information engineering Cartesian coordinate system Configuration space ComputingMethodologies_COMPUTERGRAPHICS Mathematics |
| Zdroj: | Computer-Aided Design. 90:18-26 |
| ISSN: | 0010-4485 |
| DOI: | 10.1016/j.cad.2017.05.017 |
| Popis: | We present a free space construction algorithm for a polyhedron that translates in the x y plane and rotates around its z axis, relative to a stationary polyhedron. We employ the proven paradigm of constructing the configuration space subdivision defined by patches that comprise the configurations where the boundary features of the polyhedra are in contact. We implement the algorithm robustly and efficiently. The challenge is to detect degenerate predicates efficiently and to handle them correctly. We use our ACP (Adaptive Controlled Perturbation) robustness strategy to prevent degenerate predicates due to input in special position. The remaining cases are predicates that are identical to the zero polynomial because their arguments are derived from overlapping sets of input vertices. We detect and handle these cases with custom logic. We validate the implementation by computing maximum clearance paths. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect