diff options
Diffstat (limited to 'extern/carve/lib/geom2d.cpp')
-rw-r--r-- | extern/carve/lib/geom2d.cpp | 266 |
1 files changed, 0 insertions, 266 deletions
diff --git a/extern/carve/lib/geom2d.cpp b/extern/carve/lib/geom2d.cpp deleted file mode 100644 index 0e8f3a9377c..00000000000 --- a/extern/carve/lib/geom2d.cpp +++ /dev/null @@ -1,266 +0,0 @@ -// Begin License: -// Copyright (C) 2006-2014 Tobias Sargeant (tobias.sargeant@gmail.com). -// All rights reserved. -// -// This file is part of the Carve CSG Library (http://carve-csg.com/) -// -// This file may be used under the terms of either the GNU General -// Public License version 2 or 3 (at your option) as published by the -// Free Software Foundation and appearing in the files LICENSE.GPL2 -// and LICENSE.GPL3 included in the packaging of this file. -// -// This file is provided "AS IS" with NO WARRANTY OF ANY KIND, -// INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR -// A PARTICULAR PURPOSE. -// End: - - -#if defined(HAVE_CONFIG_H) -# include <carve_config.h> -#endif - -#include <carve/geom2d.hpp> -#include <carve/math.hpp> -#include <carve/aabb.hpp> - -#include <algorithm> -#include <iostream> - -namespace carve { - namespace geom2d { - - bool lineSegmentIntersection_simple(const P2 &l1v1, const P2 &l1v2, - const P2 &l2v1, const P2 &l2v2) { - geom::aabb<2> l1_aabb, l2_aabb; - l1_aabb.fit(l1v1, l1v2); - l2_aabb.fit(l2v1, l2v2); - - if (l1_aabb.maxAxisSeparation(l2_aabb) > 0.0) { - return false; - } - - double l1v1_side = orient2d(l2v1, l2v2, l1v1); - double l1v2_side = orient2d(l2v1, l2v2, l1v2); - - double l2v1_side = orient2d(l1v1, l1v2, l2v1); - double l2v2_side = orient2d(l1v1, l1v2, l2v2); - - if (l1v1_side * l1v2_side > 0.0 || l2v1_side * l2v2_side > 0.0) { - return false; - } - - return true; - } - - bool lineSegmentIntersection_simple(const LineSegment2 &l1, - const LineSegment2 &l2) { - return lineSegmentIntersection_simple(l1.v1, l1.v2, l2.v1, l2.v2); - } - - LineIntersectionInfo lineSegmentIntersection(const P2 &l1v1, const P2 &l1v2, - const P2 &l2v1, const P2 &l2v2) { - geom::aabb<2> l1_aabb, l2_aabb; - l1_aabb.fit(l1v1, l1v2); - l2_aabb.fit(l2v1, l2v2); - - if (l1_aabb.maxAxisSeparation(l2_aabb) > EPSILON) { - return LineIntersectionInfo(NO_INTERSECTION); - } - - if (carve::geom::equal(l1v1, l1v2) || carve::geom::equal(l2v1, l2v2)) { - throw carve::exception("zero length line in intersection test"); - } - - double dx13 = l1v1.x - l2v1.x; - double dy13 = l1v1.y - l2v1.y; - double dx43 = l2v2.x - l2v1.x; - double dy43 = l2v2.y - l2v1.y; - double dx21 = l1v2.x - l1v1.x; - double dy21 = l1v2.y - l1v1.y; - double ua_n = dx43 * dy13 - dy43 * dx13; - double ub_n = dx21 * dy13 - dy21 * dx13; - double u_d = dy43 * dx21 - dx43 * dy21; - - if (carve::math::ZERO(u_d)) { - if (carve::math::ZERO(ua_n)) { - if (carve::geom::equal(l1v2, l2v1)) { - return LineIntersectionInfo(INTERSECTION_PP, l1v2, 1, 2); - } - if (carve::geom::equal(l1v1, l2v2)) { - return LineIntersectionInfo(INTERSECTION_PP, l1v1, 0, 4); - } - if (l1v2.x > l2v1.x && l1v1.x < l2v2.x) { - return LineIntersectionInfo(COLINEAR); - } - } - return LineIntersectionInfo(NO_INTERSECTION); - } - - double ua = ua_n / u_d; - double ub = ub_n / u_d; - - if (-EPSILON <= ua && ua <= 1.0 + EPSILON && -EPSILON <= ub && ub <= 1.0 + EPSILON) { - double x = l1v1.x + ua * (l1v2.x - l1v1.x); - double y = l1v1.y + ua * (l1v2.y - l1v1.y); - - P2 p = carve::geom::VECTOR(x, y); - - double d1 = distance2(p, l1v1); - double d2 = distance2(p, l1v2); - double d3 = distance2(p, l2v1); - double d4 = distance2(p, l2v2); - - int n = -1; - - if (std::min(d1, d2) < EPSILON2) { - if (d1 < d2) { - p = l1v1; n = 0; - } else { - p = l1v2; n = 1; - } - if (std::min(d3, d4) < EPSILON2) { - if (d3 < d4) { - return LineIntersectionInfo(INTERSECTION_PP, p, n, 2); - } else { - return LineIntersectionInfo(INTERSECTION_PP, p, n, 3); - } - } else { - return LineIntersectionInfo(INTERSECTION_PL, p, n, -1); - } - } else if (std::min(d3, d4) < EPSILON2) { - if (d3 < d4) { - return LineIntersectionInfo(INTERSECTION_LP, l2v1, -1, 2); - } else { - return LineIntersectionInfo(INTERSECTION_LP, l2v2, -1, 3); - } - } else { - return LineIntersectionInfo(INTERSECTION_LL, p, -1, -1); - } - } - return LineIntersectionInfo(NO_INTERSECTION); - } - - LineIntersectionInfo lineSegmentIntersection(const LineSegment2 &l1, - const LineSegment2 &l2) { - return lineSegmentIntersection(l1.v1, l1.v2, l2.v1, l2.v2); - } - - double signedArea(const P2Vector &points) { - return signedArea(points, p2_adapt_ident()); - } - - bool pointInPolySimple(const P2Vector &points, const P2 &p) { - return pointInPolySimple(points, p2_adapt_ident(), p); - } - - PolyInclusionInfo pointInPoly(const P2Vector &points, const P2 &p) { - return pointInPoly(points, p2_adapt_ident(), p); - } - -#if 0 - static int lineSegmentPolyIntersections(const P2Vector &points, - LineSegment2 line, - std::vector<PolyIntersectionInfo> &out) { - int count = 0; - - if (line.v2 < line.v1) { line.flip(); } - out.clear(); - - for (P2Vector::size_type i = 0, l = points.size(); i < l; i++) { - P2Vector::size_type j = (i + 1) % l; - LineIntersectionInfo e = - lineSegmentIntersection(LineSegment2(points[i], points[j]), line); - - switch (e.iclass) { - case INTERSECTION_PL: { - out.push_back(PolyIntersectionInfo(INTERSECT_EDGE, e.ipoint, i)); - count++; - break; - } - case INTERSECTION_PP: { - out.push_back(PolyIntersectionInfo(INTERSECT_VERTEX, e.ipoint, i + (size_t)e.p2 - 2)); - count++; - break; - } - case INTERSECTION_LP: { - out.push_back(PolyIntersectionInfo(INTERSECT_VERTEX, e.ipoint, i + (size_t)e.p2 - 2)); - count++; - break; - } - case INTERSECTION_LL: { - out.push_back(PolyIntersectionInfo(INTERSECT_EDGE, e.ipoint, i)); - count++; - break; - } - case COLINEAR: { - size_t n1 = i; - size_t n2 = j; - - P2 q1 = points[i], q2 = points[j]; - - if (q2 < q1) { std::swap(q1, q2); std::swap(n1, n2); } - - if (equal(q1, line.v1)) { - out.push_back(PolyIntersectionInfo(INTERSECT_VERTEX, q1, n1)); - } else if (q1.x < line.v1.x) { - out.push_back(PolyIntersectionInfo(INTERSECT_EDGE, line.v1, i)); - } else { - out.push_back(PolyIntersectionInfo(INTERSECT_VERTEX, q1, n1)); - } - if (equal(q2, line.v2)) { - out.push_back(PolyIntersectionInfo(INTERSECT_VERTEX, q2, n2)); - } else if (line.v2.x < q2.x) { - out.push_back(PolyIntersectionInfo(INTERSECT_EDGE, line.v2, i)); - } else { - out.push_back(PolyIntersectionInfo(INTERSECT_VERTEX, q2, n2)); - } - - count += 2; - - break; - } - default: - break; - } - } - return count; - } -#endif - - struct FwdSort { - bool operator()(const PolyIntersectionInfo &a, - const PolyIntersectionInfo &b) const { - return a.ipoint < b.ipoint; - } - }; - - struct RevSort { - bool operator()(const PolyIntersectionInfo &a, - const PolyIntersectionInfo &b) const { - return a.ipoint < b.ipoint; - } - }; - -#if 0 - static int sortedLineSegmentPolyIntersections(const P2Vector &points, - LineSegment2 line, - std::vector<PolyIntersectionInfo> &out) { - - bool swapped = line.v2 < line.v1; - - int count = lineSegmentPolyIntersections(points, line, out); - if (swapped) { - std::sort(out.begin(), out.end(), RevSort()); - } else { - std::sort(out.begin(), out.end(), FwdSort()); - } - return count; - } -#endif - - bool pickContainedPoint(const std::vector<P2> &poly, P2 &result) { - return pickContainedPoint(poly, p2_adapt_ident(), result); - } - - } -} |