search

Bersaelor / KDTree

Swift implementation of a k-dimensional binary space partitioning tree.
MIT License
153 stars 26 forks source link

Dynamic customizable split axis #59

Closed tatsuya-ogawa closed 1 year ago

tatsuya-ogawa commented 1 year ago

To customize split axis order, I added the additional argument SplitAxisEstimator. It realize the dynamic split axis selection(etc: prefer longest distance , maximum divergence...). And for backward compatibility, default SplitAxisEstimator's logic is migrated from current axis selection's.

Bersaelor commented 1 year ago

Thank you for this work @tatsuya-ogawa !

I'll have to run the tests locally I guess. We used to have travis.ci support to run the tests automatically but that hasn't worked for a while.

tatsuya-ogawa commented 1 year ago

@Bersaelor My local test result is following.

% swift test
Building for debugging...
[2/2] Emitting module KDTreeTests
Build complete! (0.96s)
Test Suite 'All tests' started at 2023-03-15 11:14:15.069
Test Suite 'KDTreePackageTests.xctest' started at 2023-03-15 11:14:15.070
Test Suite 'KDTreeCustomOrderSplitAxisEstimatorTests' started at 2023-03-15 11:14:15.070
Test Case '-[KDTreeTests.KDTreeCustomOrderSplitAxisEstimatorTests test00_tenPointTree]' started.
Test Case '-[KDTreeTests.KDTreeCustomOrderSplitAxisEstimatorTests test00_tenPointTree]' passed (0.006 seconds).
Test Case '-[KDTreeTests.KDTreeCustomOrderSplitAxisEstimatorTests test01_RangeSearchPerformance]' started.
/Users/tatsuyaogawa/Desktop/KDTree/Tests/KDTreeTests/KDTreeTests.swift:137: Test Case '-[KDTreeTests.KDTreeCustomOrderSplitAxisEstimatorTests test01_RangeSearchPerformance]' measured [Time, seconds] average: 0.000, relative standard deviation: 32.963%, values: [0.000772, 0.000305, 0.000305, 0.000561, 0.000525, 0.000374, 0.000355, 0.000444, 0.000369, 0.000307], performanceMetricID:com.apple.XCTPerformanceMetric_WallClockTime, baselineName: "", baselineAverage: , polarity: prefers smaller, maxPercentRegression: 10.000%, maxPercentRelativeStandardDeviation: 10.000%, maxRegression: 0.100, maxStandardDeviation: 0.100
Test Case '-[KDTreeTests.KDTreeCustomOrderSplitAxisEstimatorTests test01_RangeSearchPerformance]' passed (0.391 seconds).
Test Case '-[KDTreeTests.KDTreeCustomOrderSplitAxisEstimatorTests test01b_RangeSearchArrayComparison]' started.
/Users/tatsuyaogawa/Desktop/KDTree/Tests/KDTreeTests/KDTreeTests.swift:150: Test Case '-[KDTreeTests.KDTreeCustomOrderSplitAxisEstimatorTests test01b_RangeSearchArrayComparison]' measured [Time, seconds] average: 0.000, relative standard deviation: 42.265%, values: [0.000677, 0.000864, 0.000365, 0.000345, 0.000376, 0.000349, 0.000311, 0.000311, 0.000311, 0.000336], performanceMetricID:com.apple.XCTPerformanceMetric_WallClockTime, baselineName: "", baselineAverage: , polarity: prefers smaller, maxPercentRegression: 10.000%, maxPercentRelativeStandardDeviation: 10.000%, maxRegression: 0.100, maxStandardDeviation: 0.100
Test Case '-[KDTreeTests.KDTreeCustomOrderSplitAxisEstimatorTests test01b_RangeSearchArrayComparison]' passed (0.266 seconds).
Test Case '-[KDTreeTests.KDTreeCustomOrderSplitAxisEstimatorTests test02_STRangeSearchPerformance]' started.
/Users/tatsuyaogawa/Desktop/KDTree/Tests/KDTreeTests/KDTreeTests.swift:172: Test Case '-[KDTreeTests.KDTreeCustomOrderSplitAxisEstimatorTests test02_STRangeSearchPerformance]' measured [Time, seconds] average: 0.000, relative standard deviation: 50.909%, values: [0.000518, 0.000345, 0.000179, 0.000158, 0.000155, 0.000156, 0.000159, 0.000242, 0.000196, 0.000134], performanceMetricID:com.apple.XCTPerformanceMetric_WallClockTime, baselineName: "", baselineAverage: , polarity: prefers smaller, maxPercentRegression: 10.000%, maxPercentRelativeStandardDeviation: 10.000%, maxRegression: 0.100, maxStandardDeviation: 0.100
Test Case '-[KDTreeTests.KDTreeCustomOrderSplitAxisEstimatorTests test02_STRangeSearchPerformance]' passed (0.269 seconds).
Test Case '-[KDTreeTests.KDTreeCustomOrderSplitAxisEstimatorTests test02b_STRangeSearchArrayComparison]' started.
/Users/tatsuyaogawa/Desktop/KDTree/Tests/KDTreeTests/KDTreeTests.swift:188: Test Case '-[KDTreeTests.KDTreeCustomOrderSplitAxisEstimatorTests test02b_STRangeSearchArrayComparison]' measured [Time, seconds] average: 0.000, relative standard deviation: 47.544%, values: [0.000085, 0.000032, 0.000028, 0.000027, 0.000039, 0.000030, 0.000028, 0.000027, 0.000029, 0.000029], performanceMetricID:com.apple.XCTPerformanceMetric_WallClockTime, baselineName: "", baselineAverage: , polarity: prefers smaller, maxPercentRegression: 10.000%, maxPercentRelativeStandardDeviation: 10.000%, maxRegression: 0.100, maxStandardDeviation: 0.100
Test Case '-[KDTreeTests.KDTreeCustomOrderSplitAxisEstimatorTests test02b_STRangeSearchArrayComparison]' passed (0.264 seconds).
Test Case '-[KDTreeTests.KDTreeCustomOrderSplitAxisEstimatorTests test03_BuildLargeTree]' started.
Test Case '-[KDTreeTests.KDTreeCustomOrderSplitAxisEstimatorTests test03_BuildLargeTree]' passed (0.217 seconds).
Test Suite 'KDTreeCustomOrderSplitAxisEstimatorTests' passed at 2023-03-15 11:14:16.484.
         Executed 6 tests, with 0 failures (0 unexpected) in 1.413 (1.414) seconds
Test Suite 'KDTreeTests' started at 2023-03-15 11:14:16.484
Test Case '-[KDTreeTests.KDTreeTests test00_tenPointTree]' started.
Test Case '-[KDTreeTests.KDTreeTests test00_tenPointTree]' passed (0.002 seconds).
Test Case '-[KDTreeTests.KDTreeTests test01_RangeSearchPerformance]' started.
/Users/tatsuyaogawa/Desktop/KDTree/Tests/KDTreeTests/KDTreeTests.swift:137: Test Case '-[KDTreeTests.KDTreeTests test01_RangeSearchPerformance]' measured [Time, seconds] average: 0.000, relative standard deviation: 16.731%, values: [0.000251, 0.000188, 0.000163, 0.000163, 0.000200, 0.000199, 0.000173, 0.000167, 0.000148, 0.000143], performanceMetricID:com.apple.XCTPerformanceMetric_WallClockTime, baselineName: "", baselineAverage: , polarity: prefers smaller, maxPercentRegression: 10.000%, maxPercentRelativeStandardDeviation: 10.000%, maxRegression: 0.100, maxStandardDeviation: 0.100
Test Case '-[KDTreeTests.KDTreeTests test01_RangeSearchPerformance]' passed (0.259 seconds).
Test Case '-[KDTreeTests.KDTreeTests test01b_RangeSearchArrayComparison]' started.
/Users/tatsuyaogawa/Desktop/KDTree/Tests/KDTreeTests/KDTreeTests.swift:150: Test Case '-[KDTreeTests.KDTreeTests test01b_RangeSearchArrayComparison]' measured [Time, seconds] average: 0.000, relative standard deviation: 33.274%, values: [0.000561, 0.000537, 0.000710, 0.000722, 0.000332, 0.000392, 0.000418, 0.000313, 0.000309, 0.000315], performanceMetricID:com.apple.XCTPerformanceMetric_WallClockTime, baselineName: "", baselineAverage: , polarity: prefers smaller, maxPercentRegression: 10.000%, maxPercentRelativeStandardDeviation: 10.000%, maxRegression: 0.100, maxStandardDeviation: 0.100
Test Case '-[KDTreeTests.KDTreeTests test01b_RangeSearchArrayComparison]' passed (0.263 seconds).
Test Case '-[KDTreeTests.KDTreeTests test02_STRangeSearchPerformance]' started.
/Users/tatsuyaogawa/Desktop/KDTree/Tests/KDTreeTests/KDTreeTests.swift:172: Test Case '-[KDTreeTests.KDTreeTests test02_STRangeSearchPerformance]' measured [Time, seconds] average: 0.000, relative standard deviation: 122.431%, values: [0.001302, 0.000168, 0.000153, 0.000211, 0.000162, 0.000154, 0.000149, 0.000148, 0.000193, 0.000150], performanceMetricID:com.apple.XCTPerformanceMetric_WallClockTime, baselineName: "", baselineAverage: , polarity: prefers smaller, maxPercentRegression: 10.000%, maxPercentRelativeStandardDeviation: 10.000%, maxRegression: 0.100, maxStandardDeviation: 0.100
Test Case '-[KDTreeTests.KDTreeTests test02_STRangeSearchPerformance]' passed (0.262 seconds).
Test Case '-[KDTreeTests.KDTreeTests test02b_STRangeSearchArrayComparison]' started.
/Users/tatsuyaogawa/Desktop/KDTree/Tests/KDTreeTests/KDTreeTests.swift:188: Test Case '-[KDTreeTests.KDTreeTests test02b_STRangeSearchArrayComparison]' measured [Time, seconds] average: 0.000, relative standard deviation: 66.526%, values: [0.000214, 0.000066, 0.000055, 0.000054, 0.000223, 0.000062, 0.000055, 0.000190, 0.000058, 0.000064], performanceMetricID:com.apple.XCTPerformanceMetric_WallClockTime, baselineName: "", baselineAverage: , polarity: prefers smaller, maxPercentRegression: 10.000%, maxPercentRelativeStandardDeviation: 10.000%, maxRegression: 0.100, maxStandardDeviation: 0.100
Test Case '-[KDTreeTests.KDTreeTests test02b_STRangeSearchArrayComparison]' passed (0.258 seconds).
Test Case '-[KDTreeTests.KDTreeTests test03_BuildLargeTree]' started.
Test Case '-[KDTreeTests.KDTreeTests test03_BuildLargeTree]' passed (0.204 seconds).
Test Suite 'KDTreeTests' passed at 2023-03-15 11:14:17.732.
         Executed 6 tests, with 0 failures (0 unexpected) in 1.248 (1.248) seconds
Test Suite 'KDTreePackageTests.xctest' passed at 2023-03-15 11:14:17.732.
         Executed 12 tests, with 0 failures (0 unexpected) in 2.661 (2.662) seconds
Test Suite 'All tests' passed at 2023-03-15 11:14:17.732.
         Executed 12 tests, with 0 failures (0 unexpected) in 2.661 (2.663) seconds
pointsInRangeArray.count: 34
pointsInRangeArray: 2
pointsInRangeArray.count: 27
pointsInRangeArray: 0