Encontrando coordenadas de fronteira a partir de um determinado conjunto de coordenadas de pontos?

Dado um conjunto de coordenadas, Como encontramos as coordenadas de limite.
<== Figura 1
Dadas as coordenadas no conjunto acima, como posso obter as coordenadas no limite vermelho. Limite é o polígono formado pelas coordenadas de entrada dos vértices, de forma a maximizar a área.

Estou trabalhando em um aplicativo que pesquisa propriedades dentro de 'x' milhas de uma cidade . O que eu tenho é:

1. Coordenadas de todas as propriedades.
2. Um conjunto de coordenadas para cada cidade (eu tenho uma coordenada para cada CEP. E, como a maioria das cidades possui mais de um CEP, toda cidade tem um conjunto de coordenadas)

O motivo pelo qual estou solicitando a área máxima é para não criar um polígono como o abaixo:

<== Figura 2

O que eu preciso é do algoritmo para criar o conjunto de coordenadas para o limite. Um algoritmo que me permitirá criar coordenadas de limite para a Figura 1 .

Existem muitos algoritmos para resolver esse problema ( Wikipedia "Convex_hull_algorithms" ):

• Embrulho para presente, também conhecido como Jarvis march - O (nh): um dos algoritmos mais simples. Possui complexidade de tempo O (nh), onde n é o número de pontos no conjunto e h é o número de pontos no casco. No pior caso, a complexidade é O (n2).
• Graham scan - O (n log n): Algoritmo ligeiramente mais sofisticado, mas muito mais eficiente. Se os pontos já estiverem classificados por uma das coordenadas ou pelo ângulo de um vetor fixo, o algoritmo leva tempo O (n). [ pseudo código ]
• QuickHull: Como o algoritmo quicksort, ele tem a complexidade de tempo esperada de O (n log n), mas pode degenerar para O (nh) = O (n2) no pior caso. [ descrição ilustrada ]
• Dividir e conquistar - O (n log n): Esse algoritmo também é aplicável ao caso tridimensional.
• Cadeia monótona - O (n log n): Variante do Graham scan que classifica os pontos lexicograficamente por suas coordenadas. Quando a entrada já está classificada, o algoritmo demora O (n).
• Algoritmo convexo incremental do casco - O (n log n)
• Casamento antes da conquista - O (n log h): algoritmo ótimo sensível à saída.
• Algoritmo de Chan - O (n log h): algoritmo ótimo mais simples, sensível à saída.

1) Casco convexo no GRASS GIS: http://grass.fbk.eu/grass64/manuals/html64_user/v.hull.html

2) Casco convexo em Qgis Vector Tools (muito fácil de usar):

O Hawth's Tools for ArcGIS possui essa funcionalidade . Além de um script para o ArcInfo 10.

Também existe uma ferramenta de casco convexa no QuantumGIS via plugin ftools .

O que você quer é o casco convexo. No PostGIS, existe uma função (na verdade GEOS) que fornece o casco convexo, ST_ConvexHull (geometria) .

Na wikipedia, há muitas informações sobre cascos côncavos.

Se você deseja que um algoritmo faça isso (em vez de pacotes que podem fazê-lo), acho que precisaria triangular os dados; ou basicamente defina uma linha de cada ponto para qualquer outro ponto. Então, começando (digamos) no ponto com o valor Y mais alto, trace uma rota ao redor do exterior seguindo a linha conectada com o menor ângulo / rolamento externo.

Você seria capaz de acelerar o traçado jogando fora as linhas de interseção primeiro. O limite externo não terá interseções.

btw - O FME também fará isso com os transformadores ConvexHullAccumulator ou ConvexHullReplacer!

Se você estiver interessado em examinar um algoritmo existente implementado no código, o NetTopologySuite possui um algoritmo para fazer isso

Consulte ConvexHull.cs

Aliás, o NTS e várias outras bibliotecas estão envolvidas em um projeto interessante chamado DotSpatial, encontrado aqui