Algoritmo radial

Un algoritmo radial es un algoritmo matemático que permite localizar si un punto en referencia a un polígono, situados ambos en el mismo plano, se encuentra dentro o fuera de este. Este problema para el cual otros algoritmos como el de Ray casting han intentado dar solución, se conoce como punto en polígono.

Aplicaciones

Se ha propuesto su uso en programas de geometría computacional que requieren mucha precisión, como los Sistemas de Información Geográfica SIG o GIS, diseño asistido por computadora CAD, y gráficos por computadora.^[1]

Descripción intuitiva

El procedimiento consiste en calcular la sumatoria de los ángulos de barrido formados por el conjunto de pares de vectores cuyos orígenes están en el punto y sus extremos en los vértices del polígono.

Dichos pares de vectores se toman en el orden descrito por los vértices del polígono, y con el signo dependiente del sentido de crecimiento del ángulo. Habitualmente, se toma el sentido antihorario como positivo, y el sentido horario como negativo.

El algoritmo calcula un valor expresado en unidades angulares y, teóricamente, sólo son posibles dos resultados, aunque, debido a la limitada precisión de las computadoras, los valores obtenidos suelen no ser exactos.

   0 rad (o un valor muy próximo)		Indica que el punto está fuera del polígono.
   2π rad (o un valor muy próximo)	        Indica que el punto está dentro del polígono.

No obstante, y en base a estos resultados, la implementación típica del algoritmo en un lenguaje de programación, se suele modificar para que devuelva uno de los siguientes tres valores discretos:

   -1        Cuando el punto se encuentra fuera del polígono.
    0        Cuando el punto se encuentra exactamente sobre uno de los lados del polígono. Esta circunstancia se pone de manifiesto durante la
                 ejecución del algoritmo, cuando el valor absoluto del ángulo formado por uno de los pares de vectores resulta ser igual a π rad.
    1        Cuando el punto se encuentra dentro del polígono.

Pseudocódigo

 Función Punto_En_Polígono (Punto P, Vértice V[] )
 {
   suma = 0;
   // Bucle por todos los segmentos del polígono.
   Por (cada segmento S[i] formado por  V[i] y V[i+1] )
   {
       a = AnguloEntre(P, S[i]); // Ángulo con signo, desde V[i] hasta V[i+1]
       Si (|a| == π)
       {
	    Salir con Resultado = 0; // El punto está sobre el lado del polígono.
       }
       // Incrementar la suma de ángulos con signo.
       suma = suma + a;
   } Siguiente segmento.
   Si (suma == 0)  Salir con Resultado = -1;
   Si (suma == 2π) Salir con Resultado = 1;
 }

Véase también

Enlaces externos

Geogebra, página web con un gráfico de aplicación práctica.
Real Academia de Ingeniería. http://diccionario.raing.es/es/lema/algoritmo-radial

Referencias

↑ Martín Arriarán, Miguel (Mayo de 2000). «El algoritmo Radial. Otra solución para el problema del Punto en Polígono.». Mapping, Revista Internacional de Geomática y Ciencias de la Tierra 9 (62): 20-22. Consultado el 23 de diciembre de 2019.

Bibliografía

Molano, Rubén; Rodríguez, Pablo G.; Caro, Andrés; Durán, M. Luisa (2012). «Finding the largest area rectangle of arbitrary orientation in a closed contour». Applied Mathematics and Computation (en inglés) 218 (19): 9866-9874. doi:10.1016/j.amc.2012.03.063.

Datos: Q76761418

Read other articles:

قيصري إيرسيسبور

قيصري إيرسيسبور اللقب التنانين الزرق تأسس عام 1 يونيو 1966 الملعب ملعب قادر هاس(السعة: 32,864[1]) البلد تركيا الدوري الدوري التركي لكرة القدم الدوري التركي لكرة القدم 2014-15 17 (هبوط) الإدارة زيا إيرين المدرب فاتح تيكي الموقع الرسمي الموقع الرسمي الطقم الأساسي الطقم الاحتياط...

Politeknik Negeri Sambas

Politeknik Negeri SambasJenisPerguruan Tinggi Negeri, PoliteknikDirekturMahyus, S.Pd., S.E., M.M.AlamatJl.Raya Sejangkung Kawasan Pendidikan Tinggi, Kabupaten Sambas, Kalimantan Barat, IndonesiaSitus webhttps://poltesa.ac.id/ Politeknik Negeri Sambas yang disingkat Poltesa, adalah salah satu Pendidikan Tinggi yang berada di Kabupaten Sambas, Provinsi Kalimantan Barat. Sejarah Pembentukan Politeknik Negeri Sambas diprakarsai oleh Bupati Sambas Ir. H. Burhanuddin A. Rasyid dengan membentuk Tim ...

Kleopatra Selene II

Cleopatra Selene IIIbu suri NumidiaIbu suri MauretaniaPatung dada Romawi kuno Cleopatra Selene II, Ratu Mauretania, atau ibunya Cleopatra VII dari Mesir, Museum Arkeologi Cherchell, Aljazair[1]Kelahiran40 SM (diyakini, tanggal pasti tidak diketahui)Alexandria, MesirKematian6 SMCaesarea, Kerajaan MauretaniaPemakamanMausoleum Kerajaan MauretaniaNama lengkapCleopatra SeleneAyahMarkus AntoniusIbuCleopatra VII PhilopatorPasanganJuba II dari NumidiaAnakPtolemy, Raja MauretaniaDrusilla Cleop...

Sokol Çikalleshi

Sokol Çikalleshi Çikalleshi in azione con la maglia della nazionale albanese nel 2016 Nazionalità Albania Altezza 187 cm Peso 79 kg Calcio Ruolo Attaccante Squadra Konyaspor Carriera Giovanili 2004-2007 Besa Kavajë Squadre di club1 2007-2011 Besa Kavajë53 (8)2011→ Skënderbeu4 (0)2011-2012 Besa Kavajë0 (0)2012→ Tirana13 (2)2012-2013→ Incheon Utd6 (0)2013 Besa Kavajë4 (3)2013-2014 Kukësi30 (17)2014-2015 RNK Spalato32 (1...

Stasiun Kertosono

Stasiun Kertosono D16 Tampak depan Stasiun Kertosono, 2021LokasiJalan Stasiun KertosonoBanaran, Kertosono, Nganjuk, Jawa TimurIndonesiaKoordinat7°35′40″S 112°6′16″E / 7.59444°S 112.10444°E / -7.59444; 112.10444Koordinat: 7°35′40″S 112°6′16″E / 7.59444°S 112.10444°E / -7.59444; 112.10444Ketinggian+44 mOperator Kereta Api IndonesiaDaerah Operasi VII Madiun KAI Commuter KAI Logistik Letak km 96+888 lintas Surabaya Kota-Kerto...

More Deadly Than the Male

1919 film by Robert G. Vignola More Deadly Than The MaleDirected byRobert G. VignolaWritten byJoseph Gollomb (story The Female of the Species in Saturday Evening Post)Julia Crawford Ivers (scenario)Produced byJesse L. LaskyStarringEthel ClaytonCinematographyJames Van TreesProductioncompanyFamous Players–LaskyDistributed byParamount PicturesRelease date December 7, 1919 (1919-12-07) (Limited) Running time50 minutes (5 reels)CountryUnited StatesLanguageSilent (English inter...

Hisaki (satellite)

Japanese satellite This article needs to be updated. Please help update this article to reflect recent events or newly available information. (August 2015) HisakiArtistic rendering of Hisaki in orbit.Mission typeUltraviolet astronomyOperatorJAXACOSPAR ID2013-049A SATCAT no.39253Websitewww.jaxa.jp/projects/sat/sprint_a/Mission duration~1 year planned (science phase) 10 years, 7 months and 15 days (achieved) Spacecraft propertiesBusNEXTAR NX-300LManufacturerNECLaunch mass348 ...

大字 (数字)

この項目には、一部のコンピュータや閲覧ソフトで表示できない文字が含まれています（詳細）。数字の大字（だいじ）は、漢数字の一種。通常用いる単純な字形の漢数字（小字）の代わりに同じ音の別の漢字を用いるものである。概要壱万円日本銀行券（「壱」が大字）弐千円日本銀行券（「弐」が大字）漢数字には「一」「二」「三」と続く小字と、「壱」「�...

الفتوحات الأفشارية في الخليج العربي وعمان

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (يوليو 2016) الفتوحات الأفشارية في الخليج العربي وعمان جزء من حروب نادر شاه بندر بوشهر تاريخيا يعتبر أحد أكثر المدن الساحلية أهمية في بلاد فارس في جميع أنحاء الخليج العر�...

Alphonse de Poitiers

Pour les articles homonymes, voir Alphonse, Poitiers, Alphonse de Toulouse et Toulouse (homonymie). Alphonse de Poitiers Le sceau d'Alphonse de Poitiers. Fonctions Comte de Poitiers 1241 – 21 août 1271(30 ans) Prédécesseur Jean sans Terre Successeur rattaché au royaume Comte consort de Toulouse 27 septembre 1249 – 21 août 1271(21 ans, 10 mois et 25 jours) Prédécesseur Sancie d'Aragon Successeur rattaché au royaume Biographie Dynastie Capétiens Date de naissan...

Archery at the 2022 Asian Games – Mixed team recurve

Mixed team recurve at the 2022 Asian GamesVenueFuyang Yinhu Sports CentreDates1–7 OctoberMedalists Lim Si-hyeonLee Woo-seok South Korea Satsuki NodaTakaharu Furukawa Japan Diananda ChoirunisaRiau Ega Agata Salsabilla Indonesia← 20182026 → Archery at the2022 Asian GamesRecurveIndividualmenwomenTeammenwomenmixedCompoundIndividualmenwomenTeammenwomenmixedvte Main article: Archery at the 2022 Asian Games The mixed t...

Anti-Yudaisme

Untuk kritikan cendekiawan terhadap Yudaisme, lihat Kritikan terhadap Yudaisme. Untuk penganiayaan Yahudi, lihat Antisemitisme. Bagian dari serial tentangAgama Yahudi Mazhab Ortodoks (HarediHasidikModern) Konservatif Reformasi (Klasik) Karaite Rekonstruksionis Pembaharuan Humanistik Haymanot Filsafat Prinsip kepercayaan Kabbalah Mesias Etik Bangsa pilihan Nama-nama Tuhan Gerakan Musar Pustaka Tanakh (TorahNevi'imKetuvim) Ḥumash Siddur Piyutim Zohar Rabbinik (TalmudMidrashTosefta) Syari...

Officine Motovilicha

Officine MotovilichaМотовилихинские заводыМOTZLogo panorama delle officine Stato Russia Forma societariaSocietà pubblica Fondazione1736 a Perm' Fondata daVasilij Nikitič Tatiščev Sede principalePerm' GruppoRostec SettoreDifesa Prodottiarmamenti, sistemi d'artiglieria, sistemi missilistici, prodotti metallurgici Dipendenti3.000 Sito webwww.mz.perm.ru Modifica dati su Wikidata · Manuale Le Officine Motovilicha (in russo Мотовилихински�...

Jerry Relph

American politician (1944–2020) Jerry RelphMember of the Minnesota Senatefrom the 14th districtIn officeJanuary 3, 2017 – December 18, 2020Preceded byJohn PedersonSucceeded byAric Putnam Personal detailsBorn(1944-09-04)September 4, 1944[1]Boston, Massachusetts, U.S.DiedDecember 18, 2020(2020-12-18) (aged 76)Saint Cloud, Minnesota, U.S.Political partyRepublican Party of MinnesotaSpouse(s) Colette (m. 1972; died 1999)...

Satrapes occidentaux

Satrapies occidentales (Ariaca) 35–405 Territoire approximatif des satrapes occidentauxInformations générales Capitale UjjainBarygaza Langue(s) Scythe Pali (alphabet kharosthi) Sanskrit, Prakrit (alphabet brahmi) peut-être grec (alphabet grec) Religion Hindouisme, Zoroastrisme, Bouddhisme Entités précédentes : Indo-Scythes Entités suivantes : Empire Gupta Peut-être vassaux de l'Empire Kouchan modifier - modifier le code - voir Wikidata (aide) Les Satrapes occidentaux, Ksh...

クレイジーアーケード

この記事のほとんどまたは全てが唯一の出典にのみ基づいています。他の出典の追加も行い、記事の正確性・中立性・信頼性の向上にご協力ください。出典検索?: クレイジーアーケード – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2023年5月) この記事は朝鮮語版の対応するページを翻訳す�...

English Civil War

Series of wars in England, 1642–1651 For other civil wars in England, see List of English civil wars. For other uses, see English Civil War (disambiguation). English Civil WarPart of the Wars of the Three KingdomsThe Battle of Naseby, 14 June 1645; Parliamentarian victory marked the decisive turning point in the English Civil War.DateAugust 1642 – September 1651LocationGreat BritainResult Parliamentarian victory Execution of Charles I Establishment of the Commonwealth of EnglandBelligeren...

火口のふたり

この項目には、一部のコンピュータや閲覧ソフトで表示できない文字（Microsoftコードページ932（はしご高））が含まれています（詳細）。火口のふたり著者白石一文発行日 2012年11月12日発行元河出書房新社ジャンル恋愛小説官能小説国日本言語日本語形態四六判ページ数 232公式サイト kawade.co.jpコード ISBN 978-4-309-02142-3 ISBN 978-4-309-41375-4（文庫本）ウィキポータル �...

Kayardild language

Australian Aboriginal language KayardildRegionSouth Wellesley Islands, north west Queensland, AustraliaEthnicityKaiadilt, YanggalNative speakers8 (2016 census)[1]Language familyMacro-Pama–Nyungan? TangkicKayardildDialects Kayardild Yangkaal[2] Language codesISO 639-3Either:gyd – Kayardildnny – Yangkaal/Nyangga (two different languages)Glottologkaya1318AIATSIS[3]G35 Kayardild, G37 YangkaalELPKayardild Yangkaal[4]Kaya...

بنو النضير

بنو النضير، هي قبيلة يهودية، كانت تسكن غرب شبه الجزيرة العربية، حتى القرن السابع الميلادي في المدينة المنورة (يثرب) بإقليم الحجاز، قام النبي محمد بن عبد الله، بطردهم من المدينة المنورة بعد أن قام بغزوهم.[1][2][3] لمحة تاريخية عاش «بنو النضير» في المدينة لقرون، ثم ...