online compiler and debugger for c/c++

#define _USE_MATH_DEFINES #include <algorithm> #include <cassert> #include <cmath> #include <iostream> #include <optional> #include <type_traits> #include <vector> constexpr bool debugOutput = false; #ifndef QCP_PLOTTABLE_GRAPH_H struct QCPGraphData { double key, value; QCPGraphData() = default; QCPGraphData(double x, double y) : key(x), value(y) {} }; #endif auto keyLess(const QCPGraphData &l, const QCPGraphData &r) { return l.key < r.key; } #ifndef QCP_PLOTTABLE_GRAPH_H template <typename T> struct QCPDataContainer : public std::vector<T> { using std::vector<T>::vector; void sort() { std::sort(this->begin(), this->end(), keyLess); } }; using QCPGraphDataContainer = QCPDataContainer<QCPGraphData>; #endif using Point = QCPGraphData; using Container = QCPGraphDataContainer; static_assert(std::is_copy_constructible_v<Point>, "Point must be copy-constructible"); std::ostream &operator<<(std::ostream &os, const Point &p) { return os << "(" << p.key << ", " << p.value << ")"; } template <class T> bool has_unique_keys(const T &v) { constexpr auto keyEqual = [](const Point &l, const Point &r) { return l.key == r.key; }; return std::adjacent_find(std::begin(v), std::end(v), keyEqual) == std::end(v); } template <class T> bool has_valid_points(const T& v) { constexpr auto isValid = [](const Point &p) { return std::isfinite(p.key) && std::isfinite(p.value); }; return std::all_of(std::begin(v), std::end(v), isValid); } // intersection of two line segments std::optional<Point> intersection(const Point &a1, const Point &a2, const Point &b1, const Point &b2) { auto p1 = a1, p2 = a2, p3 = b1, p4 = b2; assert(p1.key <= p2.key); assert(p3.key <= p4.key); if (debugOutput) std::cout << p1 << "-" << p2 << ", " << p3 << "-" << p4; auto const denom = (p1.key - p2.key)*(p3.value - p4.value) - (p1.value - p2.value)*(p3.key - p4.key); if (fabs(denom) > 1e-6*(p2.key - p1.key)) { // the lines are not parallel auto const scale = 1.0/denom; auto const q = p1.key*p2.value - p1.value*p2.key; auto const r = p3.key*p4.value - p3.value*p4.key; auto const x = (q*(p3.key-p4.key) - (p1.key-p2.key)*r) * scale; if (debugOutput) std::cout << " x=" << x << "\n"; if (p1.key <= x && x <= p2.key && p3.key <= x && x <= p4.key) { auto const y = (q*(p3.value-p4.value) - (p1.value-p2.value)*r) * scale; return std::optional<Point>(std::in_place, x, y); } } else if (debugOutput) std::cout << "\n"; return std::nullopt; } std::vector<Point> findIntersections(const Container &a_, const Container &b_) { if (a_.size() < 2 || b_.size() < 2) return {}; static constexpr auto check = [](const auto &c){ assert(has_valid_points(c)); assert(std::is_sorted(c.begin(), c.end(), keyLess)); assert(has_unique_keys(c)); }; check(a_); check(b_); bool aFirst = a_.front().key <= b_.front().key; const auto &a = aFirst ? a_ : b_, &b = aFirst ? b_ : a_; assert(a.front().key <= b.front().key); if (a.back().key < b.front().key) return {}; // the key spams don't overlap std::vector<Point> intersections; auto ia = a.begin(), ib = b.begin(); Point a1 = *ia++, b1 = *ib++; while (ia->key < b1.key) a1=*ia++; // advance a until the key spans overlap for (Point a2 = *ia, b2 = *ib;;) { auto const ipt = intersection(a1, a2, b1, b2); if (ipt) intersections.push_back(*ipt); bool advanceA = a2.key <= b2.key, advanceB = b2.key <= a2.key; if (advanceA) { if (++ia == a.end()) break; a1 = a2, a2 = *ia; } if (advanceB) { if (++ib == b.end()) break; b1 = b2, b2 = *ib; } } return intersections; } auto findIntersections(Container &d1, Container &d2, bool presorted) { if (!presorted) { d1.sort(); d2.sort(); } return findIntersections(d1, d2); } template <typename Fun> Container makeGraph(double start, double step, double end, Fun &&fun) { Container result; int i = 0; for (auto x = start; x <= end; x = ++i * step) result.emplace_back(x, fun(x)); return result; } int main() { for (auto step2: {0.1, 0.1151484584}) { auto sinPlot = makeGraph(-2*M_PI, 0.1, 3*M_PI, sin); auto cosPlot = makeGraph(0., step2, 2*M_PI, cos); auto intersections = findIntersections(sinPlot, cosPlot); std::cout << "Intersections:\n"; for (auto &ip : intersections) std::cout << " at " << ip << "\n"; } }