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 com pontos no sentido horário
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");
}
}
}