Estou precisando verificar se um dado ponto está contido por um poligono qualquer. Bem, a API Java já faz (porcamente) esse serviço. Porem ela encontra o menor retangulo que contem o poligono e depois verifica se o pon…

PONTO contido por um POLIGONO

1 Resposta

thingol 1 de out. de 2007

Leia o código da classe java.awt.Polygon com mais atenção.
Ela realmente diz que se o ponto não estiver contido no retângulo que circunscreve o polígono, então ele não está contido no polígono.
Mas se estiver contido nesse retângulo, então ele usa aquele método de checar se o número de cruzamentos de uma reta (vertical ou horizontal) entre os vértices do retângulo é par ou ímpar, que você deve conhecer.

/**
     * {@inheritDoc}
     * @since 1.2
     */
    public boolean contains(double x, double y) {
        if (npoints &lt;= 2 || !getBoundingBox().contains(x, y)) {
	    return false;
	}
	int hits = 0;

	int lastx = xpoints[npoints - 1];
	int lasty = ypoints[npoints - 1];
	int curx, cury;

	// Walk the edges of the polygon
	for (int i = 0; i &lt; npoints; lastx = curx, lasty = cury, i++) {
	    curx = xpoints[i];
	    cury = ypoints[i];

	    if (cury == lasty) {
		continue;
	    }

	    int leftx;
	    if (curx &lt; lastx) {
		if (x &gt;= lastx) {
		    continue;
		}
		leftx = curx;
	    } else {
		if (x &gt;= curx) {
		    continue;
		}
		leftx = lastx;
	    }

	    double test1, test2;
	    if (cury &lt; lasty) {
		if (y &lt; cury || y &gt;= lasty) {
		    continue;
		}
		if (x &lt; leftx) {
		    hits++;
		    continue;
		}
		test1 = x - curx;
		test2 = y - cury;
	    } else {
		if (y &lt; lasty || y &gt;= cury) {
		    continue;
		}
		if (x &lt; leftx) {
		    hits++;
		    continue;
		}
		test1 = x - lastx;
		test2 = y - lasty;
	    }

	    if (test1 &lt; (test2 / (lasty - cury) * (lastx - curx))) {
		hits++;
	    }
	}

	return ((hits & 1) != 0);
    }

1 Resposta

Topicos relacionados