두 줄 사이의 교차점을 찾는 가장 효율적인 알고리즘은 무엇입니까?두 줄 간의 교차점을 찾기위한 효율적이고 정확하며 최적화 된 알고리즘
4 점 A, B, C, D가 부여됩니다. AB와 CD의 교차점을 찾습니다. 가능한 한 알고리즘을 최적화하십시오.
두 가지 방법이 있습니다. 하나는 내적을 사용하고 다른 하나는 선을 위해 기울기 절편 양식을 사용하는 것입니다. 어느 것이 더 낫다.
반복되는 질문이 들리 겠지만, 더 나은 복잡성으로 어떤 접근 방식이 더 효과적이고 가장 효율적인지 묻고 싶습니다.
이것은 알고리즘이 필요하지 않으며 단지 solution of two intersecting lines입니다. 이것은 기본적인 수학 문제입니다. 컴퓨팅 문제가 아닙니다. 그냥 대수 조작입니다.
그런데 여기에 a discussion이 도움이 될 것입니다.
나는 이러한 유형의 질문에 대해 Mr. Bourke의 웹 사이트를 선호합니다. 여기에 라인 intersectoin에 그의 기사의이 얼마나 사소한 감안할 때
Intersection point of two lines
, 그것은 최적화 꽤 힘든.
내가 할 수있는 최선은 CPU 캐시에 모든 것이 있는지 확인하는 것입니다. 이렇게하면 최고 속도로 수학 연산을 실행할 수 있습니다. 차이점 중 일부 (P2 - P1)를 사전 계산하려는 유혹을받을 수도 있지만,이 세상에서 메모리 조회가 단순히 뺄셈 자체를 수행하는 것보다 빠르다고 말하는 것은 어렵습니다. CPU는 1 연산에서 빼기 및 곱셈을 수행 할 수 있지만 메모리 조회는 캐시를 놓친 경우 두 자리 오랜 시간이 걸릴 수 있습니다.
업데이트 된 링크 : http://paulbourke.net/geometry/pointlineplane/ – jlstrecker
그다지 간단하지 않습니다.
지금까지 파스칼의 예제 (http://actionsnippet.com/?p=956)는 동일 선상의 점에서 작동하지 않습니다.
제대로 구현 된 알고리즘을 찾을 수 없어서 직접 작성해야했습니다.
아무리 간단한 알고리즘이든 모든 수학 연산이 있습니다. –
@BipedalShark : 요컨대,이 포럼은 수학 포럼이 아니라 컴퓨팅 포럼입니다. 예를 들어,이 '알고리즘'의 복잡성에 대해 이야기하는 것은 의미가 없습니다. 예 : 메타에 대한 토론 : http://meta.stackexchange.com/questions/26339/are-algorithm-questions-allowed-on-so –
링크 된 토론의 첫 번째 소제목은 내가 알고있는 가장 효율적인 방법을 보여줍니다. 그 두 선의 교차점에서 4 점을 얻으십시오. 문제의 대부분의 다른 수학적 논의는 여러분이 slope-intercept 형식 ('y = mx + b')으로 시작하는 것으로 가정하고 있지만 실제 응용 프로그램에서는 점에서 시작하는 경향이 훨씬 큽니다. . –