Punct in interiorul unui triunghi

Se da un triunghi prin coordonatele varfurilor. Se cere sa se afiseze pentru un set de N puncte din plan daca apartin sau nu interiorului triunghiului. Pentru a rezolva aceasta problema, sa consideram triunghiul ABC si punctul P, interior acestuia.

Observam ca vectorii ( AB, BP ), ( BC, CP ), ( CA, AP ) vor realiza mereu acelasi tip de intoarcere (in acest caz spre stanga). De aceea, determinantii:

det( ((xA,yA,1),(xB,yB,1),(xP,yP,1)) ), det( ((xB,yB,1),(xC,yC,1),(xP,yP,1)) ), det( ((xC,yC,1),(xA,yA,1),(xP,yP,1)) )
cotizo - :) trebuie LaTeX :)

trebuie sa aiba acelasi semn. In caz contrar, P este in exteriorul triunghiului. In imaginea precedenta, se observa ca in cazul punctului P', vectorii BC, CP fac o intoarcere la dreapta, deci determinantul corespunzator nu va avea acelasi semn cu ceilalti doi.

Aceasta idee poate fi generalizata pentru a fi determina daca un punct se afla in interiorul unui poligon convex in O(N). Mai exact se calculeaza det( (xi,yi,1), (xi+1, yi+1, 1) (xp,yp,1) ) pentru i luand valori de la 1 la N (cand i==N vom considera i+1=1) . Punctul P(xp,yp) se afla in interiorul poligonului daca si numai daca toti determinanti au acelasi semn. ( "+" daca parcurgem poligonul in sens direct trigonometric, "-" altfel)

Punct in interiorul unui poligon oarecare

Se da un poligon oarecare cu N varfuri si un punct P prin coordonatele carteziene. Se cere sa se determine daca punctul P este in interiorul sau in exteriorul poligonului.

Se va trasa o semidreapta orizontala cu originea in punctul P. Daca aceasta semidreapta intersecteaza un numar impar de muchii ale poligonului, atunci punctul se afla in interiorul acestuia. Mentionam ca trebuie avut in vedere cazul in care semidreapta trece chiar printr-un varf de poligon (capat a doua muchii). Vom considera imaginea urmatoare:

In cazul punctului P1, respectiv P2, semidreptele intersecteaza 3, respectiv 1 latura (numere impare) deci punctele se afla in interior. Semidreapta corespunzatoare lui P3 intersecteaza o latura si un varf de poligon. Pentru a rezolva acum aceasta problema, o solutie ar fi ca in loc sa alegem semidreapta orizontala, sa luam o semidreapta random, astfel posibilitatea ca ea sa intersecteze varfurile poligonului tinde spre 0. O alta solutie posibila - si mai usor de implementat - este sa consideram ca facand parte dintr-o latura doar punctul cu coordonata y mai mare. Se garanteaza astfel ca laturile care contin punctul de pe semidreapta vor fi numarate de numar par de ori (2 pt punctul de sus, 0 pt punctul de jos) si ca, implicit, nu vor afecta corectitudinea algoritmului.

devilkind - am dat eu o solutie care merge destul de bine ptr cazul in care semidreapta orizontala intersecteaza varfuri insa e cam jegoasa asa (cu semidrepte random si e cam aiurea). Era un smen in care considerai ca numai un capat al laturii face parte din ea, dar nu mai stiu cum era.
EDIT Gcosmin (tip) : in cazul in care semidreapta aleasa (sa zicem ca e paralela cu OX (e bine sa fie asa)) trece fix prin varful unui segment din poligon atunci segmentul il numaram doar daca semidreapta aleasa trece prin varful cu y-u mai mare. chestia asta scoate cazurile particulare si merge (da niste exemple si o sa vezi). e total aiurea sa iei o dreapta random pentru ca se complica mult treaba aiurea.
cotizo - multumim mult :) orice ajutor e binevenit :D pastram ambele variante pt ca si eu in concurs as fi bagat un random.

Punct in poligon convex

Enunt: Se da un poligon convex cu N laturi si apoi M interogari caracterizate prin coordonatele unui punct P, iar dumneavoastra trebuie sa determinati rapid daca punctul respectiv se afla sau nu in interiorul poligonului.

Solutia 1

Se ia un varf al poligonului, si se traseaza cele n-3 diagonale care pornesc din el. Astfel poligonul nostru se imparte in mai multe triunghiuri. Vom adauga intr-un vector aceste drepte plus cele 2 laturi care au originea in varful ales de noi si le sortam dupa panta. Cand primim un query vom cauta binar dupa panta si vom afla intre ce diagonale se incadreaza acesta si verificam daca punctul nostru se afla sau nu in triunghiul respectiv.

Sa luam un exemplu:

In imaginea de mai sus punctele P1,..P6 reprezinta varfurile poligonului iar punctele P7, P8, P9 reprezinta interogarile. Cu rosu sunt trasate diagonalele care delimiteaza sectoarele, si le vom tine ca drepte, sortate dupa panta, impreuna cu dreptele suport pentru cele 2 laturi care au un capat in punctul P1. Astfel cand primim o interogare vom putea cauta binar si sa aflam in ce sector se afla acesta. Pentru punctul P8 spre exemplu ne vom da seama ca se afla in sectorul determinat de diagonalele care corespund punctelor P4 si P5. Astfel vom verifica daca punctul P8 se afla in interiorul triunghiului determinat de punctele P1, P4, P5. Vom proceda asemanator si pentru celelalte interogari cu mentiunea ca trebuie sa avem grija la cazurile in care punctul nu se afla in nici unul din sectoare (P9), insa asta se poate face usor cu o verificare inainte de a porni cautarea binara.

Aceasta solutie are complexitate O(NlogN + MlogN).

Solutia 2

O alta solutie este sa impartim planul in fasii. Astfel din fiecare varf al poligonului vom trasa o dreapta verticala. Acum pentru 2 drepte consecutive vom lua laturile care il intersecteaza si le vom sorta crescator dupa y (e clar ca aceste laturi nu se intersecteaza deci putem alege orice punct de pe latura si sa sortam dupa y-ul acestuia). Acum pentru a raspunde la interogari, vom face 2 cautari binare. Vom cauta odata sa vedem in ce fasie se incadreaza punctul nostru, iar apoi vom cauta inca odata binar sa vedem cate laturi din acea fasie sunt au y-ul mai mic decat punctul nostru. Daca acest numar este impar atunci punctul este in interior, altfel este in exterior. De mentionat ca aceasta solutie se poate aplica si la poligoane concave, de altfel in cazul poligoanelor convexe nu pot fi decat 2 laturi pe o fasie si nu ar mai fi nevoie de a doua cautare binara.

Sa luam un exemplu:

Observam cu rosu dreptele care delimiteaza fasiile verticale. De asemenea vedem ca punctul P6 are in fasia lui 2 laturi cu y-ul mai mic ca al lui si este in afara poligonului, spre deosebire de punctul P7 care are o singura latura cu y-ul mai mic ca al sau si este in interior.
Avantajul acestei metode este ca functioneaza si in cazul poligoanelor concave, insa are dezavantajul faptului ca pot exista interogari in care punctele sa se afle pe dreapta care delimiteaza fasiile. Practic aceasta metoda este echivalenta cu metoda explicata mai sus, pentru a verifica daca un punct se afla sau nu in interiorul unui poligon oarecare.
In cazul poligoanelor convexe complexitatea este aceeasi ca si la metoda de mai sus, insa in cazul poligoanelor concave complexitatea teoretica e O(N^2 log N + M log N). Acest algoritm poate fi aplicat in rezolvarea problemei poligon din arhiva de probleme.

devilkind uitativa putin la solutia asta ptr ca nu sunt foarte sigur pe complexitati - in special cand e vb de poligoane concave. Mie mi se pare ca aia e complexitatea insa e posibil sa ma insel
cotizo da e corect - asta e si rezolvarea problemei "poligon"