Considere um polígono com potencial de auto-interseção, definido por uma lista de vértices no espaço 2D. Por exemplo
{{0, 0}, {5, 0}, {5, 4}, {1, 4}, {1, 2}, {3, 2}, {3, 3}, {2, 3}, {2, 1}, {4, 1}, {4, 5}, {0, 5}}
Existem várias maneiras de definir a área desse polígono, mas a mais interessante é a regra ímpar. Tomando qualquer ponto do plano, desenhe uma linha do ponto ao infinito (em qualquer direção). Se essa linha cruza o polígono um número ímpar de vezes, o ponto faz parte da área do polígono, se cruza o polígono um número par de vezes, o ponto não faz parte do polígono. Para o exemplo de polígono acima, aqui estão o contorno e a área ímpar:
O polígono geralmente não será ortogonal. Eu escolhi apenas um exemplo tão simples para facilitar a contagem da área.
A área deste exemplo é 17
(não 24
ou 33
como outras definições ou áreas podem render).
Observe que, nessa definição, a área do polígono é independente de sua ordem de enrolamento.
O desafio
Dada uma lista de vértices com coordenadas inteiras que definem um polígono, determine sua área sob a regra de pares ímpares.
Você pode escrever uma função ou programa, recebendo informações via STDIN ou alternativa mais próxima, argumento de linha de comando ou argumento de função e retornar o resultado ou imprimi-lo em STDOUT ou alternativa mais próxima.
Você pode receber entradas em qualquer formato conveniente de lista ou string, desde que não seja pré-processado.
O resultado deve ser um número de ponto flutuante, com precisão de 6 dígitos significativos (decimais) ou um resultado racional cuja representação de ponto flutuante é precisa de 6 dígitos significativos. (Se você produzir resultados racionais, é provável que sejam exatos, mas não posso exigir isso, pois não tenho resultados exatos para referência.)
Você deve ser capaz de resolver cada um dos casos de teste abaixo em 10 segundos em uma máquina de desktop razoável. (Existe alguma margem de manobra nessa regra, portanto, use seu bom senso. Se levar 20 segundos no meu laptop, eu lhe darei o benefício da dúvida; se demorar um minuto, não vou.) Acho que esse limite deve ser muito generoso, mas deve excluir abordagens em que você apenas discretiza o polígono em uma grade e contagem suficientemente finas, ou usa abordagens probabilísticas como Monte Carlo. Seja um bom esportista e não tente otimizar essas abordagens para que você possa cumprir o prazo de qualquer maneira. ;)
Você não deve usar nenhuma função existente relacionada diretamente a polígonos.
Isso é código de golfe, então a submissão mais curta (em bytes) vence.
Suposições
- Todas as coordenadas são inteiros no intervalo
0 ≤ x ≤ 100
,0 ≤ y ≤ 100
. - Haverá pelo menos
3
e no máximo50
vértices. - Não haverá vértices repetidos. Nenhum dos vértices estará em outra extremidade. (Porém, pode haver pontos colineares na lista.)
Casos de teste
{{0, 0}, {5, 0}, {5, 4}, {1, 4}, {1, 2}, {3, 2}, {3, 3}, {2, 3}, {2, 1}, {4, 1}, {4, 5}, {0, 5}}
17.0000
{{22, 87}, {6, 3}, {98, 77}, {20, 56}, {96, 52}, {79, 34}, {46, 78}, {52, 73}, {81, 85}, {90, 43}}
2788.39
{{90, 43}, {81, 85}, {52, 73}, {46, 78}, {79, 34}, {96, 52}, {20, 56}, {98, 77}, {6, 3}, {22, 87}}
2788.39
{{70, 33}, {53, 89}, {76, 35}, {14, 56}, {14, 47}, {59, 49}, {12, 32}, {22, 66}, {85, 2}, {2, 81},
{61, 39}, {1, 49}, {91, 62}, {67, 7}, {19, 55}, {47, 44}, {8, 24}, {46, 18}, {63, 64}, {23, 30}}
2037.98
{{42, 65}, {14, 59}, {97, 10}, {13, 1}, {2, 8}, {88, 80}, {24, 36}, {95, 94}, {18, 9}, {66, 64},
{91, 5}, {99, 25}, {6, 66}, {48, 55}, {83, 54}, {15, 65}, {10, 60}, {35, 86}, {44, 19}, {48, 43},
{47, 86}, {29, 5}, {15, 45}, {75, 41}, {9, 9}, {23, 100}, {22, 82}, {34, 21}, {7, 34}, {54, 83}}
3382.46
{{68, 35}, {43, 63}, {66, 98}, {60, 56}, {57, 44}, {90, 52}, {36, 26}, {23, 55}, {66, 1}, {25, 6},
{84, 65}, {38, 16}, {47, 31}, {44, 90}, {2, 30}, {87, 40}, {19, 51}, {75, 5}, {31, 94}, {85, 56},
{95, 81}, {79, 80}, {82, 45}, {95, 10}, {27, 15}, {18, 70}, {24, 6}, {12, 73}, {10, 31}, {4, 29},
{79, 93}, {45, 85}, {12, 10}, {89, 70}, {46, 5}, {56, 67}, {58, 59}, {92, 19}, {83, 49}, {22,77}}
3337.62
{{15, 22}, {71, 65}, {12, 35}, {30, 92}, {12, 92}, {97, 31}, {4, 32}, {39, 43}, {11, 40},
{20, 15}, {71, 100}, {84, 76}, {51, 98}, {35, 94}, {46, 54}, {89, 49}, {28, 35}, {65, 42},
{31, 41}, {48, 34}, {57, 46}, {14, 20}, {45, 28}, {82, 65}, {88, 78}, {55, 30}, {30, 27},
{26, 47}, {51, 93}, {9, 95}, {56, 82}, {86, 56}, {46, 28}, {62, 70}, {98, 10}, {3, 39},
{11, 34}, {17, 64}, {36, 42}, {52, 100}, {38, 11}, {83, 14}, {5, 17}, {72, 70}, {3, 97},
{8, 94}, {64, 60}, {47, 25}, {99, 26}, {99, 69}}
3514.46
fonte
upath
operador. (Na verdade, é uma conversão 1: 1 extremamente simples entre os separadores.}, {
Acaba de se tornarlineto
, e a vírgula entre xey é removida, e as chaves de abertura e fechamento são substituídas por um cabeçalho e rodapé estáticos ...)upath
elineto
parecer que você está realmente pré-processando a entrada. Ou seja, você não está fazendo uma lista de coordenadas, mas um polígono real.CrossingPolygon
.Respostas:
Mathematica,
247225222Primeiro adicione os pontos de interseção ao polígono, depois inverta algumas das arestas e, em seguida, sua área pode ser calculada como um polígono simples.
Exemplo:
fonte
{1,2},{4,4},{4,2},{2,4},{2,1},{5,3}
? Você deve sair com 3.433333333333309. Eu olhei usando uma lógica semelhante.103/30
e o valor numérico é3.43333
.Python 2,
323319 bytesLeva uma lista de vértices através de STDIN como números complexos, da seguinte forma
e grava o resultado em STDOUT.
Mesmo código após a substituição da string e algum espaçamento:
Explicação
Para cada ponto de interseção de dois lados do polígono de entrada (incluindo os vértices), passe uma linha vertical nesse ponto.
(De fato, devido ao golfe, o programa passa mais algumas linhas; isso realmente não importa, contanto que passemos pelo menos por essas linhas.) O corpo do polígono entre duas linhas consecutivas é composto por trapézios verticais ( e triângulos e segmentos de linha, como casos especiais desses). Deve ser o caso, pois se alguma dessas formas tivesse um vértice adicional entre as duas bases, haveria outra linha vertical nesse ponto, entre as duas linhas em questão. A soma das áreas de todos esses trapézios é a área do polígono.
Eis como encontramos esses trapézios: Para cada par de linhas verticais consecutivas, encontramos os segmentos de cada lado do polígono que (adequadamente) se encontram entre essas duas linhas (que podem não existir para alguns dos lados). Na ilustração acima, esses são os seis segmentos vermelhos, considerando as duas linhas verticais vermelhas. Observe que esses segmentos não se cruzam adequadamente (ou seja, eles só podem se encontrar em seus pontos finais, coincidir completamente ou não se cruzam, pois, mais uma vez, se eles se cruzarem adequadamente, haveria outra linha vertical no meio;) e, portanto, faz sentido falar em encomendar de cima para baixo, o que fazemos. De acordo com a regra dos pares pares, quando cruzamos o primeiro segmento, estamos dentro do polígono; uma vez que cruzamos o segundo, estamos fora; o terceiro, novamente; o quarto, fora; e assim por diante...
No geral, este é um algoritmo O ( n 3 log n ).
fonte
Haskell, 549
Não parece que eu possa jogar este aqui longe o suficiente, mas o conceito era diferente das outras duas respostas, então imaginei que o compartilharia de qualquer maneira. Ele executa operações racionais O (N ^ 2) para calcular a área.
Exemplo:
A idéia é religar o polígono a cada cruzamento, resultando em uma união de polígonos sem arestas que se cruzam. Podemos então calcular a área (assinada) de cada um dos polígonos usando a fórmula de cadarço de Gauss ( http://en.wikipedia.org/wiki/Shoelace_formula ). A regra par-ímpar exige que, quando um cruzamento é convertido, a área do novo polígono seja contada negativamente em relação ao polígono antigo.
Por exemplo, considere o polígono na pergunta original. A travessia no canto superior esquerdo é convertida em dois caminhos que se encontram apenas em um ponto; os dois caminhos são ambos orientados no sentido horário, de modo que as áreas de cada um seriam positivas, a menos que declarássemos que o caminho interno é ponderado por -1 em relação ao caminho externo. Isso é equivalente à reversão do caminho de alphaalpha.
Como outro exemplo, considere o polígono do comentário de MickyT:
Aqui, alguns dos polígonos são orientados no sentido horário e outros no sentido anti-horário. A regra de assinar flip-on-crossing garante que as regiões orientadas no sentido horário apanham um fator extra de -1, fazendo com que elas contribuam com uma quantidade positiva para a área.
Veja como o programa funciona:
fonte