1*c8dee2aaSAndroid Build Coastguard Worker // Copyright 2023 Google LLC 2*c8dee2aaSAndroid Build Coastguard Worker // Use of this source code is governed by a BSD-style license that can be found in the LICENSE file. 3*c8dee2aaSAndroid Build Coastguard Worker 4*c8dee2aaSAndroid Build Coastguard Worker #ifndef BentleyOttman1_DEFINED 5*c8dee2aaSAndroid Build Coastguard Worker #define BentleyOttman1_DEFINED 6*c8dee2aaSAndroid Build Coastguard Worker 7*c8dee2aaSAndroid Build Coastguard Worker #include "include/core/SkSpan.h" 8*c8dee2aaSAndroid Build Coastguard Worker 9*c8dee2aaSAndroid Build Coastguard Worker #include <optional> 10*c8dee2aaSAndroid Build Coastguard Worker #include <vector> 11*c8dee2aaSAndroid Build Coastguard Worker 12*c8dee2aaSAndroid Build Coastguard Worker namespace bentleyottmann { 13*c8dee2aaSAndroid Build Coastguard Worker struct Crossing; 14*c8dee2aaSAndroid Build Coastguard Worker struct Segment; 15*c8dee2aaSAndroid Build Coastguard Worker 16*c8dee2aaSAndroid Build Coastguard Worker // Takes in a list of segments, and returns intersection points found in the list of segments. 17*c8dee2aaSAndroid Build Coastguard Worker // A return value of nullopt means that the data are out of range. An empty vector means there 18*c8dee2aaSAndroid Build Coastguard Worker // are no self intersections. 19*c8dee2aaSAndroid Build Coastguard Worker // 20*c8dee2aaSAndroid Build Coastguard Worker // If nullopt is returned, you could divide all your points by 2, and try again. 21*c8dee2aaSAndroid Build Coastguard Worker std::optional<std::vector<Crossing>> bentley_ottmann_1(SkSpan<const Segment> segments); 22*c8dee2aaSAndroid Build Coastguard Worker } // namespace bentleyottmann 23*c8dee2aaSAndroid Build Coastguard Worker 24*c8dee2aaSAndroid Build Coastguard Worker #endif // BentleyOttman1_DEFINED 25