2 차원 점 (x, y)을 플로트 좌표로 나타냅니다. 그리면 점이 서로 가까워지면 그룹화해야하며 그룹화해야합니다 고정 된 크기의 사각형 도움. 그리고 문제는이 직사각형들이 교차하지 않아야하고, 모든 점 - 이웃들이 그룹화되어야한다는 것입니다.
근처에 종이가있는 경우 큰 사각형을 그릴 수 있습니다 (예 : 4 * 5cm - 모든 지점이있는 영역). 이제 무작위로 포인트를 넣고, 거리가 1cm 인 포인트가 있다면, 사각형 2 * 3으로 그룹화해야합니다.서로 가까이있을 때 그룹화 점
알고리즘을 만드는 방법 및 성능 문제도 찾을 수 없습니다 ... 중첩, 클러스터링을 찾았지만 필요한 것은 조금 다릅니다. 그런데 어떤 그룹화 사각형이 조건에 맞는 공통 영역을 벗어나야하는 경우 문제가되지 않습니다. 예 : 당신은 지역 4 * 5, 그리고 다른 모든 지점이 분류 되었기 때문에
(1,0), (2,1), (4,1), (4,3), (2,4)
다음 rectangles (0,0 - 3,2) & (3,1 - 6,3) and one point left (2,4)을 좋아해야 될 점과이 점은 지금 어떤 이웃이 없습니다.
내 포인트의 좌표는 정수가 아니고 부동입니다. 포인트 수는 몇 백 (최대 500) 일 수 있습니다. 그리고 나는 같은 직사각형의 영역을 깨뜨리고 단지 얼마나 많은 점이 있는지를 계산하고 싶지 않습니다. 예를 들어 위의 예를 들어 내가 반응 영역 (0,0 - 3,2)을 만들 수 있다는 것을 의미합니다 (3,0 - 6,2) , (0,3 - 3,6), (3,3 - 6,6) 그리고 단지 첫 번째 rect에 대해 2 점을 요약하고, 두 번째에 대해서는 1 (!), 세 번째에 대해서는 1, 4 번째에 대해서는 1 작업에 따라 하나의 rect가 그려지고 다른 모든 점은 => 틀린 결과가됩니다. 아이디어가 있으십니까? 적어도 어떤 알고리즘이 도움이 될 수 있습니까? 어디서 찾을 수 있습니까?
P.S. 현재 결과의 그룹 수/포인트 수는 중요하지 않습니다. e.i. 위의 예와 같이 허용되는 또 다른 결과는 (1,0-4,2) 및 (2,2-5,4) 직사각형 일 수 있으며 점이 남아 있지 않습니다.
그래서 사용이 허용 된 사각형의 치수는 고정되어 있으며 축 정렬되어 있습니까? 그리고 남은 점수를 최소화하고 싶다고 생각합니다. 맞습니까? – Jacob
예, 치수가 고정되어 있습니다 (x * y), 회전 할 수 없습니다 (x * y는 x * y를 의미하고 y는 * x로 바꿀 수 없습니다). 최소화에 대해서, 지금은 아니오. 결과는 주어진 거리보다 가까운 다른 점을 갖는 점을 포함해서는 안되며, 그 점은 모두 – Maxym
입니다. 직사각형이어야하며 정확해야합니까? k와 같은 것을 사용할 수 있습니다 : http://jsfiddle.net/8NpNp/2/ – david