Estações de Recarga da Biuaidi

Profs Wagner Meira Jr Eder Ferreira de Figueiredo DCC205 Estruturas de Dados TP3 v10 DCC ICEx UFMG 20241 Trabalho Prático 3 Estações de Recarga da BiUAIDi Descrição do problema Você foi contratado pela fabricante de carros elétricos BiUaiDi para modernizar o aplicativo de identificação de estações de recarga para os carros da fabricante O aplicativo é multiplataforma e a sua função fundamental é dada a posição atual do carro identificar as 10 estações de recarga mais próximas Belo horizonte será a primeira cidade onde o aplicativo será implantado tendo em vista as frequentes necessidades de recarga em virtude do relevo da cidade Tendo em vista os prazos exíguos de lançamento do carro e o pequeno número de estações de recarga em torno de 100 na cidade de Belo Horizonte a versão atual do aplicativo calcula a distância entre o ponto de origem e todos as estações de recarga o que é bastante ineficiente mas efetivo para o pequeno número de estações de recarga disponíveis Adicionalmente estações de recarga podem ser ativadas ou desativadas temporariamente seja por estarem sendo utilizadas por algum veículo seja por outra questão técnica além de novas estações de recarga que são habilitadas a todo momento Assim o aplicativo deve sugerir estações de recarga a partir da configuração instantânea das estações de recarga O aplicativo atual é bastante simples e não satisfaz todos os requisitos Ele é invocado informando uma coordenada x y e retorna as dez estações de recarga mais próximas Por exemplo o comando recargaBiUaiDi 610167846027439 779560243183451 gera a saída apresentada na Figura 2 e ilustrada pelo mapa da Figura 3 O aplicativo atual é disponibilizado como ponto de partida no minhaufmg Ele tem uma série de limitações como descrito a seguir Primeiro ele considera um conjunto fixo de aproximadamente 100 estações de recarga Segundo ele não permite ativações e desativações das estações Terceiro ele sempre retorna as dez estações de recarga mais próximas Finalmente as estações de recarga são mantidas em um vetor e cada consulta demanda o cálculo das distâncias da localização atual do veículo a todos os pontos de recarga On que precisam ser ordenados para identificar os dez pontos mais próximos Onlogn Diante do cenário você propôs uma estratégia de cinco estágios para construir uma nova solução descrita a seguir Flexibilização do aplicativo O primeiro estágio da estratégia é evoluir o aplicativo para que ele trabalhe com um conjunto variável de pontos de recarga e também passe a funcionar como um serviço que receba variados pontos de origem por exemplo representado pela movimentação de um veículo Essa situação será simulada pela leitura e processamento de dois arquivos Estações de recarga A BiUaiDi fez um convênio com a Prefeitura de BH e conseguiu uma lista na forma de um arquivo de todas as potenciais estações de recarga que podem ser instaladas na cidade Esse arquivo uma vez carregado no aplicativo vai permitir variar as estações de recarga ativas num dado momento Os atributos sobre estações de recarga são apresentados na Tabela 1 A Figura 1 apresenta exemplos dos dados de duas estações de recarga Atualizações e Consultas O segundo arquivo simula o funcionamento do aplicativo em um carro em movimento e o dinamismo em termos de ativação e desativação de pontos de recarga Assim cada linha do arquivo contem um de três comandos possíveis C x y n Consulta dos n pontos de recarga mais próximos da posição x y Um exemplo da consulta é apresentado a seguir C 610167846027439 779560243183451 10 A resposta para a consulta pode ser vista na Figura 2 A Figura 3 mostra um mapa contendo as estações de recarga ativas naquele momento e as estações sugeridas O mapa foi gerado pelo programa biuaidinaive Profs Wagner Meira Jr Eder Ferreira de Figueiredo DCC205 Estruturas de Dados TP3 v10 DCC ICEx UFMG 20241 004461066274461AVEPRESIDENTE ANTONIO CARLOS6627Campus UFMGPAMPULHA3127090160924297989932578027650723672 001259015371259AVEAFONSO PENA1537CentroCENTROSUL30130004611566586666557779636353379632 Figura 1 Exemplo de arquivo de entrada RUA TOMAZ GONZAGA 388 Lourdes CENTROSUL 30180140 492143724 AVE BARBACENA 691 Barro Preto CENTROSUL 30190134 1126117168 RUA GUAICUI 510 Luxemburgo CENTROSUL 30380342 1696438429 RUA CAMPO BELO 28 São Pedro CENTROSUL 30330330 2004310020 RUA ORENOCO 58 Carmo CENTROSUL 30310060 2004932781 RUA DOIS MIL SEISCENTOS E TRINTA E DOIS 105 Carlos Prates NOROESTE 30000 2060761938 AVE DOM PEDRO II 388 Bonfim NOROESTE 31210242 2234568923 RUA URUCUIA 110 Floresta CENTROSUL 30150060 2324576666 BEC BRILHANTINA 96 Vila Dias LESTE 31010172 3169933029 RUA SANTOS 494 Jardim América OESTE 30421386 3178736100 Figura 2 Exemplo de saída textual do aplicativo Atributo Tipo Descrição idend char Identificador do endereço idlogrado long Identificador do logradouro siglatipo char Tipo do logradouro pex rua e avenida nomelogra char Nome do logradouro numeroimo int Número do imóvel no logradouro nomebairr char Nome do bairro nomeregio char Nome da região pex centrosul Pampulha cep int CEP código de endereçamento postal x double Coordenada X y double Coordenada Y Tabela 1 Informações sobre potenciais estações de recarga A id Ativar o ponto de recarga associado ao identificador id O exemplo a seguir mostra o comando da ativação de uma mesma estação de recarga mostrando as duas mensagens de saída possíveis Entrada Saída A 00446106627 Ponto de recarga 00446106627 ativado A 00446106627 Ponto de recarga 00446106627 já estava ativo D id Desativar o ponto de recarga associado ao identificador id O exemplo a seguir mostra o comando de desativação de uma mesma estação de recarga mostrando as duas mensagens de saída possíveis Entrada Saída D 00446106627 Ponto de recarga 00446106627 desativado D 00446106627 Ponto de recarga 00446106627 já estava desativado Uso de QuadTree como estrutura de Dados A implementação original do aplicativo BiUaiDi adota como estrutura de dados um vetor das estações de recarga que é utilizado para calcular as distâncias de um dado ponto de origem posição instantânea de um carro a cada uma das estações de recarga As distâncias calculadas são colocadas em um segundo vetor que é ordenado e as estações associadas às distâncias mais curtas na versão original dez compõem a saída do aplicativo ilustrado nas Figuras 2 e 3 É notório que essa complexidade de Onlogn é indesejável e demanda uma reavaliação da estrutura de dados utilizada Profs Wagner Meira Jr Eder Ferreira de Figueiredo DCC205 Estruturas de Dados TP3 v10 DCC ICEx UFMG 20241 Your location Nearest stations BiUaiDi Recharging Stations Figura 3 Exemplo de saída gráfica do aplicativo Profs Wagner Meira Jr Eder Ferreira de Figueiredo DCC205 Estruturas de Dados TP3 v10 DCC ICEx UFMG 20241 A 01855100150 D 03986100116 A 03587300106A D 01981600122A D 07512700842 C 604476327080534 779393651282176 10 C 605262481794150 779325707737953 5 D 02813300418 C 616071596501685 779944881579611 7 C 607550931138684 779870116804509 10 A 01668501159A A 08098800057B C 606279331855856 779339939903000 5 C 605104903517628 779805692607213 5 C 607516231712159 779355293842478 10 A 08777200075 C 602712314503365 779815940825128 3 C 615804983781242 780003404266877 5 D 06751206455A C 616439872399631 780003451657842 10 Figura 4 Exemplo de arquivo de atualizações e consultas O segundo estágio da estratégia proposta e do TP é substituir a estrutura de dados original por uma mais eficiente A proposta é utilizar uma QuadTree estrutura de dados apropriada para dados georeferenciados para armazenar as estações de recarga e identificar as estações mais próximas de um dada localização de origem Assim deve ser implementado um tipo abstrato de dados QuadTree que execute as operações de construção inserção as funções mencionadas consultas e atualizações e destruição da estrutura de dados Embora essa implementação possa ser realizada utilizando alocação dinâmica iremos implementála utilizando um vetor onde os apontadores entre as células são índices do vetor de nodos Um exemplo de implementação de árvore binária vetorizada é provida no minhaufmg da disciplina Importante ressaltar a necessidade de reimplementar as funções de consulta de estações de recarga próximas assim como a ativação e desativação de pontos de recarga A expectativa é que a implementação dessas três funções tenha complexidade sublinear em particular logarítmica O aplicativo à semelhança da versão original naive se inicia com a leitura de um arquivo e armazenamento em uma QuadTree de todos os dados das estações de recarga seguido da lei tura e processamento de um segundo arquivo contendo as várias funções de consulta ativação e desativação a serem executadas Avaliação experimental comparativa das versões do aplicativo O terceiro estágio do projeto TP é a avaliação experimental dos aplicativos tanto em termos de desempenho quanto à sua localidade de referência O aspecto desempenho deve ser medido através do tempo execução do aplicativo como um todo e de cada uma das funções construção consultas e atualizações O aspecto localidade de referência deve ser avaliado por métricas como distância de pilha além de incluir discussões sobre a eficiência de cada estrutura de dados em executar as várias funções Para facilitar os experimentos é disponibilizado um arquivo contendo todos os endereços da cidade de Belo Horizonte 725917 endereços Como mencionado os atributos que caracterizam uma estação de recarga são mostrados na Tabela 1 Em termos da carga de trabalho a ser utilizada devem ser consideradas as seguintes dimensões Número e distribuição das estações de recarga A dimensão estações de recarga deve ser avaliada tanto em relação ao seu número quanto à distribuição espacial das estações Por Profs Wagner Meira Jr Eder Ferreira de Figueiredo DCC205 Estruturas de Dados TP3 v10 DCC ICEx UFMG 20241 exemplo a partir do elenco de estações possíveis podese selecionar as estações a serem consideradas de forma aleatória ou mesmo variando as densidades entre as regiões da cidade Número e natureza das consultas A dimensão consultas deve ser avaliada tanto em relação ao seu número absoluto e relativo comparado às ativações e desativações assim como às suas características como concentração temporal e espacial Por exemplo as consultas podem estar associadas a uma trajetória real a ser realizada por um veículo Número e natureza das ativações e desativações A dimensão ativações e desativações deve ser avaliada tanto em relação ao seu número quanto ao seu impacto em termos de densidade espacial e frequência temporal indicada pela taxa de intercalação de consultas e ativações desativações Extensão do aplicativo para uma arquitetura de dois níveis Como mencionado o aplicativo deve equipar os veículos da BiUaiDi cujo sistema multimídia tem uma memória limitada Para viabilizar a sua efetiva implementação é necessário criar uma arquitetura de dois níveis que permita a replicação transparente da parte dos dados necessária para calcular as distâncias para as estações de recarga mais próximas Essa foi a motivação de utilizar uma estrutura de dados que possua boa localidade de referência para a carga de trabalho do aplicativo Desta forma além de adaptar a estrutura de dados QuadTree implementada é necessário definir e implementar uma política de reposição de páginas Disponibilizamos no minhaufmg a extensão do algoritmo de árvore binária implementado como vetor Avaliação experimental do aplicativo estendido A avaliação experimental do aplicativo estendido deve avaliar tanto medidas de desempenho como a latência para determinar as estações de recarga mais próximas quanto o funcionamento da arquitetura de dois níveis em termos do número e volume de dados transferidos Note que as ativações e desativações não devem ser contabilizadas como tráfego do carro Desta forma a avaliação deve considerar as seguintes dimensões Razão entre memória primária e secundária É o aspecto principal do desempenho da ar quitetura de dois níveis Quanto maior for essa razão mais dados podem ser mantidos na memória primária Número de estações considerado nas consultas O número de estações considerado nas con sultas indica a amplitude da varredura pelos vizinhos mais próximos na estrutura de dados Deve ser elaborado um plano experimental que exercite variações nessas dimensões e permita observar os impactos das variações nos valores A avaliação deve incluir uma discussão dos resul tados Documentação A documentação do trabalho deve ser entregue em formato PDF e também DEVE seguir o mo delo de relatório que será postado no Moodle Além disso a documentação deve conter TODOS os itens descritos a seguir NA ORDEM em que são apresentados 1 Capa Título nome e matrícula 2 Introdução Contém a apresentação do contexto problema e qual solução será empregada 3 Método Descrição da implementação detalhando as estruturas de dados tipos abstratos de dados ou classes e funções ou métodos implementados Profs Wagner Meira Jr Eder Ferreira de Figueiredo DCC205 Estruturas de Dados TP3 v10 DCC ICEx UFMG 20241 4 Análise de Complexidade Contém a análise da complexidade de tempo e espaço dos procedimentos implementados formalizada pela notação assintótica 5 Estratégias de Robustez Contém a descrição justificativa e implementação dos meca nismos de programação defensiva e tolerância a falhas implementados 6 Análise Experimental Apresenta os experimentos realizados em termos de desempenho computacional e localidade de referência assim como as análises dos resultados 7 Conclusões A Conclusão deve conter uma frase inicial sobre o que foi feito no trabalho Posteriormente devese sumarizar o que foi aprendido 8 Bibliografia Contém fontes utilizadas para realização do trabalho A citação deve estar em formato científico apropriado que deve ser escolhido por você 9 Número máximo de páginas incluindo a capa 10 Não se esqueça de descrever de forma concisa sua implementação da Quadtree e sua organização em dois níveis Analise o impacto das sua escolhas na complexidade do algoritmo compare com outras possíveis estruturas que também resolveriam o problema A documentação deve conter a descrição do seu trabalho em termos funcionais dando foco nos algoritmos estruturas de dados e decisões de implementação importantes durante o desenvolvi mento Evite a descrição literal do códigofonte na documentação do trabalho Dica Sua documentação deve ser clara o suficiente para que uma pessoa da área de Computação ou não consiga ler entender o problema tratado e como foi feita a solução Profs Wagner Meira Jr Eder Ferreira de Figueiredo DCC205 Estruturas de Dados TP3 v10 DCC ICEx UFMG 20241 Como será feita a entrega Você deve utilizar a linguagem C ou C para o desenvolvimento do seu sistema O uso de estru turas préimplementadas pelas bibliotecaspadrão da linguagem ou terceiros é terminantemente vetado Você DEVE utilizar a estrutura de projeto abaixo junto ao Makefile TP src bin obj include Makefile A pasta TP é a raiz do projeto src deve armazenar arquivos de código c cpp ou cc a pasta include os cabeçalhos headers do projeto com extensão h por fim as pastas bin e obj devem estar vazias O Makefile deve estar na raiz do projeto A execução do Makefile deve gerar os códigos objeto o no diretório obj e o executável do TP no diretório bin O arquivo executável DEVE se chamar tp3out e deve estar localizado na pasta bin O código será compilado com o comando make a l l O seu código será avaliado através de uma VPL que será disponibilizada no moodle Você também terá à disposição uma VPL de testes para verificar se a formatação da sua saída está de acordo com a requisitada A VPL de testes não vale pontos e não conta como trabalho entregue Um pdf com instruções de como enviar seu trabalho para que ele seja compilado corretamente estará disponível no Moodle A documentação será entregue em uma atividade separada designada para tal no Moodle A entrega deve ser um arquivo com extensão pdf nomeado nomesobrenomematriculapdf onde nome sobrenome e matrícula devem ser substituídos por suas informações pessoais Avaliação Corretude na execução dos casos de teste 30 da nota total Indentação comentários do código fonte e uso de boas práticas 10 da nota total Conteúdo segundo modelo proposto na seção Documentação 20 da nota total Definição e implementação das estruturas de dados e funções 15 da nota total Apresentação da análise de complexidade das implementações 5 da nota total Análise experimental 15 da nota total Seu trabalho segue todas as instruções de entrega 5 da nota total Se o programa submetido não compilar1 seu trabalho não será avaliado e sua nota será 0 Trabalhos entregues com atraso sofrerão penalização de 2d1 pontos com d dias úteis de atraso Considerações finais 1 Comece a fazer esse trabalho prático o quanto antes enquanto o prazo de entrega está tão distante quanto jamais estará 2 Leia atentamente o documento de especificação pois o descumprimento de quaisquer requi sitos obrigatórios aqui descritos causará penalizações na nota final 1Entendese por compilar aquele programa que independente de erros no Makefile ou relacionados a problemas na configuração do ambiente funcione e atenda aos requisitos especificados neste documento em um ambiente Linux Profs Wagner Meira Jr Eder Ferreira de Figueiredo DCC205 Estruturas de Dados TP3 v10 DCC ICEx UFMG 20241 3 Certifiquese de garantir que seu arquivo foi submetido corretamente no sistema 4 Plágio é crime Trabalhos onde o plágio for identificado serão automaticamente anula dos e as medidas administrativas cabíveis serão tomadas em relação a todos os envolvidos Discussões a respeito do trabalho entre colegas são permitidas É permitido consultar fon tes externas desde que exclusivamente para fins didáticos e devidamente registradas na seção de bibliografia da documentação Cópia e compartilhamento de código não são permitidos FAQ Frequently asked Questions 1 Posso utilizar qualquer versão do C NÃO o corretor da VPL utiliza C11 2 Posso fazer o trabalho no Windows Linux ou MacOS SIM porém lembrese que a correção é feita sob o sistema Linux então certifiquese que seu trabalho está funcional em Linux 3 Posso utilizar alguma estrutura de dados do tipo Queue Stack Vector List e etc do C NÃO 4 Posso utilizar smart pointers NÃO 5 Posso utilizar o tipo String SIM 6 Posso utilizar o tipo String para simular minhas estruturas de dados NÃO 7 Posso utilizar alguma biblioteca para tratar exceções SIM 8 Posso utilizar alguma biblioteca para gerenciar memória SIM 9 As análises e apresentação dos resultados são importantes na documentação SIM 10 Os meus princípios de programação ligados a C e relacionados a engenharia de software serão avaliados NÃO 11 Posso fazer o trabalho em dupla ou em grupo NÃO 12 Posso trocar informações com os colegas sobre a teoria SIM 13 Posso utilizar IDEs Visual Studio Code Blocks Visual Code Eclipse SIM Universidade Federal de Minas Gerais UFMG Trabalho Prático 3 Estações de Recarga da BiUAIDi DCC205 Estruturas de Dados Nome Matrícula Cidade 2024 1 Introdução A crescente demanda por sistemas de gerenciamento de recursos urbanos como pontos de recarga para veículos elétricos exige soluções eficientes que possam lidar com grandes volumes de dados espaciais Este projeto aborda o desenvolvimento de um sistema que utiliza estruturas de dados espaciais para gerenciar pontos de recarga distribuídos em uma região geográfica A fabricante de carros elétricos BiUaiDi deseja modernizar o aplicativo de identificação de estações de recarga para os carros da fabricante O aplicativo é multiplataforma e a sua função fundamental é dada a posição atual do carro identificar as 10 estações de recarga mais próximas Belo horizonte será a primeira cidade onde o aplicativo será implantado tendo em vista as frequentes necessidades de recarga em virtude do relevo da cidade Tendo em vista os prazos exíguos de lançamento do carro e o pequeno número de estações de recarga em torno de 100 na cidade de Belo Horizonte a versão atual do aplicativo calcula a distância entre o ponto de origem e todos as estações de recarga o que é bastante ineficiente mas efetivo para o pequeno número de estações de recarga disponíveis Adicionalmente estações de recarga podem ser ativadas ou desativadas temporariamente seja por estarem sendo utilizadas por algum veículo seja por outra questão técnica além de novas estações de recarga que são habilitadas a todo momento Assim o aplicativo deve sugerir estações de recarga a partir da configuração instantânea das estações de recarga O aplicativo atual é disponibilizado como ponto de partida no minhaufmg Ele tem uma série de limitações como descrito a seguir Primeiro ele considera um conjunto fixo de aproximadamente 100 estações de recarga Segundo ele não permite ativações e desativações das estações Terceiro ele sempre retorna as dez estações de recarga mais próximas Finalmente as estações de recarga são mantidas em um vetor e cada consulta demanda o cálculo das distâncias da localização atual do veículo a todos os pontos de recarga On que precisam ser ordenados para identificar os dez pontos mais próximos Onlogn O primeiro estágio da estratégia é evoluir o aplicativo para que ele trabalhe com um conjunto variável de pontos de recarga e também passe a funcionar como um serviço que receba variados pontos de origem por exemplo representado pela movimentação de um veículo Essa situação deve ser simulada pela leitura e processamento de dois arquivos Estações de recarga A BiUaiDi fez um convênio com a Prefeitura de BH e conseguiu uma lista na forma de um arquivo de todas as potenciais estações de recarga que podem ser instaladas na cidade Esse arquivo uma vez carregado no aplicativo vai permitir variar as estações de recarga ativas num dado momento Atualizações e Consultas O segundo arquivo simula o funcionamento do aplicativo em um carro em movimento e o dinamismo em termos de ativação e desativação de pontos de recarga Assim cada linha do arquivo contem um de três comandos possíveis C x y n Consulta dos n pontos de recarga mais próximos da posição x y A id Ativar o ponto de recarga associado ao identificador id D id Desativar o ponto de recarga associado ao identificador id A implementação original do aplicativo BiUaiDi utiliza um vetor para armazenar as estações de recarga que é empregado para calcular as distâncias de um ponto de origem específico a posição atual de um carro até cada uma dessas estações As distâncias calculadas são armazenadas em um segundo vetor que é então ordenado As estações correspondentes às menores distâncias dez na versão original são apresentadas como resultado do aplicativo No entanto é evidente que essa abordagem com complexidade de Onlogn é pouco eficiente e exige uma reconsideração da estrutura de dados utilizada Deste modo o objetivo do trabalho é construir uma solução que seja mais eficiente no que se diz respeito ao tempo de execução especialmente na operação de consultar k pontos mais próximos Além disso trazer flexibilidade em relação ao modo atual de operação do aplicativo O problema de encontrar o k pontos mais próximos está corriqueiramente relacionado ao algoritmo knearest neighbor kNN Neste trabalho utilizamos a estrutura de dados QuadTree que será descrita ao longo do trabalho que é uma estrutura de dados especialista para buscar de ponto em um espaço geográfico como é o caso do problema trabalhado 2 Método A implementação do sistema foi dividida em três módulos principais o módulo de leitura e armazenamento de dados Node o módulo de estrutura espacial Quad e o módulo de processamento de comandos main A ideia principal da solução é utilizar uma árvore QuadTree para subdividir o espaço de busca até encontrar o ponto O espaço de busca é filtrado baseandose sempre no ponto central da área Inicialmente selecionase o ponto mais inferior e a esquerda possível e o ponto mais superior e a direita possível Se selecionarmos o ponto médio entre estes dois pontos dividimos o espaço de busca em quatro áreas Com base no ponto buscado conseguimos identificar facilmente em qual área pertence o ponto A Figura 1 apresenta um exemplo desta estratégia Figura 1 Metodologia de particionamento do espaço de busca utilizando a estrutura de dados QuadTree Fonte Huang et al 2023 Nas seções descritas são apresentados mais detalhes da implementação realizada 21 Estruturas de Dados As estruturas de dados utilizadas na solução são descritas a seguir Nodo Representa um ponto de recarga armazenando informações como coordenadas geográficas identificadores de localização e o estado de ativação do ponto struct Nodo char id50 int idlogrado char siglatipo10 char nomelogradouro100 int numeroimovel char nomebairro50 char nomeregiao50 int cep Ponto pos bool ativo Ponto Representa uma coordenada geográfica com valores de x e y struct Ponto double x double y QuadTree Quad Estrutura de dados hierárquica que divide o espaço em quadrantes menores Cada nó da QuadTree pode armazenar um único ponto e subdivide o espaço se necessário class Quad private Ponto cantoInferiorEsquerdo Ponto cantoSuperiorDireito Nodo nodo Quad quadroSuperiorEsquerdo Quad quadroSuperiorDireito Quad quadroInferiorEsquerdo Quad quadroInferiorDireito métodos e funções auxiliares public void inserirNodo nodo void buscarKNNPonto p int k Nodo nodosProximos double distanciasProximas 22 Funções Implementadas As principais funções implementadas visando solucionar o problema proposto foram Leitura de Dados Os dados dos pontos de recarga são lidos de um arquivo e armazenados em um array de estruturas Nodo Inserção na QuadTree Cada ponto de recarga é inserido na estrutura QuadTree que o posiciona em um quadrante baseado em suas coordenadas Busca de kNN Implementada na classe Quad esta função realiza uma busca recursiva pelos k pontos mais próximos de uma coordenada especificada Processamento de Comandos Função responsável por ler um arquivo de comandos e executar operações de ativação desativação e consulta de proximidade utilizando a estrutura QuadTree 3 Análise de Complexidade A análise de complexidade do sistema abrange as operações de inserção e busca na QuadTree além do processamento de comandos 31 Inserção na QuadTree A inserção de um ponto na QuadTree no pior caso tem complexidade Olog N onde N é o número de pontos na árvore Isso ocorre porque a árvore é balanceada e a cada inserção o espaço é subdividido logaritmicamente 32 Busca kNN A busca kNN na QuadTree tem uma complexidade média de Ok log N onde k é o número de vizinhos mais próximos a serem encontrados A busca envolve percorrer a árvore de forma seletiva comparando distâncias em cada nó 33 Processamento de Comandos A complexidade de processamento de comandos depende do tipo de operação A ativação e desativação de pontos tem complexidade ON pois envolve uma busca linear por um identificador A consulta kNN depende da complexidade da busca descrita anteriormente 4 Estratégias de Robustez Para garantir a robustez do sistema foram implementadas diversas estratégias de programação defensiva e mecanismos de tolerância a falhas Validação de Entrada Durante a leitura de dados e processamento de comandos são realizadas verificações de validade dos dados como checagem de coordenadas e integridade dos identificadores Tratamento de Exceções Embora o código C não utilize exceções explícitas foram adicionadas verificações condicionais para evitar operações inválidas como o acesso a ponteiros nulos ou indexação fora dos limites Gerenciamento de Memória A alocação dinâmica de memória para estruturas de dados como arrays de proximidade é acompanhada de liberações apropriadas evitando vazamentos de memória 5 Análise Experimental A análise experimental foi conduzida com o objetivo de comparar o desempenho entre a versão original do aplicativo da BiUaiDi e a versão aprimorada que utiliza a estrutura de dados QuadTree Para garantir a precisão e a relevância dos resultados foram selecionadas várias configurações de entrada variando a quantidade de pontos de recarga Esses pontos foram processados em operações de busca e atualização para medir o impacto das alterações propostas Os experimentos foram realizados em um ambiente controlado utilizando um computador com as seguintes especificações processador AMD Ryzen com 390 GHz 16 GB de RAM e sistema operacional Windows 11 Foram gerados diversos arquivos de entrada contendo 50 100 150 200 250 300 350 400 450 ou 500 pontos de recarga permitindo observar como o desempenho do sistema se comporta à medida que a complexidade do problema aumenta Os tempos de execução foram registrados para cada conjunto de dados permitindo uma comparação direta entre as duas versões do aplicativo O gráfico de comparação é apresentado na Figura 2 Figura 2 Comparação das Versões O gráfico revela uma vantagem significativa da versão que utiliza a QuadTree especialmente em cenários que se aumenta o número de pontos de recarga Acreditase que este ganho significativo devese a um custo computacional menor para a realização das buscas 6 Conclusões A atualização do aplicativo BiUaiDi incorporando a estrutura de dados QuadTree demonstrou ser uma solução extremamente eficiente para melhorar o gerenciamento das estações de recarga em áreas urbanas complexas como Belo Horizonte A nova versão proporcionou uma melhora significativa no tempo de resposta das consultas especialmente em situações onde há um grande número de estações de recarga Essa mudança permitiu ao sistema lidar de maneira mais eficaz com a tarefa de localizar as estações mais próximas o que é essencial para a funcionalidade do aplicativo em cenários de mobilidade Além de aprimorar o desempenho a introdução da QuadTree também trouxe mais flexibilidade ao sistema A capacidade de ativar e desativar estações de recarga de forma dinâmica sem comprometer a eficiência das buscas garante que o aplicativo possa se ajustar rapidamente a mudanças no ambiente de recarga Isso é vital para responder às variações nas condições operacionais em tempo real como a disponibilidade das estações proporcionando uma experiência de usuário mais confiável e robusta Finalmente a análise experimental confirmou a eficiência da QuadTree em diferentes cenários de aplicação destacando sua capacidade de escalabilidade À medida que o volume de dados aumenta o aplicativo mantém um desempenho eficiente preparandose para futuras expansões como a inclusão de novas cidades ou o aumento do número de estações de recarga Assim a implementação da QuadTree não só melhora o desempenho imediato do sistema mas também assegura sua capacidade de evolução e adaptação frente às crescentes demandas da mobilidade elétrica 7 Bibliografia CORMEN T H et al Algoritmos teoria e prática Editora Campus v 2 p 296 2002 HUANG Y et al QSFDEW a fingerprint positioning method based on quadtree search and fractal direction entropy weighting Wireless Networks v 29 n 1 p 437448 2023 STROBACH P et al Quadtreestructured recursive plane decomposition coding of images IEEE Transactions on Signal Processing v 39 n 6 p 13801397 1991 Universidade Federal de Minas Gerais UFMG Trabalho Prático 3 Estações de Recarga da BiUAIDi DCC205 Estruturas de Dados Nome Matrícula Cidade 2024 1 Introdução A crescente demanda por sistemas de gerenciamento de recursos urbanos como pontos de recarga para veículos elétricos exige soluções eficientes que possam lidar com grandes volumes de dados espaciais Este projeto aborda o desenvolvimento de um sistema que utiliza estruturas de dados espaciais para gerenciar pontos de recarga distribuídos em uma região geográfica A fabricante de carros elétricos BiUaiDi deseja modernizar o aplicativo de identificação de estações de recarga para os carros da fabricante O aplicativo é multiplataforma e a sua função fundamental é dada a posição atual do carro identificar as 10 estações de recarga mais próximas Belo horizonte será a primeira cidade onde o aplicativo será implantado tendo em vista as frequentes necessidades de recarga em virtude do relevo da cidade Tendo em vista os prazos exíguos de lançamento do carro e o pequeno número de estações de recarga em torno de 100 na cidade de Belo Horizonte a versão atual do aplicativo calcula a distância entre o ponto de origem e todos as estações de recarga o que é bastante ineficiente mas efetivo para o pequeno número de estações de recarga disponíveis Adicionalmente estações de recarga podem ser ativadas ou desativadas temporariamente seja por estarem sendo utilizadas por algum veículo seja por outra questão técnica além de novas estações de recarga que são habilitadas a todo momento Assim o aplicativo deve sugerir estações de recarga a partir da configuração instantânea das estações de recarga O aplicativo atual é disponibilizado como ponto de partida no minhaufmg Ele tem uma série de limitações como descrito a seguir Primeiro ele considera um conjunto fixo de aproximadamente 100 estações de recarga Segundo ele não permite ativações e desativações das estações Terceiro ele sempre retorna as dez estações de recarga mais próximas Finalmente as estações de recarga são mantidas em um vetor e cada consulta demanda o cálculo das distâncias da localização atual do veículo a todos os pontos de recarga On que precisam ser ordenados para identificar os dez pontos mais próximos Onlogn O primeiro estágio da estratégia é evoluir o aplicativo para que ele trabalhe com um conjunto variável de pontos de recarga e também passe a funcionar como um serviço que receba variados pontos de origem por exemplo representado pela movimentação de um veículo Essa situação deve ser simulada pela leitura e processamento de dois arquivos Estações de recarga A BiUaiDi fez um convênio com a Prefeitura de BH e conseguiu uma lista na forma de um arquivo de todas as potenciais estações de recarga que podem ser instaladas na cidade Esse arquivo uma vez carregado no aplicativo vai permitir variar as estações de recarga ativas num dado momento Atualizações e Consultas O segundo arquivo simula o funcionamento do aplicativo em um carro em movimento e o dinamismo em termos de ativação e desativação de pontos de recarga Assim cada linha do arquivo contem um de três comandos possíveis C x y n Consulta dos n pontos de recarga mais próximos da posição x y A id Ativar o ponto de recarga associado ao identificador id D id Desativar o ponto de recarga associado ao identificador id A implementação original do aplicativo BiUaiDi utiliza um vetor para armazenar as estações de recarga que é empregado para calcular as distâncias de um ponto de origem específico a posição atual de um carro até cada uma dessas estações As distâncias calculadas são armazenadas em um segundo vetor que é então ordenado As estações correspondentes às menores distâncias dez na versão original são apresentadas como resultado do aplicativo No entanto é evidente que essa abordagem com complexidade de Onlogn é pouco eficiente e exige uma reconsideração da estrutura de dados utilizada Deste modo o objetivo do trabalho é construir uma solução que seja mais eficiente no que se diz respeito ao tempo de execução especialmente na operação de consultar k pontos mais próximos Além disso trazer flexibilidade em relação ao modo atual de operação do aplicativo O problema de encontrar o k pontos mais próximos está corriqueiramente relacionado ao algoritmo knearest neighbor kNN Neste trabalho utilizamos a estrutura de dados QuadTree que será descrita ao longo do trabalho que é uma estrutura de dados especialista para buscar de ponto em um espaço geográfico como é o caso do problema trabalhado 2 Método A implementação do sistema foi dividida em três módulos principais o módulo de leitura e armazenamento de dados Node o módulo de estrutura espacial Quad e o módulo de processamento de comandos main A ideia principal da solução é utilizar uma árvore QuadTree para subdividir o espaço de busca até encontrar o ponto O espaço de busca é filtrado baseandose sempre no ponto central da área Inicialmente selecionase o ponto mais inferior e a esquerda possível e o ponto mais superior e a direita possível Se selecionarmos o ponto médio entre estes dois pontos dividimos o espaço de busca em quatro áreas Com base no ponto buscado conseguimos identificar facilmente em qual área pertence o ponto A Figura 1 apresenta um exemplo desta estratégia Figura 1 Metodologia de particionamento do espaço de busca utilizando a estrutura de dados QuadTree Fonte Huang et al 2023 Nas seções descritas são apresentados mais detalhes da implementação realizada 21 Estruturas de Dados As estruturas de dados utilizadas na solução são descritas a seguir Nodo Representa um ponto de recarga armazenando informações como coordenadas geográficas identificadores de localização e o estado de ativação do ponto struct Nodo char id50 int idlogrado char siglatipo10 char nomelogradouro100 int numeroimovel char nomebairro50 char nomeregiao50 int cep Ponto pos bool ativo Ponto Representa uma coordenada geográfica com valores de x e y struct Ponto double x double y QuadTree Quad Estrutura de dados hierárquica que divide o espaço em quadrantes menores Cada nó da QuadTree pode armazenar um único ponto e subdivide o espaço se necessário class Quad private Ponto cantoInferiorEsquerdo Ponto cantoSuperiorDireito Nodo nodo Quad quadroSuperiorEsquerdo Quad quadroSuperiorDireito Quad quadroInferiorEsquerdo Quad quadroInferiorDireito métodos e funções auxiliares public void inserirNodo nodo void buscarKNNPonto p int k Nodo nodosProximos double distanciasProximas 22 Funções Implementadas As principais funções implementadas visando solucionar o problema proposto foram Leitura de Dados Os dados dos pontos de recarga são lidos de um arquivo e armazenados em um array de estruturas Nodo Inserção na QuadTree Cada ponto de recarga é inserido na estrutura QuadTree que o posiciona em um quadrante baseado em suas coordenadas Busca de kNN Implementada na classe Quad esta função realiza uma busca recursiva pelos k pontos mais próximos de uma coordenada especificada Processamento de Comandos Função responsável por ler um arquivo de comandos e executar operações de ativação desativação e consulta de proximidade utilizando a estrutura QuadTree 3 Análise de Complexidade A análise de complexidade do sistema abrange as operações de inserção e busca na QuadTree além do processamento de comandos 31 Inserção na QuadTree A inserção de um ponto na QuadTree no pior caso tem complexidade Olog N onde N é o número de pontos na árvore Isso ocorre porque a árvore é balanceada e a cada inserção o espaço é subdividido logaritmicamente 32 Busca kNN A busca kNN na QuadTree tem uma complexidade média de Ok log N onde k é o número de vizinhos mais próximos a serem encontrados A busca envolve percorrer a árvore de forma seletiva comparando distâncias em cada nó 33 Processamento de Comandos A complexidade de processamento de comandos depende do tipo de operação A ativação e desativação de pontos tem complexidade ON pois envolve uma busca linear por um identificador A consulta kNN depende da complexidade da busca descrita anteriormente 4 Estratégias de Robustez Para garantir a robustez do sistema foram implementadas diversas estratégias de programação defensiva e mecanismos de tolerância a falhas Validação de Entrada Durante a leitura de dados e processamento de comandos são realizadas verificações de validade dos dados como checagem de coordenadas e integridade dos identificadores Tratamento de Exceções Embora o código C não utilize exceções explícitas foram adicionadas verificações condicionais para evitar operações inválidas como o acesso a ponteiros nulos ou indexação fora dos limites Gerenciamento de Memória A alocação dinâmica de memória para estruturas de dados como arrays de proximidade é acompanhada de liberações apropriadas evitando vazamentos de memória 5 Análise Experimental A análise experimental foi conduzida com o objetivo de comparar o desempenho entre a versão original do aplicativo da BiUaiDi e a versão aprimorada que utiliza a estrutura de dados QuadTree Para garantir a precisão e a relevância dos resultados foram selecionadas várias configurações de entrada variando a quantidade de pontos de recarga Esses pontos foram processados em operações de busca e atualização para medir o impacto das alterações propostas Os experimentos foram realizados em um ambiente controlado utilizando um computador com as seguintes especificações processador AMD Ryzen com 390 GHz 16 GB de RAM e sistema operacional Windows 11 Foram gerados diversos arquivos de entrada contendo 50 100 150 200 250 300 350 400 450 ou 500 pontos de recarga permitindo observar como o desempenho do sistema se comporta à medida que a complexidade do problema aumenta Os tempos de execução foram registrados para cada conjunto de dados permitindo uma comparação direta entre as duas versões do aplicativo O gráfico de comparação é apresentado na Figura 2 Figura 2 Comparação das Versões O gráfico revela uma vantagem significativa da versão que utiliza a QuadTree especialmente em cenários que se aumenta o número de pontos de recarga Acreditase que este ganho significativo devese a um custo computacional menor para a realização das buscas 6 Conclusões A atualização do aplicativo BiUaiDi incorporando a estrutura de dados QuadTree demonstrou ser uma solução extremamente eficiente para melhorar o gerenciamento das estações de recarga em áreas urbanas complexas como Belo Horizonte A nova versão proporcionou uma melhora significativa no tempo de resposta das consultas especialmente em situações onde há um grande número de estações de recarga Essa mudança permitiu ao sistema lidar de maneira mais eficaz com a tarefa de localizar as estações mais próximas o que é essencial para a funcionalidade do aplicativo em cenários de mobilidade Além de aprimorar o desempenho a introdução da QuadTree também trouxe mais flexibilidade ao sistema A capacidade de ativar e desativar estações de recarga de forma dinâmica sem comprometer a eficiência das buscas garante que o aplicativo possa se ajustar rapidamente a mudanças no ambiente de recarga Isso é vital para responder às variações nas condições operacionais em tempo real como a disponibilidade das estações proporcionando uma experiência de usuário mais confiável e robusta Finalmente a análise experimental confirmou a eficiência da QuadTree em diferentes cenários de aplicação destacando sua capacidade de escalabilidade À medida que o volume de dados aumenta o aplicativo mantém um desempenho eficiente preparandose para futuras expansões como a inclusão de novas cidades ou o aumento do número de estações de recarga Assim a implementação da QuadTree não só melhora o desempenho imediato do sistema mas também assegura sua capacidade de evolução e adaptação frente às crescentes demandas da mobilidade elétrica 7 Bibliografia CORMEN T H et al Algoritmos teoria e prática Editora Campus v 2 p 296 2002 HUANG Y et al QSFDEW a fingerprint positioning method based on quadtree search and fractal direction entropy weighting Wireless Networks v 29 n 1 p 437448 2023 STROBACH P et al Quadtreestructured recursive plane decomposition coding of images IEEE Transactions on Signal Processing v 39 n 6 p 13801397 1991