círculo máximo dentro de um polígono irregular a partir de um ponto aleatório

8

Estou tentando elaborar um algoritmo para criar o círculo de raio máximo dentro de um polígono irregular (um setor censitário) com base em um determinado centro do círculo.

A motivação para isso é obscurecer a localização de uma pessoa que respondeu a uma pesquisa. Sua localização real é conhecida, no entanto, ela precisa ser obscurecida na análise, a fim de liberar os dados ao público, para posterior análise.

Queremos ter um polígono em forma de anel para cada respondente da pesquisa que possua um raio interno (fácil), limitado por um raio externo que é limitado pelo setor censitário em que o indivíduo se encontra. Sua localização final será colocada aleatoriamente no polígono de anel .

Eu já vi muitas respostas para perguntas semelhantes aqui, mas não essa específica, que neste caso começa com um local ESPECÍFICO.

Uma vez estabelecido o donut, podemos aleatoriamente a localização da resposta individual dentro do polígono. Isso é relativamente fácil ...

Obrigado por suas idéias, as minhas até agora pareciam uma força bruta e computacionalmente "caras" ou ineficientes ...

Percy
fonte
1
Não é apenas a menor distância do local específico até o limite do polígono que você deseja?
Nicklas Avén 17/03/2013
Qual software ou linguagem de programação você está usando?
Pablo
Por que não apenas cruzar o anel desejado com o trato? Melhor ainda, não há razão para usar formas circulares - você também pode usar um anel quadrado, o que levaria a uma execução mais rápida.
whuber
3
Parece haver pouco ou nenhum consenso . Uma visão geral de alguns métodos aparece aqui, começando na p. 34 . Um método sofisticado foi proposto em nosso site . Um grupo de trabalho internacional recente explorou muitas questões relacionadas. Uma revisão recente de Mathews & Harel pode ser útil.
whuber
3
@ Whuber, muito obrigado! Suponho que você seja o mesmo Bill Huber que publica ajuda e código-fonte desde que comecei a usar o GIS em 1998. Adorei todos os seus scripts Avenue, aprendi muito com eles (e presumo que o programa mencionado abaixo seja o ArcView, é incrível o quão rápido ele roda nos dias de hoje !!!). Só queria que você soubesse o quanto você é apreciado na comunidade de profissionais de GIS! Obrigado por todos os seus anos de ótimos conselhos!
22313 Percy

Respostas:

3

Um método simples para mover locais dentro de tais anéis explora uma representação em grade da distância até o limite do trato. Começando com uma representação poligonal dos setores censitários (que é o habitual),

  1. Converta isso nos limites do polígono (uma camada de polilinha).

  2. Calcule a grade da distância euclidiana até os limites.

  3. Extraia as distâncias euclidianas nos locais indicados.

  4. Mova cada local dentro do intervalo indicado pela distância - que, por definição, é o máximo até o limite.

Cada um normalmente requer apenas um único comando com um GIS, tornando a sequência inteira facilmente automatizada e facilmente executada manualmente. Esses são comandos eficientes , porque não exigem a construção de um buffer para cada ponto (o que normalmente cria várias dezenas a quase mil pontos para descrever um anel ou anel ). Também não são necessários ensaios ou pesquisas aleatórias: os pontos são deslocados diretamente por quantias garantidas para deixá-los dentro de seus setores censitários originais.


Por exemplo, movi 172.902 locais em 47 setores em direções aleatórias por deslocamentos uniformemente distribuídos entre metade da distância e a distância total até o limite. Aqui está uma parte de uma área antes da mudança:

figura 1

(quadrados amarelos marcam os locais) e após a mudança:

Figura 2

(agora quadrados cinza marcam os novos locais). A operação total levou apenas um ou dois minutos (usando um GIS desatualizado antigo :-).

Comparando esses números de perto, você pode ver que

  • Os pontos que estão agora próximos ao limite (como perto dos dois lagos mostrados como "buracos" brancos nessas figuras) permanecem necessariamente próximos ao limite.

  • Pontos distantes do limite tendem a se afastar.

Consequentemente, um ponto próximo ao limite provável (mas não certamente) se originou muito próximo, enquanto qualquer ponto distante do limite provavelmente se originou em algum outro lugar longe do limite. Essas duas tendências estão longe de ser completamente aleatórias: elas podem (com bastante facilidade) ser exploradas por alguém que deseja penetrar na privacidade que esses movimentos pretendiam proporcionar.

Métodos melhores tornariam as conexões entre a localização final e a inicial mais tênues e mais aleatórias. No mínimo, os pontos devem ser movidos dentro de bairros razoavelmente grandes, em vez de bairros de tamanhos variados (e possivelmente arbitrariamente pequenos). Tais movimentos não são realizados prontamente com grades, porque geralmente requerem algumas tentativas e erros: você gera vários pontos aleatórios em uma vizinhança de cada ponto original e seleciona o primeiro que se encontra no mesmo setor censitário. Esse é um loop envolvendo (1) um movimento aleatório e (2) uma consulta ponto a polígono. Ambas as operações são rápidas, mas isso requer um pouco de programação para implementar o loop.

(Em um comentário à pergunta, forneço links para alguns estudos de métodos usados ​​para disfarçar dados de localização para fins de privacidade.)

whuber
fonte
2

Eu só queria testar seus donuts no PostGIS

Eu tentei no PostGISonline.

Para fazer o mesmo teste, acesse: http://postgisonline.org/map.php

Existem alguns polígonos chamados "propriedade" de impressão:

SELECT * FROM property;

e pressione "Map1"

Em seguida, você pode testar o código da rosca copiando o abaixo para a área de texto e pressione "map2" (o mapa de propriedades permanecerá):

SELECT ST_Difference(ST_Buffer(the_geom,dist),ST_Buffer(the_geom,dist/3)) the_geom,dist FROM
(
    SELECT ST_Distance(poly.boundary,points.the_geom) dist, points.the_geom FROM
    (
        SELECT ST_Boundary(the_geom) boundary,the_geom FROM property
    ) poly
    INNER JOIN
    (
        SELECT ST_SetSrid('POINT(137816 267009)'::geometry,3021) the_geom
        UNION ALL
        SELECT ST_SetSrid('POINT(139816 268542)'::geometry,3021) the_geom
        UNION ALL
        SELECT ST_SetSrid('POINT(135016 268102)'::geometry,3021) the_geom
    ) points
    ON ST_Contains(poly.the_geom,points.the_geom)
) a

Isso deve fornecer um resultado semelhante a: insira a descrição da imagem aqui

Nicklas Avén
fonte
O PostGIS simplesmente arrasa! Obrigado, isso é incrível, bom trabalho!
223 Percy
1

Espero que esta solução Python o ajude. O fluxo de trabalho geral é o seguinte:

  1. Converta polígonos em polilinhas para poder calcular uma distância Próximo
  2. Buffer os pontos com base na distância próxima

insira a descrição da imagem aqui

# Import arcpy module
import arcpy, os
from arcpy import env

env.overwriteOutput = 1

env.workspace = r'C:\sample.gdb\temp'
Dir = env.workspace

# Local variables:
points = "points"
polygon = "polygon"
points_2 = "points"
buffers = "buffers"
polyline = "polyline"

# Polygon To Line
arcpy.PolygonToLine_management(polygon, polyline, "IDENTIFY_NEIGHBORS")

# Near
arcpy.Near_analysis(points, polyline)

# Buffer
arcpy.Buffer_analysis(points_2, buffers, "NEAR_DIST")
Aaron
fonte
Obrigado! parece que pode funcionar! :-) vamos tentar!
Percy