스케치 어플리케이션의 포인트 데이터 구조

Question

현재 HTML5 Canvas 요소를 기반으로 약간 sketching application을 개발 중입니다. 내가 아직 적절한 해결책을 찾을 수 없었던 한 가지 특별한 문제가 있습니다.

아이디어는 사용자가 기존의 획 데이터 (점)를 아주 자유롭게 조작 할 수 있다는 것입니다. 여기에는 포인트 데이터 (예 : 자석 공구)를 밀고 다른 방식으로 조작하는 것이 포함됩니다 (예 : 색상 변경).

현재 브러시 엔진은 기존의 획 데이터를 개수로 음영 처리 할 수 ​​있습니다. 현재 스트로크에서 포인트를 반복하고 거리 규칙에 따라 포인트를 확인하므로 빠르고 간단합니다.

이제 문제는 좋은 방법으로이를 수행하는 방법입니다. 주어진 캔버스 좌표와 반경 내에서 모든 점을 반환하는 효율적인 쿼리를 수행하는 것이 매우 중요합니다. 공간 사용과 같은 다른 기능은 이에 부차적이어야합니다. 사용자가 그림을 그리는 동안 스트로크 사이에 몇 가지 추가 처리 작업을해도 상관 없습니다.

모든 안내를 환영합니다. :)

Answer 1

당신은 일반적으로 spatial indexing에서보고 싶은데 :

Answer 2

나는 x에 주어진 픽셀에 대해, y 매트릭스의 값은 그 색입니다 간단한 매트릭스 int pixels[][]와 함께 갈 것입니다.

좀 더 정교한 데이터 구조를 사용하는 것이 분명하지는 않지만 매트릭스는 매우 빠르고 사용하기 쉽습니다. 예를 들어, 주어진 좌표와 반경에 대한 점을 얻는 등의 작업에 대해서는 행렬 인덱스에서 수학을 수행하고 일치 픽셀 만 검색하는 등 빠른 속도로 출혈이 발생합니다.

Answer 3

기본적으로 객체의 배열을 픽셀의 데이터를 이동하거나 샘플링하는 몇 가지 특수 함수로 래핑합니다. 날씨 - 침식 프로젝트에서 비슷한 점을 보였습니다 ... 일종의 원주/가중 원리에 따라 데이터를 샘플링하고 푸시하는 데 Gaussian 함수를 사용했습니다.

실행 취소/브러시 스트로크 상호 작용을 원할 경우 각 '브러시 스트로크'에 매핑되는 픽셀 목록을 가져야하지만 다른 개체처럼 보이는 것이 좋습니다. 모든 브러시 스트로크가 그 중앙을 가리키고 있습니다. 행렬 (영향을받은 점들의 실제 내용에 대해 - 그들이 점에 기여한 색과 관련하여 '가중치'를 가졌을 수도 있음). http://en.wikipedia.org/wiki/Quadtree

Answer 4

차원에서 임의의 점 목록 작업을위한 표준 솔루션은 쿼드 트리 공간 분할이다. Johan은 quadtree에 대해 좋은 제안을했습니다. 사용할 수있는 다른 데이터 구조 :

• kd-tree
• vp tree
• simple grid index