Drawing Nice Projections of Objects in Space
Identifieur interne : 002138 ( Main/Exploration ); précédent : 002137; suivant : 002139Drawing Nice Projections of Objects in Space
Auteurs : Prosenjit Bose [Canada] ; Francisco G Mez [Espagne] ; Pedro Ramos [Espagne] ; Godfried Toussaint [Canada]Source :
- Journal of Visual Communication and Image Representation [ 1047-3203 ] ; 1999.
Abstract
Given a polygonal object (simple polygon, geometric graph, wire-frame, skeleton or more generally a set of line segments) in three-dimensional Euclidean space, we consider the problem of computing a variety of “nice” parallel (orthographic) projections of the object. We show that given a general polygonal object consisting ofnline segments in space, deciding whether it admits acrossing-freeprojection can be done inO(n2logn+k) time andO(n2+k) space, wherekis the number of edge intersections of forbidden quadrilaterals (i.e., a set of directions that admits a crossing) and varies from zero toO(n4). This implies for example that, given a simple polygon in 3-space, we can determine if there exists a plane on which the projection is a simple polygon, within the same complexity. Furthermore, if such a projection does not exist, aminimum-crossingprojection can be found inO(n4) time and space. We show that an object always admits a regular projection (of interest to knot theory) and that such a projection can be obtained inO(n2) time and space or inO(n3) time and linear space. A description of the set of all directions which yield regular projections can be computed inO(n3logn+k) time, wherekis the number of intersections of a set of quadratic arcs on the direction sphere and varies fromO(n3) toO(n6). Finally, when the objects are polygons and trees in space, we considermonotonicprojections, i.e., projections such that every path from the root of the tree to every leaf is monotonic in a common direction on the projection plane. We solve a variety of such problems. For example, given a polygonal chainP, we can determine inO(n) time ifPis monotonic on the projection plane, and inO(nlogn) time we can findallthe viewing directions with respect to whichPis monotonic. In addition, inO(n2) time, we can determine all directions with respect to which a given tree or simple polygon is monotonic.
Url:
DOI: 10.1006/jvci.1999.0415
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001A39
- to stream Istex, to step Curation: 001922
- to stream Istex, to step Checkpoint: 000D88
- to stream Main, to step Merge: 002492
- to stream Main, to step Curation: 002138
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Drawing Nice Projections of Objects in Space</title><author><name sortKey="Bose, Prosenjit" sort="Bose, Prosenjit" uniqKey="Bose P" first="Prosenjit" last="Bose">Prosenjit Bose</name></author><author><name sortKey="G Mez, Francisco" sort="G Mez, Francisco" uniqKey="G Mez F" first="Francisco" last="G Mez">Francisco G Mez</name></author><author><name sortKey="Ramos, Pedro" sort="Ramos, Pedro" uniqKey="Ramos P" first="Pedro" last="Ramos">Pedro Ramos</name></author><author><name sortKey="Toussaint, Godfried" sort="Toussaint, Godfried" uniqKey="Toussaint G" first="Godfried" last="Toussaint">Godfried Toussaint</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:37153A26F40DCA674F245CC22C001457F8E6DE2E</idno><date when="1999" year="1999">1999</date><idno type="doi">10.1006/jvci.1999.0415</idno><idno type="url">https://api.istex.fr/document/37153A26F40DCA674F245CC22C001457F8E6DE2E/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001A39</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001A39</idno><idno type="wicri:Area/Istex/Curation">001922</idno><idno type="wicri:Area/Istex/Checkpoint">000D88</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000D88</idno><idno type="wicri:doubleKey">1047-3203:1999:Bose P:drawing:nice:projections</idno><idno type="wicri:Area/Main/Merge">002492</idno><idno type="wicri:Area/Main/Curation">002138</idno><idno type="wicri:Area/Main/Exploration">002138</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Drawing Nice Projections of Objects in Space</title><author><name sortKey="Bose, Prosenjit" sort="Bose, Prosenjit" uniqKey="Bose P" first="Prosenjit" last="Bose">Prosenjit Bose</name><affiliation wicri:level="1"><country wicri:rule="url">Canada</country><wicri:regionArea>School of Computer Science, Carleton University, 1125 Colonel By Drive, Ottawa, Ontario, K1S 5B6</wicri:regionArea><wicri:noRegion>K1S 5B6</wicri:noRegion></affiliation></author><author><name sortKey="G Mez, Francisco" sort="G Mez, Francisco" uniqKey="G Mez F" first="Francisco" last="G Mez">Francisco G Mez</name><affiliation wicri:level="1"><country wicri:rule="url">Espagne</country><wicri:regionArea>Escuela Universitaria de Informática, U.P.M. Madrid</wicri:regionArea><wicri:noRegion>U.P.M. Madrid</wicri:noRegion></affiliation></author><author><name sortKey="Ramos, Pedro" sort="Ramos, Pedro" uniqKey="Ramos P" first="Pedro" last="Ramos">Pedro Ramos</name><affiliation wicri:level="1"><country wicri:rule="url">Espagne</country><wicri:regionArea>Facultad de Informática, U.P.M. Madrid</wicri:regionArea><wicri:noRegion>U.P.M. Madrid</wicri:noRegion></affiliation></author><author><name sortKey="Toussaint, Godfried" sort="Toussaint, Godfried" uniqKey="Toussaint G" first="Godfried" last="Toussaint">Godfried Toussaint</name><affiliation wicri:level="4"><country wicri:rule="url">Canada</country><wicri:regionArea>School of Computer Science, McGill University, Montreal, Quebec</wicri:regionArea><orgName type="university">Université McGill</orgName><placeName><settlement type="city">Montréal</settlement><region type="state">Québec</region></placeName></affiliation></author></analytic><monogr></monogr><series><title level="j">Journal of Visual Communication and Image Representation</title><title level="j" type="abbrev">YJVCI</title><idno type="ISSN">1047-3203</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="1999">1999</date><biblScope unit="volume">10</biblScope><biblScope unit="issue">2</biblScope><biblScope unit="page" from="155">155</biblScope><biblScope unit="page" to="172">172</biblScope></imprint><idno type="ISSN">1047-3203</idno></series><idno type="istex">37153A26F40DCA674F245CC22C001457F8E6DE2E</idno><idno type="DOI">10.1006/jvci.1999.0415</idno><idno type="PII">S1047-3203(99)90415-7</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">1047-3203</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Given a polygonal object (simple polygon, geometric graph, wire-frame, skeleton or more generally a set of line segments) in three-dimensional Euclidean space, we consider the problem of computing a variety of “nice” parallel (orthographic) projections of the object. We show that given a general polygonal object consisting ofnline segments in space, deciding whether it admits acrossing-freeprojection can be done inO(n2logn+k) time andO(n2+k) space, wherekis the number of edge intersections of forbidden quadrilaterals (i.e., a set of directions that admits a crossing) and varies from zero toO(n4). This implies for example that, given a simple polygon in 3-space, we can determine if there exists a plane on which the projection is a simple polygon, within the same complexity. Furthermore, if such a projection does not exist, aminimum-crossingprojection can be found inO(n4) time and space. We show that an object always admits a regular projection (of interest to knot theory) and that such a projection can be obtained inO(n2) time and space or inO(n3) time and linear space. A description of the set of all directions which yield regular projections can be computed inO(n3logn+k) time, wherekis the number of intersections of a set of quadratic arcs on the direction sphere and varies fromO(n3) toO(n6). Finally, when the objects are polygons and trees in space, we considermonotonicprojections, i.e., projections such that every path from the root of the tree to every leaf is monotonic in a common direction on the projection plane. We solve a variety of such problems. For example, given a polygonal chainP, we can determine inO(n) time ifPis monotonic on the projection plane, and inO(nlogn) time we can findallthe viewing directions with respect to whichPis monotonic. In addition, inO(n2) time, we can determine all directions with respect to which a given tree or simple polygon is monotonic.</div></front></TEI><affiliations><list><country><li>Canada</li><li>Espagne</li></country><region><li>Québec</li></region><settlement><li>Montréal</li></settlement><orgName><li>Université McGill</li></orgName></list><tree><country name="Canada"><noRegion><name sortKey="Bose, Prosenjit" sort="Bose, Prosenjit" uniqKey="Bose P" first="Prosenjit" last="Bose">Prosenjit Bose</name></noRegion><name sortKey="Toussaint, Godfried" sort="Toussaint, Godfried" uniqKey="Toussaint G" first="Godfried" last="Toussaint">Godfried Toussaint</name></country><country name="Espagne"><noRegion><name sortKey="G Mez, Francisco" sort="G Mez, Francisco" uniqKey="G Mez F" first="Francisco" last="G Mez">Francisco G Mez</name></noRegion><name sortKey="Ramos, Pedro" sort="Ramos, Pedro" uniqKey="Ramos P" first="Pedro" last="Ramos">Pedro Ramos</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002138 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 002138 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:37153A26F40DCA674F245CC22C001457F8E6DE2E
|texte= Drawing Nice Projections of Objects in Space
}}
| This area was generated with Dilib version V0.6.31. |  |