A simple linear algorithm for intersecting convex polygons View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

1985-08

AUTHORS

Godfried T. Toussaint

ABSTRACT

LetP andQ be two convex polygons withm andn vertices, respectively, which are specified by their cartesian coordinates in order. A simpleO(m+n) algorithm is presented for computing the intersection ofP andQ. Unlike previous algorithms, the new algorithm consists of a two-step combination of two simple algorithms for finding convex hulls and triangulations of polygons. More... »

PAGES

118-123

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bf01898355

DOI

http://dx.doi.org/10.1007/bf01898355

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1034934409


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "McGill University", 
          "id": "https://www.grid.ac/institutes/grid.14709.3b", 
          "name": [
            "School of Computer Science, McGill University, 805 Sherbrooke Street West, H3A 2K6, Montreal, Quebec, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Toussaint", 
        "givenName": "Godfried T.", 
        "id": "sg:person.014041144375.22", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014041144375.22"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/0020-0190(78)90062-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006110172"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02243778", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032338660", 
          "https://doi.org/10.1007/bf02243778"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02243778", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032338660", 
          "https://doi.org/10.1007/bf02243778"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0031-3203(82)90057-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032948866"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0031-3203(82)90057-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032948866"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-94-009-7772-3_7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033730369", 
          "https://doi.org/10.1007/978-94-009-7772-3_7"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0146-664x(82)90023-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048751598"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.2307/2319703", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1069885864"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/sfcs.1983.1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086229955"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/sfcs.1976.16", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086250697"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1080/00029890.1975.11993898", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1103214563"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1985-08", 
    "datePublishedReg": "1985-08-01", 
    "description": "LetP andQ be two convex polygons withm andn vertices, respectively, which are specified by their cartesian coordinates in order. A simpleO(m+n) algorithm is presented for computing the intersection ofP andQ. Unlike previous algorithms, the new algorithm consists of a two-step combination of two simple algorithms for finding convex hulls and triangulations of polygons.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/bf01898355", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1046897", 
        "issn": [
          "0178-2789", 
          "1432-2315"
        ], 
        "name": "The Visual Computer", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "1"
      }
    ], 
    "name": "A simple linear algorithm for intersecting convex polygons", 
    "pagination": "118-123", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "a66a240dab7bbab3b14ee0d9d8d91fb56b3aecc770ae06cc80af1a1bea899fc6"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf01898355"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1034934409"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf01898355", 
      "https://app.dimensions.ai/details/publication/pub.1034934409"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T10:52", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000351_0000000351/records_43229_00000000.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007/BF01898355"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/bf01898355'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/bf01898355'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf01898355'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf01898355'


 

This table displays all metadata directly associated to this object as RDF triples.

90 TRIPLES      21 PREDICATES      36 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf01898355 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nd4ca781fe1ad4a2586d8712483d2b5fc
4 schema:citation sg:pub.10.1007/978-94-009-7772-3_7
5 sg:pub.10.1007/bf02243778
6 https://doi.org/10.1016/0020-0190(78)90062-5
7 https://doi.org/10.1016/0031-3203(82)90057-7
8 https://doi.org/10.1016/0146-664x(82)90023-5
9 https://doi.org/10.1080/00029890.1975.11993898
10 https://doi.org/10.1109/sfcs.1976.16
11 https://doi.org/10.1109/sfcs.1983.1
12 https://doi.org/10.2307/2319703
13 schema:datePublished 1985-08
14 schema:datePublishedReg 1985-08-01
15 schema:description LetP andQ be two convex polygons withm andn vertices, respectively, which are specified by their cartesian coordinates in order. A simpleO(m+n) algorithm is presented for computing the intersection ofP andQ. Unlike previous algorithms, the new algorithm consists of a two-step combination of two simple algorithms for finding convex hulls and triangulations of polygons.
16 schema:genre research_article
17 schema:inLanguage en
18 schema:isAccessibleForFree true
19 schema:isPartOf N45c0b272a2a54f0b8ab3b516bdd3bc23
20 N7bf542617877436886a6ecd712e522a7
21 sg:journal.1046897
22 schema:name A simple linear algorithm for intersecting convex polygons
23 schema:pagination 118-123
24 schema:productId N3b36ad5e97204103959bb37aac905304
25 N7b04a688e6ac473898db46164ac51014
26 Nd5c5328fa2694e7c8691eb5696904b77
27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034934409
28 https://doi.org/10.1007/bf01898355
29 schema:sdDatePublished 2019-04-11T10:52
30 schema:sdLicense https://scigraph.springernature.com/explorer/license/
31 schema:sdPublisher N4c5da9e80ff5462ba1a67b43e7aa077d
32 schema:url http://link.springer.com/10.1007/BF01898355
33 sgo:license sg:explorer/license/
34 sgo:sdDataset articles
35 rdf:type schema:ScholarlyArticle
36 N3b36ad5e97204103959bb37aac905304 schema:name dimensions_id
37 schema:value pub.1034934409
38 rdf:type schema:PropertyValue
39 N45c0b272a2a54f0b8ab3b516bdd3bc23 schema:issueNumber 2
40 rdf:type schema:PublicationIssue
41 N4c5da9e80ff5462ba1a67b43e7aa077d schema:name Springer Nature - SN SciGraph project
42 rdf:type schema:Organization
43 N7b04a688e6ac473898db46164ac51014 schema:name doi
44 schema:value 10.1007/bf01898355
45 rdf:type schema:PropertyValue
46 N7bf542617877436886a6ecd712e522a7 schema:volumeNumber 1
47 rdf:type schema:PublicationVolume
48 Nd4ca781fe1ad4a2586d8712483d2b5fc rdf:first sg:person.014041144375.22
49 rdf:rest rdf:nil
50 Nd5c5328fa2694e7c8691eb5696904b77 schema:name readcube_id
51 schema:value a66a240dab7bbab3b14ee0d9d8d91fb56b3aecc770ae06cc80af1a1bea899fc6
52 rdf:type schema:PropertyValue
53 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
54 schema:name Information and Computing Sciences
55 rdf:type schema:DefinedTerm
56 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
57 schema:name Computation Theory and Mathematics
58 rdf:type schema:DefinedTerm
59 sg:journal.1046897 schema:issn 0178-2789
60 1432-2315
61 schema:name The Visual Computer
62 rdf:type schema:Periodical
63 sg:person.014041144375.22 schema:affiliation https://www.grid.ac/institutes/grid.14709.3b
64 schema:familyName Toussaint
65 schema:givenName Godfried T.
66 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014041144375.22
67 rdf:type schema:Person
68 sg:pub.10.1007/978-94-009-7772-3_7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033730369
69 https://doi.org/10.1007/978-94-009-7772-3_7
70 rdf:type schema:CreativeWork
71 sg:pub.10.1007/bf02243778 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032338660
72 https://doi.org/10.1007/bf02243778
73 rdf:type schema:CreativeWork
74 https://doi.org/10.1016/0020-0190(78)90062-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006110172
75 rdf:type schema:CreativeWork
76 https://doi.org/10.1016/0031-3203(82)90057-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032948866
77 rdf:type schema:CreativeWork
78 https://doi.org/10.1016/0146-664x(82)90023-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048751598
79 rdf:type schema:CreativeWork
80 https://doi.org/10.1080/00029890.1975.11993898 schema:sameAs https://app.dimensions.ai/details/publication/pub.1103214563
81 rdf:type schema:CreativeWork
82 https://doi.org/10.1109/sfcs.1976.16 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086250697
83 rdf:type schema:CreativeWork
84 https://doi.org/10.1109/sfcs.1983.1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086229955
85 rdf:type schema:CreativeWork
86 https://doi.org/10.2307/2319703 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069885864
87 rdf:type schema:CreativeWork
88 https://www.grid.ac/institutes/grid.14709.3b schema:alternateName McGill University
89 schema:name School of Computer Science, McGill University, 805 Sherbrooke Street West, H3A 2K6, Montreal, Quebec, Canada
90 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...