|
Titlul: Cercuri + Poligoane Scris de: Ungureanu Daniel din Aprilie 19, 2008, 23:17:11 Mai am si eu niste intrebari :D. Cum se realizeaza urmatoarele probleme???
Intersectia a doua cercuri Centrul de greutate al unui poligon Intersectie de poligoane convexe Va multumesc anticipat. Titlul: Răspuns: Cercuri + Poligoane Scris de: Alina Ene din Aprilie 19, 2008, 23:49:05 1. Cu putina algebra. Daca vrei sa simplifici calculele, poti sa schimbi sistemul de coordonate astfel incat unul din cercuri sa aiba centrul in origine.
2. Google is your friend. De ex, http://local.wasp.uwa.edu.au/~pbourke/geometry/polyarea/ 3. Ditto. Pagina aceasta de ex. descrie the method of rotating calipers (nu imi mai amintesc daca algoritmul are un nume, eu il numesc asa pentru ca foloseste rotating calipers ca sa afle convex hull-ul (infasurarea convexa?)) http://www.iro.umontreal.ca/~plante/compGeom/algorithm.html Titlul: Răspuns: Cercuri + Poligoane Scris de: Cosmin Negruseri din Aprilie 20, 2008, 03:51:11 1. http://local.wasp.uwa.edu.au/~pbourke/geometry/2circle/ uite aici al 2-lea rezultat de pe google e destul de bine explicat
2. http://www.faqs.org/faqs/graphics/algorithms-faq/ Gasesti aici si explicatie la formula centroidului. Si aici o explicatie ceva mai buna zic eu la formula ariei http://geometryalgorithms.com/Archive/algorithm_0101/ 3. Chestia cu pointerii ce fug unul dupa altul (cred ca la asta te referi cand zici de rotating calipers), e nasol de implementat sa scapi de cazuri simple in implementare. Cel putin pentru dreptunghiuri nu am reusit sa fac sa nu cicleze la infinit. Implementam asta acum 8 ani deci probabil acuma daca as implementa mi-ar iesi. Algoritmul respectiv e O(n + m) dar in concursuri nu cere nimeni asa ceva. Era un articol vechi in ginfo cu algoritmul asta http://www.ginfo.ro/9_8/061.shtml Un algoritm simplu ar fi sa implementezi intersectia de un semiplan cu un poligon convex. Poti face asta se face foarte simplu cu o lista dublu inlantuita. O intersectie dureaza O(n) is cum trebuie sa faci m intersectii algoritmul final va fi O(nm). Alt algoritm ce il foloseam pana sa ajung la idea de intersectie de semiplan cu poligon convex era urmatorul: - gasesti toate intersectiile intre laturile celor doua poligoane O(n * m) - gasesti punctele dintr-un poligon ce sunt in interiorul celuilalt O(n * m) sau O(n log m + m log n) - faci infasuratoarea convexa a punctelor rezultate din cei doi pasi mai sus O( (n + m) log (n + m) ) si asta e intersectia celor doua poligoane asta e mai nasol ca trebuie sa implementezi pe langa intersectie de segmente si punct interior unui poligon si infasuratoare convexs |