Algoritmo para encontrar centróide de polígono irregular (ponto da etiqueta)

Preciso encontrar um centróide (ou ponto de etiqueta) para polígonos de formato irregular no Google Maps. Estou mostrando o InfoWindows para encomendas e preciso de um local para ancorar o InfoWindow que é garantido que está na superfície. Veja as imagens abaixo.

Na realidade, não preciso de nada específico do Google Maps, apenas procurando uma idéia de como encontrar esse ponto automaticamente.

Minha primeira idéia foi encontrar o centróide "falso" pegando a média de lat e lngs e a colocação aleatória de pontos de lá até encontrar um que cruze o polígono. Eu já tenho o código point-in-polygon. Isso me parece terrivelmente "hacky".

Devo observar que não tenho acesso a nenhum código do lado do servidor que gera a geometria, portanto não posso fazer nada como ST_PointOnSurface (the_geom).

Rápido e sujo: se o centróide "falso" não estiver no polígono, use o vértice mais próximo a esse ponto.

Você pode olhar para isso: http://github.com/tparkin/Google-Maps-Point-in-Polygon

Parece usar um algoritmo de Ray Casting que deve corresponder ao caso que você apresentou.

Há um post sobre isso aqui. http://appdelegateinc.com/blog/2010/05/16/point-in-polygon-checking/

Um algoritmo ESRI (mais antigo) calcula o centro de massa e, após testá-lo para inclusão no polígono, move-o horizontalmente, se necessário, até que fique dentro do polígono. (Isso pode ser feito de várias maneiras, dependendo de quais operações fundamentais estão disponíveis no seu ambiente de programação.) Isso tende a produzir pontos de etiqueta bem perto do centro visual do polígono: experimente na ilustração.

Eu resolvi meu problema estendendo o código epoly popular de http://econym.org.uk/gmap . Basicamente, o que acabei fazendo foi:

• Crie uma série de raios que começam do "falso centróide" e se estendem a todos os cantos e laterais (total de 8)
• Crie incrementalmente um ponto 10,20,30 ... por cento abaixo de cada raio e veja se esse ponto está em nosso polígono original

Código epoly extendido abaixo:

google.maps.Polygon.prototype.Centroid = function() {
var p = this;
var b = this.Bounds();
var c = new google.maps.LatLng((b.getSouthWest().lat()+b.getNorthEast().lat())/2,(b.getSouthWest().lng()+b.getNorthEast().lng())/2);
if (!p.Contains(c)){
    var fc = c; //False Centroid
    var percentages = [0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9]; //We'll check every 10% down each ray and see if we're inside our polygon
    var rays = [
        new google.maps.Polyline({path:[fc,new google.maps.LatLng(b.getNorthEast().lat(),fc.lng())]}),
        new google.maps.Polyline({path:[fc,new google.maps.LatLng(fc.lat(),b.getNorthEast().lng())]}),
        new google.maps.Polyline({path:[fc,new google.maps.LatLng(b.getSouthWest().lat(),fc.lng())]}),
        new google.maps.Polyline({path:[fc,new google.maps.LatLng(fc.lat(),b.getSouthWest().lng())]}),
        new google.maps.Polyline({path:[fc,b.getNorthEast()]}),
        new google.maps.Polyline({path:[fc,new google.maps.LatLng(b.getSouthWest().lat(),b.getNorthEast().lng())]}),
        new google.maps.Polyline({path:[fc,b.getSouthWest()]}),
        new google.maps.Polyline({path:[fc,new google.maps.LatLng(b.getNorthEast().lat(),b.getSouthWest().lng())]})
    ];
    var lp;
    for (var i=0;i<percentages.length;i++){
        var percent = percentages[i];
        for (var j=0;j<rays.length;j++){
            var ray = rays[j];
            var tp = ray.GetPointAtDistance(percent*ray.Distance()); //Test Point i% down the ray
            if (p.Contains(tp)){
                lp = tp; //It worked, store it
                break;
            }
        }
        if (lp){
            c = lp;
            break;
        }
    }
}
return c;}

Ainda um pouco hacky, mas parece funcionar.

Outro algoritmo "sujo" para fazer isso:

• Pegue a caixa delimitadora da geometria (Xmax, Ymax, Xmin, Ymin)

• Faça um loop até encontrar um ponto aleatório ( Xmin+rand*(Xmax-Xmin), Ymin+rand*(Ymax-Ymin) ) na geometria (usando Google-Maps-Point-in-Polygon )

À luz do seu esclarecimento recente de que você preferiria uma localização estritamente interior, você pode selecionar qualquer ponto na Transformação do Eixo Medial que também não esteja no limite do polígono. (Se você não possui código para um MAT, pode aproximá-lo armazenando em buffer negativo o polígono. Uma pesquisa binária ou secante produzirá rapidamente um pequeno polígono interno que se aproxima de parte do MAT; use qualquer ponto em seu limite.)

Por que não usar o centróide apenas na posição vertical (latitude)? Em seguida, você pode posicionar o rótulo horizontalmente escolhendo a longitude média nessa latitude . (Para isso, você precisa encontrar o valor da longitude de uma aresta de polígono em uma latitude específica, o que não deve causar problemas).

Além disso, tenha cuidado com as formas em U e as mais complexas. :) Possivelmente, escolha a média do par de longitudes mais à direita (cada par corresponderia a uma fatia do polígono), pois a janela de informações está orientada dessa maneira?

Isso também oferece um pouco mais de controle sobre o posicionamento; por exemplo, pode ser bom posicionar a janela de informações em 66 ou 75% verticalmente, a fim de deixar mais do polígono visível. (Ou talvez não! Mas você tem o botão para ajustar.)

Que tal usar apenas o ponto em que o usuário clicou para selecioná-lo, se ele for selecionado pelo usuário.

Também estou tentando resolver isso. Eu impus aos meus polígonos uma condição de que eles não podem ter linhas cruzadas que entram no que descreverei.

Então, minha abordagem usa triangulação. Pegue um vértice aleatório (possivelmente um vértice no extremo N, E, W ou S pode simplificar as coisas).

Nesse vértice, desenhe linhas para o vértice a um vértice de distância, ou seja, se o vértice for o vértice 3, observe o vértice 3 + 2.

Construa uma linha do seu vértice original para esse vértice. Se a linha construída:

1. não cruza nenhuma outra linha e
2. seu ponto médio não está fora do polígono

Então você construiu um triângulo que está dentro do polígono. Se o vértice bem-sucedido foi n + 2, seu triângulo é {n, n + 1, n + 2}, ao qual nos referiremos como {v, v1, v2}. Caso contrário, tente o próximo vértice e continue até que todos os vértices tenham sido tentados.

Quando você encontrar um triângulo, encontre o centro disso tomando uma linha do vértice v até o ponto médio de v1 e v2. É garantido que o ponto médio dessa linha esteja dentro do triângulo e dentro do polígono.

Ainda não codifiquei isso, mas percebo que um polígono com linhas cruzadas causará de fato algumas condições exóticas onde isso não funciona. Se esse é o tipo de polígono que você possui, você precisará testar cada segmento de linha no polígono e garantir que não esteja sendo cruzado. Pule os segmentos de linha cruzados e acho que funcionará.

https://github.com/mapbox/polylabel pode ser útil (javascript e C ++). Implementação de C # aqui: https://gist.github.com/dfaivre/acfef42cdbf411555956e9eba65dd30d .

Pergunta SO original aqui: /programming//a/38522611/79113