An Algorithm for Determining the Intersection of Two Simple Polyhedra

dc.contributor.authorSzilvasi-Nagy, M.en_US
dc.date.accessioned2014-07-31T09:05:16Z
dc.date.available2014-07-31T09:05:16Z
dc.date.issued1984en_US
dc.description.abstractAn algorithm is presented for the construction of the intersection of two simple possibly non-convex polyhedra. The methods of descriptive geometry are applied, so that this three-dimensional problem can be solved in two dimensions.We have to find all intersections of the edges of each polyhedron with the faces of the other, and these points of intersection can be found in Monge’s model. Projecting both polyhedra on the xy and on the xz coordinate planes we obtain two superimposed maps in both projections. The algorithm to find the intersection of two maps is based upon the Shamos-Hoey, the Bentley-Ottmann and the Nievergelt-Preparata algorithms. The asymptotic time requirement for determining the polygon of intersection of two polyhedra is O((N + S)log N), where N is the sum of the numbers of vertices of the two polyhedra and S is the total number of intersections of all projected edges in the xy-plane (S = O(N2)).en_US
dc.description.number3en_US
dc.description.seriesinformationComputer Graphics Forumen_US
dc.description.volume3en_US
dc.identifier.doi10.1111/j.1467-8659.1984.tb00071.xen_US
dc.identifier.issn1467-8659en_US
dc.identifier.pages219-225en_US
dc.identifier.urihttps://doi.org/10.1111/j.1467-8659.1984.tb00071.xen_US
dc.publisherBlackwell Publishing Ltd and the Eurographics Associationen_US
dc.titleAn Algorithm for Determining the Intersection of Two Simple Polyhedraen_US
Files
Collections