Método "contains" (classe GeneralPath) retorna false

Programação Java
#1

Boa tarde senhores,

Tenho alguns pontos que formam um poligono. Em determinado momento preciso saber quais pontos estão posicionados dentro desse poligono.
Pesquisei e vi a classe GeneralPath, quando a precisão não é grande ele funciona corretamente, porém quando tenho uma precisão alta ele me retorna false…

Estou deixando passar alguma coisa?

Obrigado.

import java.awt.geom.GeneralPath;


public class Poligono {

	public static void main(String[] args) {
		
		GeneralPath g = new GeneralPath();
		
		double x1 = 9.99999999717344D;
		double y1 = 8.998489425981866D;
	
		double x2 = 10.000000002887727;
		double y2 = 11.690332326283981;
		
		double x3 = 10.000000002836707D;
		double y3 = 33.52416918429003;
		
		g.moveTo(x1, y1);
		g.lineTo(x2, y2);
		g.lineTo(x3, y3);

		g.closePath();
		
		System.out.println(g.contains(10.0D, 20.0D)); // retorna false.
		
	}
}
#2

Resolvi o problema para o meu caso reduzindo a precisão da aquisição das coordenadas, porém é interessante para a comunidade conseguirmos a resposta para essa questão.

Abraço,

#3

Você está querendo saber se um ponto está dentro de um triângulo, certo?

Nesse caso desse triângulo absurdamente fino ( 9.99999999717344, 10.000000002836707 e 10.000000002887727 ) você intuitivamente sabe que ele fica dentro do triângulo, mas se você fosse fazer as contas com double você mesmo, tem certeza que o seu algoritmo, com a precisão do double, iria corretamente indicar que está dentro do triângulo?

#4

Olá entanglement,

No meu caso é o seguinte: eu tenho um gráfico feito com a biblioteca JFreeChart, no gráfico o usuário consegue com cliques do mouse criar um polígono. Estou conseguindo desenhar o polígono corretamente no gráfico (e por isso eu sei que o ponto está dentro dele), mas na hora que utilizo o método “contains” ele não consegue me afirmar isso.

Link para imagem: https://docs.google.com/open?id=0B5EM_bu_2R9fVG03bXpvVjZsNTg

Coordenadas dos pontos do polígono na imagem:

(10.000000001020409,22.557401812688823)
(9.99999999892857,22.15861027190332)
(9.99999999994898,30.234138972809667)

Coordenada do ponto dentro do polígono:

(10,25)

O que acha?

#5

Se você já estudou cálculo numérico, provavelmente esse é um problema “mal-condicionado”. Uma forma de melhorar o condicionamento de um problema desses é você deixar o triângulo “mais gordinho”. Por exemplo, converter o triângulo

        double x1 = 9.99999999717344D;  
        double y1 = 8.998489425981866D;  
      
        double x2 = 10.000000002887727;  
        double y2 = 11.690332326283981;  
          
        double x3 = 10.000000002836707D;  
        double y3 = 33.52416918429003;

em:

        double x1 = -0.282656; // (9.99999999717344D - 10) * 1E8)
        double y1 = 8.998489425981866D;  
      
        double x2 = 0.2887727;  // (10.000000002887727 - 10) * 1E8
        double y2 = 11.690332326283981;  
          
        double x3 = 0.2836707; // (10.000000002836707 - 10) * 1E8
        double y3 = 33.52416918429003;

é um “condicionamento” do problema (para evitar trabalhar com diferenças de números muito próximos).
Então você não testaria o ponto 10.0, 20.0 e sim o ponto 0.0, 20.0:

System.out.println(g.contains(0.0, 20.0D));
#6