다각형 내의 각 포인트를 반복하십시오.

Question

그리드 환경에서 일부 다각형 정점을 가지고 있다고 가정하면, 포함 된 각 셀 (가장자리에있는 셀 포함)을 반복 할 수 있습니까? (좌상이 (0, 0) 경우로 계산)

내가 다음 정점을 명확히하려면 이와 같은 다각형을 정의 할

//each point is [x, y] 
var verts = [ 
    [1, 1], 
    [3, 1], 
    [3, 2], 
    [4, 2], 
    [4, 4], 
    [0, 4], 
    [0, 3], 
    [1, 3] 
]; 

:

어디 각각 녹색 점은 위의 정점을 기반으로 반복하고 싶은 점입니다. 정점이 다각형의 가장자리를 따라 걷는 방향에 패턴이 없으면 폴리곤 주위로 시계 방향 또는 시계 반대 방향으로 갈 수 있습니다. 그러나 그들은 순서대로있을 것이다. 즉, 펜을 내려 놓고 각 꼭지점까지 순서대로 이동하지 않고 들어 올리면 폴리곤 내부를 횡단하지 않고 윤곽선을 그립니다.

캔버스 API를 통해로드 된 PNG에서 imageData이라는 유스 케이스가 있습니다. 이 PNG는 "영역"으로 나뉘며 현재 "영역"의 각 픽셀을 반복해야합니다. 각 "영역"은 위와 같은 꼭지점 배열로 정의됩니다.

나는 다음과 같은 것을 시도해 보았습니다. 배열에서 4 개의 꼭지점 각각에 대해 반복 할 사각형을 만듭니다. 그 생각에

for(var v = 0, vl = verts.length - 4; v < vl; ++v) { 
    //grabbing the minimum X, Y and maximum X, Y to define a square to iterate in 
    var minX = Math.min(verts[v][0], verts[v + 1][0], verts[v + 2][0], verts[v + 3][0]), 
     minY = Math.min(verts[v][1], verts[v + 1][1], verts[v + 2][1], verts[v + 3][1]), 
     maxX = Math.max(verts[v][0], verts[v + 1][0], verts[v + 2][0], verts[v + 3][0]), 
     maxY = Math.min(verts[v][1], verts[v + 1][1], verts[v + 2][1], verts[v + 3][1]); 

    for(var x = minX; x < maxX; ++x) { 
     for(var y = minY; y < maxY; ++y) { 
      //do my checks on this pixel located at X, Y in the PNG 
     } 
    } 
} 

두 개의 큰 문제 :

1. 그것은 다각형 내에 지점을 반복 할 수 있으며,
이
2. 그것은

내가 먼저 해결할 수 다각형 외부에 포인트를 잡을 수 있습니다 확인하는 지점을 추적하여 문제를 확인하므로 수표를 반복하지 않습니다. 두 번째 방법은 각 포인트에 대해 PointInPoly 검사를 실행해야만 해결할 수 있습니다. 그러면이 솔루션이 내가 원하는 것보다 훨씬 무거울 수 있습니다.

EDIT
순회 각 화상 전체의 화소 각각에 PointInPoly 체크를 적용하는 것도 허용되지; 위의 알고리즘보다 느릴 수도 있습니다.

Answer 1

당신의 다각형이 볼록 경우, 당신은 다음을 수행 할 수 있습니다

• 가 될 수있는, (이것은 정상적인 기반으로 내부 한쪽 외부 한쪽을 나타내는 다각형의 각 에지 라인 만들기 굴곡 방향에 따라 다름)
• 이미 계산 한 경계 상자 안의 모든 픽셀에 대해 픽셀이 선의 인면에 있는지 확인합니다. 픽셀이 선의 바깥쪽에 있으면 그 픽셀은 다각형 바깥에 있습니다. 그것이 모두 내부에 있다면, 그것은 내부에 있습니다.

기본 알고리즘은 여기에서있다 : 당신의 다각형 하지 볼록 경우 https://github.com/thegrandpoobah/voronoi/blob/master/stippler/stippler.cpp#L187

후, 내가 무엇을 할 것입니다 실제로 적용 후 특정 색상의 캔버스에 다각형을 그리고하는 것입니다 iterative flood fill algorithm.따라서 내부에있는 하나 이상의 픽셀을 알고 있어야하지만 비싼 테스트는 아닙니다. 하지만 이것은 오프 스크린 버퍼 (canvas 태그에 익숙하지 않은 버퍼)에서 수행 할 수없는 경우 JavaScript에서 적합하지 않을 수 있습니다.