Computational Geometry
De Pontão Nós Digitais
Ir para navegaçãoIr para pesquisar
////////// Under Construction //////////
This is the main page of a graduate level course in computational geometry being taught in 2019/2 at the Polytechnic Institute IPRJ/UERJ. It is generally useful for programmers at the advanced level in the fields of machine learning, scientific simulations, graphics, computer vision and and multimedia programming.
General Info
- Instructor: prof. Ricardo Fabbri, Ph.D. Brown University
- Meeting times: Wednesdays 7:50-11:30, Thursdays 7:50-9:40, and 15:00-17:00, room 110.
- Evaluation criteria: at least 2 quizzes (40%), practical projects (60%).
- Forum for file exchange and discussion: email and IRC #labmacambira
Lecture Log
Part 1: C++ Programming Practice and Review
Wed 9Out19 (twice lecture load)
- Hello world
- for loop print 10x
- Slides 1 Review C Fabbri
- Variables, arrays/vectors
- Farenheit to/from celcius program: homework
Wed 16Oct19
- Show results of Farenheit to Celsius
- Learn Codeblocks
Thu 17Oct19
- Print function graph (K&R Histogram)
- Horizontal
- Learn how to write max function: non-recursive and recursive
- Learn first simple sort algorithm using max
- Horizontal
Wed 23Out19 (twice lecture load)
- Due: simple sort using max
- bucket sort (class exercise). Due. (student juliana: done)
- Other simple sorts. Insertion, selection, bubble
- Basic building block: insert on sorted array, keeping it sorted
- Theory: arrays.
Thu 24Out19
- Overdue: simple sort using max
- Did: used max function
- at first, max function without index
- Sub-exercise: implement max of an array to return index, recursive and non-recursive
- did: sort with max function, with index
- at first, max function without index
- Question: does it work with repeated entries?
- If you have a vector of float height[num_people] and age[num_people], and there is a repeated age, can you print ages and respective heights sorted by age, without losing information?
- What is a stable sort
- Did: used max function
- Vector and cross product exercise
- Exercise from qualify
- Sort building blocks
Wed 30Out19
- Overdue: Vertical Function graph (K&H Histogram)
- Due: Insert on sorted array (Juliana: 9,5)
- Due: Merge two sorted arrays as warmup for next lecture (Juliana: 5)
- Due: Simple sort by recursive and non-recursive max is stable? argue in PDF (Juliana 0)
- Content
- Reviewed due homework
- Pointers, references
- Arrays and pointers
- Matrices as multidimensional arrays. Pointers.
- Malloc for arrays and matrices
- Structs
- Void *
- Pointers to functions
Thu 31Out19
- Due: better sorted insert
- Due: max() in vertical histogram
- Due: more efficient merge
- Bitwise operators. Modulo operator.
- Excercises: one regarding Matrices, another regarding number and bit manipulation.
- Image lookup table for sorting intensities
Wed 13Out19
- Exam: programming fundamentals
Future
- Intro to advanced sorts: Merge sort, Quick Sort
- Basic building blocks:
- merge: merge two sorted arrays into a sorted array.
- partition an arbitrary array into smaller and larger than a given t
- Basic building blocks:
Tasks + Homework
Part 1: C++ Programming practice and Review
Hello World
Celsius to/from Farenheit
Print Function graph (K&R Histogram): horizontally
- Sub exercise: max function
Implement max function recursively
Sort using max function
Print Function graph (K&R Histogram): vertically
Bucket sort
Vector and cross product exercise
- Exercise from qualify
Dados 2 vetores de inteiros A=[a1,a2,a3] e B=[b1,b2,b3] :
- Crie uma função que leia estes vetores do teclado
- Crie um função que calcule o produto escalar entre estes vetores.
- Crie uma função que calcule o produto vetorial entre estes vetores.
- Crie uma função que imprima o resultado na tela
- produto escalar
C = A*B=a1b1 + a2b2 + a3b3
- produtor vetorial
C =[a2b3 – a3b2, a3b1 – a1b3, a1b2 - a2b1]
Basic sort building blocks
- insert: insert on sorted array, keeping it sorted
- merge: merge two sorted arrays into a sorted array.
- partition an arbitrary array into smaller and larger than a given t
Tarefa 7 - Busca Binaria 30Mai19
- Implementar busca binaria de um vetor ordenado de floats
- Utilizar apenas linguagem C e sua propria implementacao
- Bonus: implementar em C++ usando a biblioteca padrao
Tarefa 8 - Ordenacao 6Jun19
- Implementar o mergesort, o quicksort e o insertion sort
Part 2: Computational Geometry problems to practice C++ programming
- Compute scalar and vector product of 3-vectors
- Hash tables, Buckets for point query
- Proximity
- Voronoi Diagrams
- Curve Algorithms
Homework: given a list of points, compute the closest point
- Naive algorithm
- Hash table from Programming Pearls
Homework: given a list of points, output all lines passing through each pair of points
- Line going through two points
Trabalho: Parte 1 valendo bonus, dia 2/Maio/2019, Parte2 completo 16/Maio/2019 (REMARCADA)
- Dado um labirinto na forma de uma matriz, onde os caminhos sao formados por espaco ' ',
e as paredes do labirindo sao formadas pela letra 'a' ou '8' conforme abaixo, e dada uma entrada e uma saida marcadas por espaco ' ' ou na parede de cima do labirinto, ou na parede de baixo, resolva o labirinto ou retorne 0 caso nao exista um caminho. Note que tanto as paredes ou os caminhos podem ter largura maior que 1 caractere.
- A parte 2 do trabalho valera nota e devera ser entregue 1 semana apos a parte 1. A parte 1 eh apenas bonus para incentivar o aluno a resolver o problema com ideias proprias.
- Sera dado um grande bonus.
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa a 8 8 8 8 8 8 8 8 8 aaaaaaaaa 8 aaaaa aaaa8aaaa aaaa8 aaaaa aaaaa 8 8 8 8 8 8 8 8 8 8 8 8 8aaaaaaaa a 8aaaaaaa8 8aaaaaaaa 8aaaa a 8 8 8aaaaaaa8 8 8 8 8 8 8 8 8 8 8 8 8 8 a 8aaa8aaaaaaaa a 8 aaaaaaaa8 8aaa8 8 8aaaaaaaa 8 8 8 8 8 8 8 8 8 8 8 8 8 8aaaaaaaaaaaa 8aaa8 8aaaa 8 aaaaa 8aaaaaaaa 8 aaaa8 8 8 8 8 8 8 8 8 8 8 8 8 aaaaa 8aaaa 8 8aaaa 8 8aaaaaaa8 a a 8 8aaaaaaaaaaa8 8 8 8 8 8 8 8 8 8 8 8 8 8aaaaaaa8aaaa 8 8 8 aaaa8aaaa 8 aaaa8 8 8aaaa 8aaaa 8 8 8 8 8 8 8 8 8 8 8 8 aaaaa 8 8aaaaaaaa 8aaaa 8 8aaaa 8aaa8 aaaa8aaaaaaaa 8 8 8 8 8 8 8 8 8 8 8 8 8 aaaa8aaaa a 8aaaa aaaa8aaaa 8 8 8aaaaaaaaaaaa 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8aaaaaaaa 8 8 8 8aaa8 8aaaaaaa8 aaaaaaaaa 8 8aaaaaaa8 8 8 8 8 8 8 8 8 8 8 8 8 aaaa8 8aaa8 aaaaa 8aaaaaaaa 8aaa8 a 8aaaaaaaa a 8 8 8 8 8 8 8 8 8 8aaaaaaaaaaaaaaaaaaa8aaaaaaaaaaa8aaaaaaaaaaaaaaa8aaaaaaaaaaaaaaa8aaa8