Computational Geometry

De Pontão Nós Digitais

////////// Under Construction //////////

Computational-geometry-concept-diagram.png

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

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
    • 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
  • 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

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] :

  1. Crie uma função que leia estes vetores do teclado
  2. Crie um função que calcule o produto escalar entre estes vetores.
  3. Crie uma função que calcule o produto vetorial entre estes vetores.
  4. 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


Quizz 1: C++ programming skills