Intersectia a doua poligoane convexe

[•popoiu.george]

Am gasit un algoritm ce foloseste intersectia unui semiplan determinat de latura unui poligon convex cu celalat poligon in "Programarea in limbajul C/C++ pentru liceu, vol. III", dar nu este si implementat.

Nu stiu cum sa implementez intersectia unei laturi cu un semiplan. As dori niste tips sau sa-mi explice cineva sau daca aveti vreun link bun, nu am nevoie de cod neaparat, poate doar pseudocod.

Mai stiu de un algoritm care are mai multi pasi :
- determini intersectiile dintre laturile celor doua poligoane si le retii
- determini varfurile unui poligon care sunt in interiorul celuilalt si le retii
- calculezi infasuratoarea convexa a punctelor retinute si obtii intersectia poligoanelor

"Nu imi place" pentru ca trebuie sa implementez defapt 3 algoritmi ca sa fac asta, sa nu mai vorbim de potentialele erori si de timpul de implementare.

Multumesc anticipat !

[•Cosmin]

Ai deja doua idei foarte simplu de implementat. Una in care doar trebuie sa manipulezi o lista circulara si alta in care trebuie sa folosesti algoritmul de infasuratoare care ar trebui sa il ai la degetul mic daca mergi la olimpiada. La geometrie daca nu esti sigur pe tine poti sa desenezi pe ecran ce face algoritmul la fiecare pas si atunci o sa fie mult mai usor sa scapi de buguri.

Bafta.

[•Cosmin]

Problema camera (http://infoarena.ro/problema/camera) pentru care sursele sunt deschise se rezolva cu ideea de taiere a unui poligon convex cu semiplane. Ai aici rezolvarea lui Bogdan http://infoarena.ro/job_detail/2310?action=view-source

[•popoiu.george]

Multumesc !

Am implementat pana la urma solutia pe care o stiam, dar nu strica niciodata sa stii sa rezolvi o problema prin mai multe metode.