{"entities":{"Q1822240":{"pageid":1832982,"ns":120,"title":"Item:Q1822240","lastrevid":73448850,"modified":"2026-04-14T16:02:14Z","type":"item","id":"Q1822240","labels":{"en":{"language":"en","value":"A simple linear algorithm for intersecting convex polygons"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4001478"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1822240$36602FBD-6ED9-48EE-B211-FCCE7DCFA9E4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"720c5037213b488dfb8d8866cc21af1c4b1a9769","datavalue":{"value":{"text":"A simple linear algorithm for intersecting convex polygons","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1822240$405F0597-6CF5-485B-9EF5-74623B3E2394","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b6cfb28baf341dba44965fd043ad6a59051e726a","datavalue":{"value":"0617.68041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1822240$2E2A346C-4423-4021-B5E2-F9DCD0EC3B22","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"422cf2b5db75fee7e72d556cf18121906ef6d684","datavalue":{"value":"10.1007/BF01898355","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1822240$F7DA468E-A404-48A9-9A24-890E75D3E5E1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"899862c0c77c2524569e7ab477589b03463c5b0f","datavalue":{"value":{"entity-type":"item","numeric-id":182688,"id":"Q182688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1822240$A5615CBC-1FAA-481D-A633-A36CDE93AE52","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"43813089db9b51ed7a23a6dbdbdac76a6962820f","datavalue":{"value":{"entity-type":"item","numeric-id":205026,"id":"Q205026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1822240$C98D1D36-FEED-4F37-8E0D-D0E7A63720DE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1822240$B94862D6-36E8-4E2B-8850-3737F24B6978","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d8fcd1c3d315c69d2eb5c77f6f2e10020bc50f63","datavalue":{"value":"Let P and Q be two convex polygons with m and n vertices, respectively, which are specified by their cartesian coordinates in order. A simple \\(O(m+n)\\) algorithm is presented for computing the intersection of P and Q. Unlike previous algorithms, the new algorithm consists of a two-step combination of two simple algorithms for finding convex hulls and triangulations of polygons.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1822240$CF1565D5-8DC5-404E-A050-F19FEEF22EBE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1822240$A0E434E5-AB72-4A64-8D7C-6D1CAF1BC268","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ddd8cb1932c6bc41681458db5f685a2a286fde55","datavalue":{"value":"52Bxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1822240$3A3ABEFD-5986-4E57-B463-233801CCB15E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e5762e9b09407c15760c5fa5cac71c82c32bf230","datavalue":{"value":"52A10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1822240$E3156B96-17C5-4B96-925C-464B19AF2854","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"787991083c73d36b11211c889ffe92c15b06a9ed","datavalue":{"value":"4001478","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1822240$D9C130AE-1C42-4FA1-9750-D6C1DEF30316","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1822240$605C386A-6433-4A55-8C4E-F450963911F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"96582d85dbf9b845ada3b4fb4627bf8479daeaf5","datavalue":{"value":"geometric algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1822240$BADF540B-CF2E-47A7-AA55-1486F8B97908","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0fa312182bb7eaae3fd62e5da43ed90b053a6af4","datavalue":{"value":"convex polygons","type":"string"},"datatype":"string"},"type":"statement","id":"Q1822240$8BE16E38-6D3C-4A10-8803-BEB05E08F69F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ab57561e8c95fe21680ade7400a07692c4406a75","datavalue":{"value":"intersection","type":"string"},"datatype":"string"},"type":"statement","id":"Q1822240$5925ACF8-9614-4B39-A152-A713D2B7C549","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"87b147aa16e08aea71594b690e239b8aa358d8be","datavalue":{"value":"convex hulls","type":"string"},"datatype":"string"},"type":"statement","id":"Q1822240$31BF2F04-66F3-412E-A1F1-510C37B4C0EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac56fc76a1881f7734420caaa3087335e88a6301","datavalue":{"value":"triangulations of polygons","type":"string"},"datatype":"string"},"type":"statement","id":"Q1822240$B010172D-DBF9-41F2-BA0F-D48CB1998A69","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1822240$591F6D87-41BB-4886-A22A-2F694D3F0D44","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ae0713540eb691df7bd8820bc004fcb597f484c","datavalue":{"value":{"entity-type":"item","numeric-id":1249042,"id":"Q1249042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1822240$694C63B3-770B-4E74-8310-ECEF22CFDE64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"914d72616aa01d5795c7ffcd12e073291e7b2ddf","datavalue":{"value":{"entity-type":"item","numeric-id":4060124,"id":"Q4060124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1822240$B14E34EC-89CB-43DB-8D38-F2B8E9CD9841","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83ab627dbfca4abdba382950256fa769d0e8cfb3","datavalue":{"value":{"entity-type":"item","numeric-id":3316124,"id":"Q3316124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1822240$FFA07877-65B9-4272-85CC-AF863BDC303F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67de1d20565f1e86d9fc7d83e01bc45002e72551","datavalue":{"value":{"entity-type":"item","numeric-id":786507,"id":"Q786507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1822240$8F18ED18-1099-4344-A361-7050E5441B86","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8024869fad18c9653c9bbd806cdf26a9840a53dc","datavalue":{"value":"https://doi.org/10.1007/bf01898355","type":"string"},"datatype":"url"},"type":"statement","id":"Q1822240$8CC487AB-B2B3-49A7-852B-ED32778C05C5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0995e3b5a222f8c36139e5a25e3459a69e39a3b5","datavalue":{"value":"W1977534285","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1822240$55608D4E-CFDB-44A8-AFBA-7D5D3DADD018","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"331eca5d9d9374a0a39391e0705f9372ea03490f","datavalue":{"value":{"entity-type":"item","numeric-id":3316124,"id":"Q3316124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30e24bb56c14008c9280df86eb2354e6cc7e9f13","datavalue":{"value":{"amount":"+0.9518207907676696","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1822240$5194C6C3-B5EB-45C9-BCFB-C9450A2271D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3326df61c1072dfe637210fa037dd8cfa441834d","datavalue":{"value":{"entity-type":"item","numeric-id":1107994,"id":"Q1107994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c987136675ae86da7bfff3637dba47cee3f1a525","datavalue":{"value":{"amount":"+0.8816955089569092","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1822240$2BBE4537-5D96-4970-BCF2-1FA4CDCBF76D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"707f135203e3472e8c86641eb6750ff47bef77e4","datavalue":{"value":{"entity-type":"item","numeric-id":5368724,"id":"Q5368724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8695b0712aca5844c6bd2b9299694d6cd8f7ce43","datavalue":{"value":{"amount":"+0.8502339720726013","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1822240$2BE09B6A-20FB-46AE-8EA9-E319CE06A8FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8446dcb82fa389aa8f6a1c5a53d13ec1a3f0977d","datavalue":{"value":{"entity-type":"item","numeric-id":728493,"id":"Q728493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a45ca5e0d85cf2941eaedc8f2d5123dd1bf57bb","datavalue":{"value":{"amount":"+0.850233793258667","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1822240$D5BA0F33-E756-4F5B-B924-BB35EABC928B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5b5d60bda5e837b9f006853135255ddebbf1e3d5","datavalue":{"value":{"entity-type":"item","numeric-id":3700833,"id":"Q3700833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"808b520b556569b95a4f88ee4c49b5c8271b295f","datavalue":{"value":{"amount":"+0.8284552693367004","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1822240$2D693C05-9E95-44E3-B4E6-DFD4D1368192","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A simple linear algorithm for intersecting convex polygons","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_simple_linear_algorithm_for_intersecting_convex_polygons"}}}}}