Point in polygon (original) (raw)
Der Punkt-in-Polygon-Test nach Jordan prüft, ob ein bestimmter Punkt in der Ebene innerhalb, außerhalb oder an der Grenze eines Polygons liegt. Nach dem Jordanschen Kurvensatz teilen, vereinfacht gesagt, die Ränder eines Polygons den Datenraum in eine Innen- und eine Außenseite. Für viele Anwendungen ist es nötig, herauszufinden, ob ein Punkt innerhalb oder außerhalb eines Polygons liegt.
| Property | Value |
|---|---|
| dbo:abstract | En geometria computacional, el problema del punt al polígon (PIP, de point-in-polygon) demana si un punt donat roman a dins, a fora, o als límits d'un polígon. És un cas especial dels problemes de localització de punts i té aplicacions en les àrees que tracten el processament de dades geomètriques, com ara la infografia, la visió artificial, els sistemes d'informació geogràfica (SIG), la i el disseny assistit per ordinador. Una descripció primerenca del problema en gràfics computacionals mostra dos enfocaments comuns (traçament de raigs i suma d'angles) que s'empraven ja el 1974. Un intent dels entesos en gràfics computacionals per trobar la història del problema i alguns trucs per resoldre'l es pot trobar en un exemplar de Ray Tracing News. (ca) Der Punkt-in-Polygon-Test nach Jordan prüft, ob ein bestimmter Punkt in der Ebene innerhalb, außerhalb oder an der Grenze eines Polygons liegt. Nach dem Jordanschen Kurvensatz teilen, vereinfacht gesagt, die Ränder eines Polygons den Datenraum in eine Innen- und eine Außenseite. Für viele Anwendungen ist es nötig, herauszufinden, ob ein Punkt innerhalb oder außerhalb eines Polygons liegt. (de) In computational geometry, the point-in-polygon (PIP) problem asks whether a given point in the plane lies inside, outside, or on the boundary of a polygon. It is a special case of point location problems and finds applications in areas that deal with processing geometrical data, such as computer graphics, computer vision, geographic information systems (GIS), motion planning, and computer-aided design (CAD). An early description of the problem in computer graphics shows two common approaches (ray casting and angle summation) in use as early as 1974. An attempt of computer graphics veterans to trace the history of the problem and some tricks for its solution can be found in an issue of the Ray Tracing News. (en) В вычислительной геометрии известна задача об определении принадлежности точки многоугольнику. На плоскости даны многоугольник и точка. Требуется решить вопрос о принадлежности точки многоугольнику. Многоугольник может быть как выпуклым, так и невыпуклым. Обычно предполагается, что многоугольник простой, то есть без самопересечений; но задачу рассматривают и для не-простых многоугольников. В последнем случае разные способы определения принадлежности точки многоугольнику могут привести к разным результатам. Различают алгоритмы без предварительной обработки; и алгоритмы с предварительной обработкой, в ходе которой создаются некоторые структуры данных, позволяющие в дальнейшем быстрее отвечать на множество запросов о принадлежности разных точек одному и тому же многоугольнику. (ru) Em geometria computacional, o problema ponto em polígono (PIP) pergunta se um dado ponto no plano repousa dentro, fora ou na borda do polígono. É um caso especial de problemas de localização de pontos e encontra aplicações em áreas que lidam com o processamento de dados geométricos, tais como computação gráfica, visão computacional e sistemas de informação geográfica (SIG) e CAD. Uma descrição precoce do problema em computação gráfica mostra duas abordagens comuns (ray casting e o soma de ângulo) em uso no começo de 1974. Uma tentativa de gráficos de computador veteranos para rastrear o histórico do problema e alguns truques para a sua solução pode ser encontrada em um problema do Ray Tracing News. (pt) Задача про належність точки многокутнику — задача обчислювальної геометрії, яка полягає в тому, що треба з'ясувати, як розташована на площині задана точка відносно многокутника. Задача розв'язується, як для простих многокутників, тобто без самоперетинів, так і для многокутників, що містять перетин сторін. Розрізняють алгоритми без попередньої обробки даних і алгоритми з попередньою обробкою, в ході якої створюються структури даних, що дозволяють при повторних розв'язаннях швидше відповідати на запити про належність точок одному й тому ж многокутнику. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Simple_polygon.svg?width=300 |
| dbo:wikiPageExternalLink | http://geomalgorithms.com/a03-_inclusion.html http://www.ics.uci.edu/~eppstein/161/960307.html |
| dbo:wikiPageID | 504484 (xsd:integer) |
| dbo:wikiPageLength | 11977 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1124815758 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Monotone_polygon dbr:Barycentric_coordinate_system dbc:Polygons dbr:Jordan_curve_theorem dbr:Regular_polygon dbr:Scalable_Vector_Graphics dbr:Geographic_information_system dbr:Ray_casting dbr:Convex_polygon dbr:Convex_polytope dbc:Geometric_algorithms dbr:Computational_geometry dbr:Computer-aided_design dbr:Computer_graphics dbr:Computer_program dbr:Computer_vision dbc:Point_(geometry) dbr:Parametric_equation dbr:Polygon dbr:Simple_polygon dbr:Even_number dbr:Numerical_analysis dbr:Inverse_trigonometric_functions dbr:JTS_Topology_Suite dbr:Surface_(mathematics) dbr:Triangle dbr:Winding_number dbr:Dot_product dbr:Odd_number dbr:Vertex_(geometry) dbr:Point_location dbr:Ray_(mathematics) dbr:Even–odd_rule dbr:Subtended_angle dbr:Motion_planning dbr:Nonzero-rule dbr:Star-shaped_polygon dbr:Tolerance_(engineering) dbr:Finite_precision_arithmetics dbr:Simple_polygons dbr:Numerical_robustness dbr:Complex_polygons dbr:File:Winding_number_algorithm_example.svg dbr:Geometric_query dbr:File:RecursiveEvenPolygon.svg dbr:File:Simple_polygon.svg |
| dbp:wikiPageUsesTemplate | dbt:Anchor dbt:Code dbt:Expand_section dbt:Reflist dbt:See_also dbt:Short_description dbt:Wikibooks |
| dcterms:subject | dbc:Polygons dbc:Geometric_algorithms dbc:Point_(geometry) |
| rdf:type | owl:Thing yago:Artifact100021939 yago:DataSystem103164344 yago:Instrumentality103575240 yago:Object100002684 yago:PhysicalEntity100001930 yago:WikicatGeographicInformationSystems yago:System104377057 yago:Whole100003553 |
| rdfs:comment | Der Punkt-in-Polygon-Test nach Jordan prüft, ob ein bestimmter Punkt in der Ebene innerhalb, außerhalb oder an der Grenze eines Polygons liegt. Nach dem Jordanschen Kurvensatz teilen, vereinfacht gesagt, die Ränder eines Polygons den Datenraum in eine Innen- und eine Außenseite. Für viele Anwendungen ist es nötig, herauszufinden, ob ein Punkt innerhalb oder außerhalb eines Polygons liegt. (de) В вычислительной геометрии известна задача об определении принадлежности точки многоугольнику. На плоскости даны многоугольник и точка. Требуется решить вопрос о принадлежности точки многоугольнику. Многоугольник может быть как выпуклым, так и невыпуклым. Обычно предполагается, что многоугольник простой, то есть без самопересечений; но задачу рассматривают и для не-простых многоугольников. В последнем случае разные способы определения принадлежности точки многоугольнику могут привести к разным результатам. Различают алгоритмы без предварительной обработки; и алгоритмы с предварительной обработкой, в ходе которой создаются некоторые структуры данных, позволяющие в дальнейшем быстрее отвечать на множество запросов о принадлежности разных точек одному и тому же многоугольнику. (ru) Задача про належність точки многокутнику — задача обчислювальної геометрії, яка полягає в тому, що треба з'ясувати, як розташована на площині задана точка відносно многокутника. Задача розв'язується, як для простих многокутників, тобто без самоперетинів, так і для многокутників, що містять перетин сторін. Розрізняють алгоритми без попередньої обробки даних і алгоритми з попередньою обробкою, в ході якої створюються структури даних, що дозволяють при повторних розв'язаннях швидше відповідати на запити про належність точок одному й тому ж многокутнику. (uk) En geometria computacional, el problema del punt al polígon (PIP, de point-in-polygon) demana si un punt donat roman a dins, a fora, o als límits d'un polígon. És un cas especial dels problemes de localització de punts i té aplicacions en les àrees que tracten el processament de dades geomètriques, com ara la infografia, la visió artificial, els sistemes d'informació geogràfica (SIG), la i el disseny assistit per ordinador. Una descripció primerenca del problema en gràfics computacionals mostra dos enfocaments comuns (traçament de raigs i suma d'angles) que s'empraven ja el 1974. (ca) In computational geometry, the point-in-polygon (PIP) problem asks whether a given point in the plane lies inside, outside, or on the boundary of a polygon. It is a special case of point location problems and finds applications in areas that deal with processing geometrical data, such as computer graphics, computer vision, geographic information systems (GIS), motion planning, and computer-aided design (CAD). An early description of the problem in computer graphics shows two common approaches (ray casting and angle summation) in use as early as 1974. (en) Em geometria computacional, o problema ponto em polígono (PIP) pergunta se um dado ponto no plano repousa dentro, fora ou na borda do polígono. É um caso especial de problemas de localização de pontos e encontra aplicações em áreas que lidam com o processamento de dados geométricos, tais como computação gráfica, visão computacional e sistemas de informação geográfica (SIG) e CAD. Uma descrição precoce do problema em computação gráfica mostra duas abordagens comuns (ray casting e o soma de ângulo) em uso no começo de 1974. (pt) |
| rdfs:label | Punt al polígon (ca) Punkt-in-Polygon-Test nach Jordan (de) Point in polygon (en) Ponto em polígono (pt) Задача о принадлежности точки многоугольнику (ru) Належність точки многокутнику (uk) |
| rdfs:seeAlso | dbr:Jordan_curve_theorem |
| owl:sameAs | freebase:Point in polygon yago-res:Point in polygon wikidata:Point in polygon dbpedia-ca:Point in polygon dbpedia-de:Point in polygon dbpedia-fa:Point in polygon dbpedia-fi:Point in polygon dbpedia-he:Point in polygon dbpedia-no:Point in polygon dbpedia-pt:Point in polygon dbpedia-ru:Point in polygon dbpedia-sr:Point in polygon dbpedia-uk:Point in polygon dbpedia-vi:Point in polygon https://global.dbpedia.org/id/Zhvi |
| prov:wasDerivedFrom | wikipedia-en:Point_in_polygon?oldid=1124815758&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Winding_number_algorithm_example.svg wiki-commons:Special:FilePath/RecursiveEvenPolygon.svg wiki-commons:Special:FilePath/Simple_polygon.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Point_in_polygon |
| is dbo:wikiPageDisambiguates of | dbr:Pip |
| is dbo:wikiPageRedirects of | dbr:Point-in-polygon dbr:Point-in-polygon_queries dbr:Point-in-polygon_query dbr:Point_in_polygon_test dbr:Ray_casting_algorithm dbr:Inside-outside_test dbr:Inside–outside_test |
| is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:List_of_combinatorial_computational_geometry_topics dbr:Monotone_polygon dbr:Privacy-preserving_computational_geometry dbr:Dynamic_convex_hull dbr:List_of_geometry_topics dbr:Geo-fence dbr:Computational_geometry dbr:Pip dbr:Polygon dbr:Simple_polygon dbr:Vector_overlay dbr:Map_database_management dbr:Parity_of_zero dbr:Hit-testing dbr:JTS_Topology_Suite dbr:Winding_number dbr:Point_location dbr:Even–odd_rule dbr:Polygon_partition dbr:Study_of_animal_locomotion dbr:Point-in-polygon dbr:Point-in-polygon_queries dbr:Point-in-polygon_query dbr:Point_in_polygon_test dbr:Ray_casting_algorithm dbr:Inside-outside_test dbr:Inside–outside_test |
| is foaf:primaryTopic of | wikipedia-en:Point_in_polygon |
