두 개의 가능한 인덱스가있는 집합에 요소 저장

Question

특정 상황에 대한 솔루션이 필요합니다. 기본적으로 선분에서 작동하는 알고리즘이 있습니다. 나는 선분 끝과 시작점 만 알고있다. (점은 2 좌표 x, y를 가지며 이미지의 픽셀 포인트이며 이미지의 크기를 알 수 있습니다.)이 선분을 검사하여 그 위에 무엇인가 할 수 있습니다. 그러나, 나는 또한 같은 선분을 다시 검사하지 않도록 검사 된 선분을 추적해야합니다. 저는 C++을 사용하고 있습니다. 그래서 stl set container를 사용하고 싶습니다.

제 질문은 어떻게이 선분을 끝점과 시작점에 따라 저장할 수 있습니까? 끝점과 시작점에 대해 고유 번호를 생성해야합니다. (또한 다른 조언을 위해 stl set을 사용하는 것 이외에는 열려 있습니다.)

하나의 가능한 해결책은 다음과 같이이 두 픽셀에 대한 인덱스 번호를 생성한다는 것입니다. (y * image-> Witdh) + x. 그런 다음 두 개의 인덱스 번호를 얻습니다 (정수에 따라). 그런 다음이 숫자를 연결합니다. (indexStart < < 32) + indexEnd (두 번 얻음). 이제 고유 번호가 생기고 세트에 쉽게 저장할 수 있습니다. 그러나 문제는 내 검색 중에 라인 세그먼트의 시작점이 같은 선분의 끝점이 될 수 있다는 것입니다. 끝점에서 동일한 선분을 발견하면 연결된 선분 고유 번호는 (indexEnd < < 32) + indexStart가됩니다. 그런 다음 피할 필요가있는 내 세트 컨테이너에 동일한 선분을 추가합니다.

어떤 조언을 주셔서 감사합니다.

Answer 1

해결 방법을 유지하거나 operator<을 사용할 수 있습니다. 당신은 약간의 해시 셋 구현으로 전환하는 것이 쉽다는 장점이 있습니다. 다른 하나는 전반적으로 (더 이해하기 쉽고, 아마 더 빠르며, 64 비트 좌표와 함께 사용될 수 있습니다) 전반적으로 더 나은 연습이어야합니다.

그냥 당신이 설명하는 문제를 해결 start 및 end하지만 lower 및 upper 좌표를 구별하지 않음으로써 (당신은 모두 apporaches이 작업을 수행해야합니다). 같은 위치에서 항상 더 작은 좌표를 사용하는 것은 가짜 긍정적 인 다른 세그먼트를 다른 방향으로 발견 할 때 쉽게 해결할 수 있습니다.

Answer 2

선분에 적합한 순서 관계 연산자 만 지정하면됩니다. 나는. 당신의 세그먼트를 같이하는 경우 :

는

struct LineSegment { 
    int start; 
    int end; 
}; 

간단히 std::less<LineSegment>의 인스턴스 (이 중요한 이유에 대한 definition of set 참조)이 존재하도록, 그 구조체에 operator<을 정의합니다.

bool operator<(LineSegment const& lhs, LineSegment const& rhs) { 
    if (lhs.start == rhs.start) 
    return lhs.end < rhs.end; 
    return lhs.start < rhs.start; 
} 

이렇게하면 올바른 순서와 관련하여 std::set<LineSegment> 세트를 사용할 수 있습니다. LineSegments는 실제로는 다른 경우에만 구분됩니다 (정확하게 질문을 이해하면 원하는 것입니다. 그렇지 않으면 operator< 구현을 쉽게 적용 할 수 있습니다).

마찬가지로 LineSegment* 포인터를 세트에 저장하려면 두 번째 템플릿 매개 변수 (대체 std::less<LineSegment*>)에서 세트의 비교 연산자를 무시할 수 있습니다.

std::set<std::pair<std::pair<int, int>, std::pair<int, int> > >

각 키가 결정적으로 고유 한 값을 가지고 있으며, 전체 라인 세그먼트를 설명하는이 방법은 즉시 마음에 온다

Answer 3

한 구조는 int의의 pair s의 setpair의 s입니다.

(indexLeft << 32) + indexRight 

하지만 당신은 왼쪽과 오른쪽 각각의 시간을 할당해야합니다 :

Answer 4

한 솔루션입니다. 예를 들어, 왼쪽에는 최소 X 값이 있습니다.