Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Da li duž seče pravougaonik?

[es] :: Art of Programming :: Da li duž seče pravougaonik?

[ Pregleda: 5626 | Odgovora: 12 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

Predrag Damnjanovic
Predrag Damnjanovic
Nis, Srbija

Član broj: 141
Poruke: 1305
*.verat.net

Sajt: www.mycity.rs


+1 Profil

icon Da li duž seče pravougaonik?04.12.2003. u 05:04 - pre 247 meseci
Imam jedan geometrijsko-programerski problem.

Imam jedan pravougaonik, i jednu duž, čije se tačke nalaze izvan tog pravougaonika.
Poznate su naravno sve tačke, i pravougaonika, i duži.

Trebam nekako da ispitam da li ta duž seče pravougaonik.
Znači. tačke duži mogu da budu svuda oko pravougaonika, i duž može da seče taj pravougaonik, a i ne mora.
Koordinate pravougaonika i duži su naravno promenjive.

Treba mi dakle algoritam, ili barem neko matematičko rešenje, ako postoji negde, pošto pretpostavljam da je neko već imao potrebu za takvim algoritmom.

P.S. Nije u pitanju neko cimanje za školu/fax, ovo mi stvarno treba, za jednu relativno ozbiljnu aplikaciju.
 
Odgovor na temu

degojs

Član broj: 4716
Poruke: 5096



+51 Profil

icon Re: Da li duž seče pravougaonik?04.12.2003. u 05:45 - pre 247 meseci
U biti treba da proveriš da li se tvoja duž seče sa nekom od duži koje su stranice poligona.

Koristi jednačinu prave kroz dve tačke i to za tvoju duž i za svaku stranicu poligona (pravougaonika). Prostim izjednačavanjem jednačine prave na kojoj je tvoja duž sa svakom od jednačina pravih na kojima su stranice i rešavanjem po x (i y) dobićeš koordinate preseka pravih. Naravno dalje proveri da li se tačka preseka nalazi na tvojoj duži i određenoj stranici.

Jednačina prave kroz 2 tačke je ako se sećam više dobro:
y - y1 = ( (y2-y1)/(x2-x1) ) (x-x1)

Dakle pomoću gornje formule i tačaka A(x1,y1) i B(x2,y2) koje definišu duž nađeš jednačinu prave na kojoj je tvoja duž, npr:
y = ax + b

i onda isto tako pomoću one formule nađi jednačinu prave na kojoj je prva stranica (stranica je isto duž, je li):
y = a1x + b1

Izjednači ax + b = a1x + b1 i videćeš da li prava na kojoj je tvoja duž negde seče pravu na kojoj je prva stranica poligona, a onda tako i za ostale. Kako rekoh, kad nađeš presek, samo proveri da je na traženoj duži i stranici.

Mislim da to može tako :-)


/edit: hehe, mala optimizacija bi bila da proveriš da li je a = a1. Ako jeste, onda su prave paralelne pa se duži ne seku osim možda ako nisu baš na istoj pravoj.. A ako tvoja duž ne seče jednu stranicu odmah znaš da ne seče ni suprotnu pošto su paralelne (u slučaju pravougaonika).. detalji..
Commercial-Free !!!
 
Odgovor na temu

Časlav Ilić
Braunšvajg, Nemačka

Član broj: 4945
Poruke: 565
217.26.67.*



+27 Profil

icon Re: Da li duž seče pravougaonik?04.12.2003. u 07:49 - pre 247 meseci
Meni je trebalo nešto slično, pogledaj temu http://www.elitesecurity.org/tema/23457/ (ima tamo i nekog kôda, možda ti posluži).
 
Odgovor na temu

mucky
Aleksandar Mastilović
Freelancer
Novi Sad - Srbija

Član broj: 237
Poruke: 412
*.lar.sch.gr



+1 Profil

icon Re: Da li duž seče pravougaonik?04.12.2003. u 07:53 - pre 247 meseci
degojs, tvoje resenje radi samo kada su u pitanju prave, a ne i duzi. Sta ako je npr.
trazena duz unutar pravougaonika, a ne sece ni jednu stranicu? Po tvom algoritmu
ispalo bi da ona sece dve stranice pravougaonika (koje takodje smatras za prave)
a to jednostavno nije tacno...
 
Odgovor na temu

degojs

Član broj: 4716
Poruke: 5096



+51 Profil

icon Re: Da li duž seče pravougaonik?04.12.2003. u 08:06 - pre 247 meseci
mucky, rekoh gore dva puta: kada se nađe tačka preseka pravih potrebno je proveriti da li se nalazi na potrebnim dužima (tj. na duži i na određenoj stranici). To valjda nije teško. Ne vidim da je algoritam neispravan.. mada, naravno, moguće je da grešim.


Čak i da nije tako, Predrag je rekao:
Citat:
Imam jedan pravougaonik, i jednu duž, čije se tačke nalaze izvan tog pravougaonika.

Commercial-Free !!!
 
Odgovor na temu

mucky
Aleksandar Mastilović
Freelancer
Novi Sad - Srbija

Član broj: 237
Poruke: 412
*.lar.sch.gr



+1 Profil

icon Re: Da li duž seče pravougaonik?04.12.2003. u 08:35 - pre 247 meseci
Izvini, nisam video da si to napisao :) A ono sto sam rekao za duz unutar pravougaonika
je trebalo da posluzi samo kao jasan primer kada algoritam ne radi :)
 
Odgovor na temu

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.et.tudelft.nl

Jabber: filmil@jabber.org
ICQ: 36601391


+3 Profil

icon Re: Da li duž seče pravougaonik?04.12.2003. u 08:53 - pre 247 meseci
Citat:
degojs:
Koristi jednačinu prave kroz dve tačke i to za tvoju duž i za svaku stranicu poligona ....Jednačina prave kroz 2 tačke je ako se sećam više dobro:
y - y1 = ( (y2-y1)/(x2-x1) ) (x-x1)


Ovo nije baš dobro rešenje jer se koristi jednačina koja ima singularitet kada je x2==x1 i ima numeričkih problema kada je sistem jednačina slabo uslovljen, dakle kada je x2 blizu x1.

Na temi http://www.elitesecurity.org/tema/23457 možeš pogledati (krajnje subjektivno) malo bolji način, sa sve matematikom.

f
 
Odgovor na temu

idb
Ivan Bulic
Beograd

Član broj: 4436
Poruke: 402



Profil

icon Re: Da li duž seče pravougaonik?04.12.2003. u 10:23 - pre 247 meseci
Kako rece filmil 01.06.2003.:
Citat:

Jednostavan način da se utvrdi da li se dve duži seku je da se ispita
položaj krajnjih tačaka jedne duži u odnosu na drugu duž. Preseka ne
može biti ako obe krajnje tačke leže sa iste strane duži.

Ima tome jedno 10 godina kako je u tadasnjim casopisu "Racunari" (neka mi autor teksta oprosti - ime sam zaboravio)

bio resavan slican problem, a ja sam koju godinu kasnije imao prakticne potrebe da to sprovedem u delo.

Prvi deo problema je:
1. Da li se duzi AB(x1,y1, x2,y2) i CD(x3,y3, x4,y4) seku?
Evo tadasnjeg resenja u Turbo Pascalu:
Code:

Function Cross(x1,y1,x2,y2,x3,y3,x4,y4:Real):Boolean;
Var A1,B1,C1,A2,B2,C2:Real;
Begin
  A1:=Y2-Y1; A2:=Y4-Y3; B1:=X2-X1; B2:=X4-X3;
  C1:=(X1*Y2)-(X2*Y1); C2:=(X3*Y4)-(X4*Y3);
  Cross:=(((A1*X3-B1*Y3-C1>0) Xor (A1*X4-B1*Y4-C1>0)) And
          ((A2*X1-B2*Y1-C2>0) Xor (A2*X2-B2*Y2-C2>0)));
End;


A evo sada i ceo program u C++:
Code:

#include <iostream>
#include <stdlib.h>
using namespace std;

bool Cross1(double x1,double y1,double x2,double y2, double x3,double y3,double x4,double y4);

int main(int argc, char *argv[])
{
  if (Cross1(2,4,5,1, 2,2,4,6)) cout<<"Seku se!\n\n"; else cout<<"NE seku se!\n\n";
  if (Cross1(2,4,5,1, 5,3,8,6)) cout<<"Seku se!\n\n"; else cout<<"NE seku se!\n\n";
  system("PAUSE");    
  return 0;
}

bool Cross1(double x1,double y1,double x2,double y2,double x3,double y3,double x4,double y4){
  double a1,b1,c1,a2,b2,c2;
  a1=y2-y1; a2=y4-y3; b1=x2-x1; b2=x4-x3;
  c1=(x1*y2)-(x2*y1); c2=(x3*y4)-(x4*y3);
  cout<<"AB: "<<x1<<"\t"<<y1<<"\t"<<x2<<"\t"<<y2<<endl; //ovo mozes izbaciti
  cout<<"CD: "<<x3<<"\t"<<y3<<"\t"<<x4<<"\t"<<y4<<endl; //ovo mozes izbaciti
  if ( ( ((a1*x3-b1*y3-c1)>0)||((a1*x4-b1*y4-c1)>0) ) &&  
     ( ((a2*x1-b2*y1-c2)>0)||((a2*x2-b2*y2-c2)>0)) ) return true; 
    else return false;
}

Ovo ce ti kao rezultat ispisati:
AB: 2 4 5 1
CD: 2 2 4 6
Seku se!

AB: 2 4 5 1
CD: 5 3 8 6
NE seku se!

Press any key to continue . . .


Pa ti sad prodji kroz sve stranice pravougaonika, pa proveri..
Ako je uslov preseka da duz preseca pravougaonik ispunjen samo ako se oba temenae duzi nalaze van pravougaonika onda preboj broj preseka.
- Ako je paran onda se oba temena duzi nalaze van pravougaonika
- Ako je neparan onda je jedna tacke unutar pravougaonika.
- Ako je broj preseka == 0, onda naravno nema preseka...

Ovo ti inace vazi za sve poligone, a ne samo za pravougaonik.


 
Odgovor na temu

Predrag Damnjanovic
Predrag Damnjanovic
Nis, Srbija

Član broj: 141
Poruke: 1305
*.verat.net

Sajt: www.mycity.rs


+1 Profil

icon Re: Da li duž seče pravougaonik?04.12.2003. u 13:44 - pre 247 meseci
Hvala puno, ustedeli ste mi sate i sate, mozda i dane :)
 
Odgovor na temu

Mihailo Kolundzija
Novi Sad

Član broj: 11323
Poruke: 100
*.ftn.ns.ac.yu



+1 Profil

icon Re: Da li duž seče pravougaonik?04.12.2003. u 15:55 - pre 247 meseci
Samo jedna mala ispravka u vezi onog C++ koda - u funkciji "Cross1" treba koristiti iskljucivu disjunkciju umesto obicne, sto ce reci "^" umesto "||".
 
Odgovor na temu

leka
Dejan Lekić
senior software engineer, 3Developers
Ltd.
London, UK

Član broj: 234
Poruke: 2534
*.telia.com

Sajt: dejan.lekic.org


+2 Profil

icon Re: Da li duž seče pravougaonik?07.12.2003. u 12:05 - pre 247 meseci
U principu bi ovaj problem trebalo da se svede na ispitivanje da li data duz sece odgovarajucu dijagonalu pravougaonika...
Dejan Lekic
software engineer, MySQL/PgSQL DBA, sysadmin
 
Odgovor na temu

Predrag Damnjanovic
Predrag Damnjanovic
Nis, Srbija

Član broj: 141
Poruke: 1305
*.dial.InfoSky.Net

Sajt: www.mycity.rs


+1 Profil

icon Re: Da li duž seče pravougaonik?07.12.2003. u 23:27 - pre 247 meseci
da, tako imamo samo 2 duzi (dijagonale) da ispitamo, a ne sve 4 stranice...
 
Odgovor na temu

dust
Dušan Stefanović

Član broj: 9827
Poruke: 33
*.rcub.bg.ac.yu



Profil

icon Re: Da li duž seče pravougaonik?09.12.2003. u 05:34 - pre 247 meseci
Možeš da probaš Janičićevu skriptu iz grafike (http://www.matf.bg.ac.yu/~janicic negde pri dnu strane). Tu je teorijski objašnjeno, mada teško da ćeš imati neke vajde od koda u skripti. Na Samardžievom sajtu (http://www.matf.bg.ac.yu/r4rg odeljak predavanja) imaš stvarnu implementaciju.
 
Odgovor na temu

[es] :: Art of Programming :: Da li duž seče pravougaonik?

[ Pregleda: 5626 | Odgovora: 12 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.