html5 캔버스 요소에 대한 요소 점 맵, 알고리즘이 필요합니다.

Question

저는 현재 일부 페이지에서 플래시 개체로 여겨지는 "비행 태그 구름 구"의 순수 HTML 5 캔버스 구현 작업을하고 있습니다.

태그는 잘게 그려지고 성능은 만족 스럽지만 캔버스 요소에는이 아이디어를 깨뜨리는 것이 하나 있습니다. 캔버스에 그렸던 객체를 식별 할 수는 없습니다. 간단한 평면 "이미지"..

이 경우해야 할 일은 클릭 이벤트를 포착하고 클릭 한 요소를 "추측"하려고하는 것입니다. 그래서 캔버스에있는 각 픽셀에 대한 태그 객체에 대한 링크를 저장하는 일종의 행렬을 가져야하며 모든 다시 그릴 때마다이 행렬을 업데이트해야합니다. 이제 이것은 매우 비효율적 인 것으로 들립니다. 그리고 구현하기 시작하기 전에 커뮤니티에 물어보고 싶습니다.이 경우에는 "잘 알려진"알고리즘이 있습니까? 아니면 뭔가를 놓친 것일 수도 있습니다. 그 대답은 바로 뒤에 있습니다. :)

Answer 1

이것은 point location problem이라고하며 계산 기하학의 기본 주제 중 하나입니다. 생각할 수있는 방법보다 훨씬 빠를 수있는 많은 방법이 있습니다. 그러나 세부 사항은 정확히 수행하고자하는 바에 달려 있습니다.

예를 들어, 각 텍스트 문자열은 경계 상자에 포함됩니다. 사용자가 해당 상자에서 어딘가를 클릭했는지 여부를 테스트하고 싶습니까? 그런 다음 렌더링 된 각 문자열의 최소 및 최대 좌표를 저장하고 각 경계 상자가 해당 범위에 포함되어 있는지 확인하기 위해 각 경계 상자를 테스트하십시오. 테스트 할 점이 많으면이를 가속화 할 수있는 데이터 구조를 여러 개 만들 수 있습니다 (예 : R-trees). 단일 점의 경우 이러한 구조를 구성하는 오버 헤드는 아마도 가치가 없습니다.

사실 점이 스트로크 된 문자의 불투명 한 영역 내에 있는지 여부에 신경을 쓰면 문제가 약간 복잡해집니다. 한 가지 해결책은 경계 상자 접근법을 사용하여 가능한 대부분의 가능성을 없애고 나머지 문자열을 한 번에 하나씩 오프 스크린 버퍼에 렌더링 한 다음 매번 대상 지점에 접촉했는지 확인하는 것입니다.