점이 스플라인/베 지어 곡선에있는 점 사이를 확인하십시오.

Question

여기 제가 해결하려고하는 것이 있습니다. 3 차원 (x1, y1), (x2, y2), (x3, y3) (2 차원 평면에 있음)을 포함하는 곡선이 있습니다. 내가 알아 내려고하는 것은 클릭 포인트가 포인트 1과 포인트 2 사이에 있는지 아니면 포인트 2와 포인트 3 사이에 있는지에 따라 베 지어 곡선에서 네 번째 포인트가 사용자에 의해 클릭되는 경우입니다. 클릭 포인트는 라인이 직접 클릭하여 포인트 1과 포인트 2 또는 포인트 2와 포인트 3 사이에 있어야합니다.

라인은 컴파일시 임의로 생성되며 임의의 (x, y) 위치에서 시작하고 끝낼 수 있습니다.

선을 구성하는 3 세트의 점은 시작점, 커브 점 및 끝점입니다. 이 세 점은 선의 조절 점입니다. 그런 다음 제어점에서 선 객체가 작성됩니다. 제어점은 프로그램을 실행할 때마다 임의로 생성되므로 매번 스플라인이 달라집니다.

이 문제를 해결하는 데 필요한 특정 알고리즘이 있습니까? 나는 자바 스크립트에서 이것을 코딩하고 있지만 의사 코드와 같은 모든 C++ 또는 java가 좋습니다. 도와 주셔서 감사합니다.

Answer 1

사용자가 클릭 할 때 클릭 한 (x, y) 좌표를 곡선의 t 값 (또는 사용자가 컨트롤을 호출 한 값)으로 확인할 수 있도록 곡선에 대한 LUT (조회 테이블)을 작성하십시오. 물론 변수). 사실상 불가능한 (x, y) 좌표를 기반으로 평가하는 대신 네 좌표를 모두 t 값으로 해석하면 매우 간단 해집니다.

(x1, y1)은 t = 0이고 (x2 , y2)가 t = T이고 (x3, y3)이 t = 1 인 경우 사용자가 곡선의 아무 곳이나 클릭하면 새 값을 얻습니다. 이 값이 T보다 작 으면 점은 점 1과 점 2 사이에 있고 점이 T보다 크면 점 2와 점 3 사이에 놓입니다.

곡선 테이블마다 룩업 테이블을 작성해야하며, 처음으로 커브를 그릴 때 실행하십시오. 그러면 이미 t 값이 (x, y) 좌표로 매핑되어 있으므로 "무료"역 매핑을 빌드 할 수 있습니다. 드로 코드를 제어하지 않으면 커브를 만들 때 자신 만의 코드를 실행해야합니다.

하나의 문제가 있습니다. 여기에 3 개의 커브 점으로 정의 된 커브는 베 지어 커브를 정의하는 일반적인 방법이 아닙니다. 베 지어 곡선의 경우 제어점은 곡선 "선체"를 정의합니다. (3 점을 가진) 2 차 곡선의 경우, 점 1과 점 3이 곡선에 있음을 의미하지만 점 2는 그렇지 않다는 것을 의미합니다. 이 세 점 (세 점을 통과하는 곡선)을 기반으로 실제 베 지어 곡선을 찾으려면 세 점을 진정한 곡선으로 바꾸는 알고리즘을 실행해야합니다.

(전체 코드는 어떻게이 응답의 범위를 벗어나는 꽤 많이 할 방법을 알려,하지만 나는 3 점을 기반으로 진정한 곡선을 형성 http://pomax.github.io/bezierinfo/#pointcurves에서 남중, 베 지어 곡선에 긴 글에서 설명)

를