Encontre a linha reta mais longa entre dois pontos na superfície do polígono

8

Minha forma é um polígono levemente côncavo e gostaria de saber o diâmetro máximo. Imagino uma linha reta entre dois pontos na superfície do polígono, de modo que a linha não passe para fora do polígono.

Existe um algoritmo geral para isso?

No meu caso, estou interessado em 2D. Minhas formas são tumores em imagens médicas. Portanto, também podemos assumir: 1 o centróide está sempre dentro do polígono. 2 uma alta densidade de vértices, ou seja, o próximo vértice está sempre próximo ao anterior.

mathematics computational-geometry polygon jiggunjer
fonte
11
Existem pinças rotativas, mas isso só funciona para polígonos convexos. Caso contrário, você pode usá-lo como base para uma solução de força bruta.
Ratchet freak #
3
Bem se S (n ^ 2) não é um problema, em seguida testar todos os pares de pontos
joojaa
2
Na verdade, é um pouco mais complicado: imagine 2 quartos conectados por um corredor estreito. O maior diâmetro terminará nas paredes das diferentes salas e não terminará em nenhum ponto.
Ratchet freak #
11
Você está procurando um algoritmo que funcione no caso mais geral ou que possa ser restrito, por exemplo, ao caso 2D? Isso pode ser mais fácil de resolver com mais informações ou restrições sobre a entrada. Você usa a palavra polígono, que pode sugerir apenas 2D, também a pergunta que você vinculou sugere o caso 2D. Além disso, é suficiente considerar as distâncias vértice-vértice ou você precisa de resultados corretos para casos como catraca esquisita mencionados em seu comentário ?
Nero
2
Além disso, estou preocupado com uma forma de C que tem uma espessura muito estreita, mas um interior grande e aberto; e assim um grande raio de curvatura. Seu diâmetro (como você o define) seria muito pequeno, porque seria apenas um curto que segue a curvatura do C. No entanto, um nódulo de câncer do tamanho do tamanho interior seria bastante preocupante. Então talvez seja o casco convexo que você deseja calcular o diâmetro.
Wyck

Respostas:

1

Não tenho uma resposta exata para isso, pois a resposta está longe de ser trivial. Eu sugeriria que você desse uma olhada na geometria computacional, pois isso claramente é um problema de visibilidade - meu palpite é que já existe uma solução. Minha própria idéia seria: para cada segmento de linha no polígono, encontre as partes visíveis dos outros segmentos de linha e escolha o par de pontos mais afastados. Link inspirador: Wikipedia sobre 'polígono de visibilidade' .

além
fonte