Sa luam un exemplu:
!notiuni-de-geometrie-si-aplicatii?polig1!

In imaginea de mai sus punctele $P{~1~}$,..{$P{~6~}$} reprezinta varfurile poligonului iar punctele $P{~7~}$, $P{~8~}$, $P{~9~}$ 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 $P{~1~}$. Astfel cand primim o interogare vom putea cauta binar si sa aflam in ce sector se afla acesta. Pentru punctul $P{~8~}$ spre exemplu ne vom da seama ca se afla in sectorul determinat de diagonalele care corespund punctelor $P{~4~}$ si $P{~5~}$. Astfel vom verifica daca punctul $P{~8~}$ se afla in interiorul triunghiului determinat de punctele $P{~1~}$, $P{~4~}$, $P{~5~}$. 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, insa asta se poate face usor cu o verificare inainte de a porni cautarea binara.

In imaginea de mai sus punctele $P{~1~}$,..{$P{~6~}$} reprezinta varfurile poligonului iar punctele $P{~7~}$, $P{~8~}$, $P{~9~}$ 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 $P{~1~}$. Astfel cand primim o interogare vom putea cauta binar si sa aflam in ce sector se afla acesta. Pentru punctul $P{~8~}$ spre exemplu ne vom da seama ca se afla in sectorul determinat de diagonalele care corespund punctelor $P{~4~}$ si $P{~5~}$. Astfel vom verifica daca punctul $P{~8~}$ se afla in interiorul triunghiului determinat de punctele $P{~1~}$, $P{~4~}$, $P{~5~}$. 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, 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:
 

h1. TODO