Pentru a vă înregistra, vă rugăm să trimiteți un email către administratorul site-ului.
Pune o întrebare

3.6k intrebari

6.8k raspunsuri

15.5k comentarii

2.5k utilizatori

2 plusuri 0 minusuri
3.0k vizualizari
Un hexagon regulat are centrul în punctul H de coordonate (xH, yH). Latura hexagonului este a, iar orientarea lui este în așa fel încît două laturi sînt paralele cu axa Ox. Se mai dă și punctul P, la coordonatele (xP, yP).

Cunoscînd valorile numerice pentru xH, yH, a, xP, yP, cum se poate determina prin calcul dacă punctul P este în interiorul sau exteriorul hexagonului?

Cîștigă soluția care necesită cele mai puține operații numerice și deci este cea mai potrivită pentru programare.
Expert (12.9k puncte) in categoria Matematica

3 Raspunsuri

2 plusuri 0 minusuri
 Mai întâi câteva notații necesare și câteva observații utile.  
  
       Am considerat hexagonul în cadranul 1, pozitiv, al sistemului de coordonate, ceea ce nu reduce din generalitate. Notăm colțurile hexagonului începând cu cel dinspre axa y, în sens invers trigonometric, cu A, B, C, D, E și F. Notăm raza cercului circumscris, reprezentată de oricare din segmentele ce unesc centrul H cu unul din colțuri cu r. 
 Notăm intersecția segmentelor AD și BF cu G și intersecția AD și CE cu I. 
  
      Observăm că hexagonul regulat are unghiuri de 120 grade, iar triunghiurile formate de orice latură cu razele cercului circumscris care o subîntind sunt echilaterale, având ungiurile egale cu 60 grade. De aici rezultă că a=r. 
  
       Determinăm apotema hexagonului care este, în acest caz, m=a/(2tg30)=(a*sqrt3)/2. 
  
       Construim dreptunghiul BCEF a cărui lungime este dublul apotemei adică a*sqrt3 și a cărui lățime este egală cu a.  
  
 Voi determina condițiile pe care trebuie să le îndeplinească punctele din plan pentru a se situa în interiorul hexagonului. 
  
       1. Un punct e în interiorul dreptunghiului BCEF dacă și numai dacă pentru orice xP în intervalul xH-a/2<xP<xH+a/2, yP respectă condiția yH-(a*sqrt3)/2<yP<yH+(sqrt3)/2. Acest lucru se vede simplu din desen. 
  
       2. Pentru ca un punct să fie în interiorul triunghiului ABF, avem valorile lui xP în intervalul  
 xH-a<xP<xH-a/2. Observăm că unghiul ABF este egal cu 120-90=30 (grade). Variind pe x în intervalul considerat obținem triunghiuri asemenea cu ABG cu catetele  xP și yPmax. 
 Din tg30=xP/yPmax rezultă yPmax=xP*sqrt3. Procedând analog în triunghiulAGF rezultă că yPmax=2xP*sqrt3. 
       În final, pentru xH-a<xP<xH-a/2 avem yH-m<yP<2xPsqrt3 sau yH-(a*sqrt3)<yP<2xPsqrt3. 
  
       3. Asemănător, pentru ca un punct să fie în interiorul triunghiului CDE, xP ia valori în intervalul  xH+a/2<xP<xH+a. Variind pe x in sens pozitiv obținem triunghiuri asemenea cu CDI în care tg30=(xH+a-xP)/yPmax. Luând în considerare și triunghjul IDE, rezultă că valoarea maximă a lui yP este yPmax=2(xH+a-xP)sqrt3. 
       În final, pentru xH+a/2<xP<xH+a avem yH-(a*sqrt3)/2<yP<2(xH+a-xP)sqrt3. 
  
 Rezumând, 
       1. Pentru xH-a/2<xP<xH+a/2 trebuie ca  yH-(a*sqrt3)/2<yP<yH+(a*sqrt3)/2; 
       2. Pentru xH-a<xP<xH-a/2     trebuie ca  yH-(a*sqrt3)/2<yP<2xP*sqrt3; 
       3. Pentru xH+a/2<xP<xH+a   trebuie ca  yH-(a*sqrt3)/2<yP<2(xH+a-xP)*sqrt3. 
  
  
    
  
  
        
Senior (6.6k puncte)
0 0
Mulțumesc. Altfel spus ați împărțit suprafața hexagonului în trei zone (un dreptunghi și două triunghiuri) și verificați dacă punctul P se află în vreuna din ele. Soluția e bună, cu observația minoră că unele din acele inegalități trebuie să includă și egalitatea. De exemplu, dacă xP este exact egal cu xH+a/2 punctul P pare să fie în exteriorul hexagonului indiferent cît e yP, pentru că lipsește semnul egal din formule. Altfel soluția funcționează.

Dar mi se pare puțin cam muncitorească, atît pentru dumneavoastră cît și pentru implementarea într-un program. Există soluții mai simple, care au și avantajul suplimentar că se pot generaliza ușor pentru cazul în care hexagonul e orientat altfel.
1 0
 Da, și eu am impresia că am folosit forța brută, a fost prima abordare care mi-a venit în minte.  
  
0 0
 În soluția dată, atunci când l-am situat pe xP între xH-a/2 și xH+a/2 (punctul 1 din rezumatul final),  am omis să menționez că intervalul este închis, neavând taste pentru "mai mare sau egal" și "mai mic sau egal". De asemenea, la același punct, am omis să specific că valorile permise ale lui yP se află tot în interiorul unui interval închis. Așa încât, punctele xH-a/2 și xH+a/2 au rămas total în afară, intervalul total al valorilor lui xP având două discontinuități. 
  
 Pe de altă parte, încerc să folosesc anumite proprietăți de simetrie ale hexagonului regulat pentru o solutie care să prezinte și avantajul că se poate generaliza ușor pentru orice poziție a acestuia, dar nu reușesc și, cel puțin intuitiv, nu văd cum aș putea reduce numărul de operații numerice. 
  
  
  
   
0 0
Problema se poate simplifica. Un hexagon regulat poate fi considerat ca suprapunere a trei dreptunghiuri cu doua laturi comune cu laturile opuse ale hexagonului. Un punct este in afara hexagonului daca este in afara tuturor celor trei dreptunghiuri. Se scrie conditia o singura data in program si se ruleaza de trei ori.
0 0
@puriu.

Si va ies operatii mai putine cand puneti conditiile ca punctul P sa nu fie continut in niciunul dintre dreptunghiuri?

Iar in ideea unei generalizari pentru orice orientare a hexagonului, ar trebui un parametru care sa inlocuiasca ipoteza initiala a problemei, aceea ca hexagonul e orientat astfel incat doua laturi sa fie paralele cu axa x.
0 0
Puriu s-a apropiat mult de soluția mea. Ca să vă faceți o idee, tocmai am scris o rutină care calculează dacă punctul e interior sau nu (pe baza soluției mele) și are numai 4 linii de cod. Recunosc că asta mă surprinde pînă și pe mine. Mai mult, rutina nu conține nici un if și nici un apel la vreo altă subrutină, ci doar calcule efective, și permite orice orientare, poziție și mărime a hexagonului. Impune doar ca hexagonul să fie regulat.
0 0

Poate vă ajută informația că problema cu distanța dintre un punct și o dreaptă este de fapt un indiciu pentru problema de față.

0 0
 Am rezolvat problema cu distanța dintre un punct și o dreaptă și am obținut coordonatele lui T în funcție de coordonatele lui D și P și depinzând de unghiul a prin funcții trigonometrice altele decât tangenta care ridica mici probleme în pi/2. 
 Dar poate azi, mai târziu, voi avea timp să postez răspunsul, bineînțeles dacă nu dă cineva răspunsul corect între timp. 
 Văzând comentariile de deasupra am înțeles și legătura dintre probleme. 
0 plusuri 1 minus
Uite cum as face eu pentru numar minim de calcule,printr-o metoda euristica:

1.Fac din hexagon o alta structura virtuala patrat si vad daca se incadreaza in patrat. folosind latura si inaltimea pot desena dpdv logic un patrat care sa il cuprinda ,suprapunandu-se cu laturile paralele cu OX, si trecand prin colturile din stanga si dreapta .sa Daca nu se incadreaza, atunci STOP.Daca da, merg mai departe

2. Calculez  in ce parte a Hexagonului fata de intersectia in forma de + din mijloc se afla( in ce cadran) .

3. Dupa ce am aflat in care din cele 4, impart spatiul ramas liber dintre hexagon si patrat in 2 triunghiuri si salvez coordonatele.

5.Daca punctul nu se incadreaza in coordonatele respective, atunci e in hexagon, daca da, atunci STOP si nu se incadreaza.

Eu asa as face, daca ai alte intrebari pune-le aici
Novice (301 puncte)
0 0
Iertați-mă, nu se înțelege mai nimic. Cum faceți din hexagon un pătrat? Mai departe cu cadranul și coordonatele n-am înțeles nimic. În plus nu dați nici o formulă de calcul.
1 plus 0 minusuri

Iată și soluția mea, acum după ce știm să determinăm distanța dintre un punct și o dreaptă.

Ideea este că hexagonul are trei diagonale principale (și șase secundare) și că nici un punct din interiorul hexagonului regulat nu se poate afla față de o diagonală principală la o distanță mai mare decît o anumită limită, care este lungimea apotemei. Un punct exterior se află la o distanță mai mare decît apotema de cel puțin una din cele trei diagonale principale.

Pentru a rezolva problema calculez distanțele de la punctul P la următoarele drepte, care sînt suporturile diagonalelor principale, definite prin faptul că trec prin centrul hexagonului:

x = xH + t * cos(u1,2,3)
y = yH + t * sin(u1,2,3)

unde u1, u2, u3 sînt unghiurile făcute de diagonale cu axa Ox, adică u1 = 0, u2 = pi/3, u3 = 2pi/3.

Iată și formulele pentru a calcula cele trei distanțe:

d1 = |(xP-xH)*sin(u1)-(yP-yH)*cos(u1)|
d2 = |(xP-xH)*sin(u2)-(yP-yH)*cos(u2)|
d3 = |(xP-xH)*sin(u3)-(yP-yH)*cos(u3)|

Ca ultim pas verific dacă toate cele trei distanțe sînt toate mai mici decît lungimea apotemei, adică a*sqrt(3)/2. Cu asta problema de matematică e rezolvată.

În ce privește programarea, calculul arată astfel (în funcție și de limbajul folosit, Matlab în exemplul meu):

d1=abs((xp-xh)*sin(u0)-(yp-yh)*cos(u0));
d2=abs((xp-xh)*sin(u0+pi/3)-(yp-yh)*cos(u0+pi/3));
d3=abs((xp-xh)*sin(u0+2*pi/3)-(yp-yh)*cos(u0+2*pi/3));
b=(d1<a*sqrt(3)/2)*(d2<a*sqrt(3)/2)*(d3<a*sqrt(3)/2);

unde u0 este orientarea hexagonului (u0=0 în cazul hexagonului din enunț), iar variabila b este booleană: adevărată dacă punctul P este în hexagon și falsă altfel. Deci tot calculul se face în 4 linii de cod, care mai pot fi simplificate, dar le-am lăsat așa pentru claritate. În plus, într-un limbaj ca Matlab care lucrează ușor cu vectori, de fapt toată rutina se poate scrie într-o singură linie de cod:

b=sum(abs((xp-xh)*sin(u0+pi/3*(0:2))-(yp-yh)*cos(u0+pi/3*(0:2)))<a*sqrt(3)/2)==3;

 

Expert (12.9k puncte)
...