Determinando a orientação dos pontos de um polígono

by Cássio R Eskelsen 8. janeiro 2009 14:38

Em um sistema georeferenciado quando trabalhamos com polígonos precisamos saber qual é a orientação dos pontos do polígono: horário ou anti-horário.

Polígono no sentido horário 
Polígono com pontos no sentido horário

image  
Polígono com pontos no sentido anti-horário

Falando mais especificamente, quando persistimos um polígono em uma base de dados (como o SQL Server 2008) precisamos garantir que o ordenamento é o correto. No caso do Sql Server, os segmentos externos de um polígono precisam estar orientados no sentido anti-horário.

Para determinar a orientação de um polígono, disponibilizo a seguir uma pequena função.

Como retirei essa função de dentro de meus projetos, simplifiquei um pouco os objetos espaciais para facilitar a compreensão aqui

Basicamente considero um polígono um conjunto de coordenadas que por sua vez são formadas por um par longitude/latitude.
Alguns preferem tratar os polígonos como um conjunto de segmentos de reta, mas para as minhas necessidades isso não é preciso.

Não deve-se esquecer que um polígono deve ser fechado, ou seja, o último ponto deve ser igual ao primeiro.

Com poucas adaptações essa função pode trabalhar também com dados geométricos ao invés de dados geográficos.

Adicionei também um pequeno método que permite inverter a ordem dos pontos. Nada mais do que um wrapper para um método do próprio .Net

No final, criei um pequeno exemplo de como utilizar o método, mostrando a ordem original de cada polígono, invertendo suas ordens e mostrando a nova ordem.

/* 
 * Método para determinação da ordem de um polígono
 * Adaptado por Cássio Rogério Eskelsen (http://www.bizness.com.br)
 * Janeiro/2009
 */
using System;
using System.Collections.Generic;
using System.Linq;

namespace IsCCW
{
    public class Polygon
    {
        private LinkedList<Position> _positions;

        public Polygon()
        {
            _positions = new LinkedList<Position>();
        }

        public Polygon(IList<Position> positions)
        {
            _positions = new LinkedList<Position>(positions);
        }

        //Inverte a ordem dos pontos do polígono
        public void Reverse()
        {
            _positions = new LinkedList<Position>(_positions.Reverse());
        }

        /// <summary>
        /// Determina se o polígono está orientado no sentido anti-horário 
        /// CCW: Counterclockwise - anti-horário
        /// </summary>
        /// <returns></returns>
        public bool IsCCW()
        {
            Position hip, p, prev, next;
            int hii, i;
            int nPoints = this._positions.Count;

            var vertices = _positions.ToArray();

            // verifica se é um poligono válido, ou seja, se tem ao menos 4 pontos.
            // lembrando que em um polígono válido o último ponto é igual ao primeiro
            if (nPoints < 4) return false;

            // encontra o ponto inicial
            hip = vertices[0]; // Position
            hii = 0;           // índice dentro da array
            for (i = 1; i < nPoints; i++)
            {
                p = vertices[i];
                if (p.Longitude.DecimalValue > hip.Longitude.DecimalValue)
                {
                    hip = p;
                    hii = i;
                }
            }
            // encontra os pontos de cada lado do ponto inicial
            int iPrev = hii - 1;
            if (iPrev < 0) iPrev = nPoints - 2;
            int iNext = hii + 1;
            if (iNext >= nPoints) iNext = 1;
            prev = vertices[iPrev];
            next = vertices[iNext];
            
            // converte para que "hip" esteja na origem
            // isso ajuda a previnir alguns problemas de precisão 
            // (por exemplo, quanto vetores muito pequenos possuem coordenadas muito grandes)
            double prev2x = (double)(prev.Longitude.DecimalValue - hip.Longitude.DecimalValue);
            double prev2y = (double)(prev.Latitude.DecimalValue - hip.Latitude.DecimalValue);
            double next2x = (double)(next.Longitude.DecimalValue - hip.Longitude.DecimalValue);
            double next2y = (double)(next.Latitude.DecimalValue - hip.Latitude.DecimalValue);

            double disc = next2x * prev2y - next2y * prev2x;
            // se é igual a zero, as linha são paralelas. São dois casos possíveis
            //    (1) as linhas se encontram ao longo do eixo x no sentido contrário
            //    (2) as linhas se sobrepoe  - isso não deveria acontecer          


            if (disc == 0.0)
            {
                // polígono é anti-horário se prev.longitude está à direita de next.longitude
                return (prev.Longitude.DecimalValue > next.Longitude.DecimalValue);
            }
            else
            {
                // se área é positiva, os pontos estão ordenados no senti anti-horário
                return (disc > 0.0);
            }
        }
    }

    public class Position
    {
        public Position()
        {
        }

        public Position(decimal lat, decimal lon)
        {
            this.Latitude = new Coordinate(lat);
            this.Longitude = new Coordinate(lon);

        }
        public Coordinate Latitude { get; set; }
        public Coordinate Longitude { get; set; }
    }

    /// <summary>
    /// Coordenada. Um valor que representa uma longitude ou uma latitude
    /// </summary>
    public class Coordinate
    {
        public Coordinate() { }
        public Coordinate(decimal value)
        {
            this.DecimalValue = value;
        }

        public decimal DecimalValue { get; set; }
    }

    public class Program
    {
        static void Main(string[] args)
        {
            List<Position> posisA = new List<Position>();
            List<Position> posisB = new List<Position>();

            // TESTE COM POLIGONO CW
            posisA.Add(new Position(12.039320557540572M, -50.44921875M));
            posisA.Add(new Position(-0.615222552406841M, -34.8046875M));
            posisA.Add(new Position(-11.005904459659451M, -37.96875M));
            posisA.Add(new Position(-3.688855143147035M, -57.919921875M));
            posisA.Add(new Position(12.039320557540572M, -50.44921875M));

            Polygon polCW = new Polygon(posisA);
            ShowOrder(polCW);
            polCW.Reverse();
            ShowOrder(polCW);

            // TESTE COM POLIGONO CCW
            posisB.Add(new Position(8.320212289522944M, -48.8671875M));
            posisB.Add(new Position(-5.7908968128719565M, -61.5234375M));
            posisB.Add(new Position(-12.89748918375589M, -46.0546875M));
            posisB.Add(new Position(-4.915832801313164M, -38.056640625M));
            posisB.Add(new Position(8.320212289522944M, -48.8671875M));

            Polygon polCCW = new Polygon(posisB);
            ShowOrder(polCCW);
            polCCW.Reverse();
            ShowOrder(polCCW);

            Console.ReadLine();

        }

        static void ShowOrder(Polygon pol)
        {
            Console.WriteLine("Poligono é {0}", (pol.IsCCW()) ? "anti-horário" : "horário");
        }
    }
    
}

Tags: , ,

.Net | Geo

Comentários

Comentar




  Country flag

biuquote
  • Comentário
  • Pré-visualização
Loading