SHARE
TWEET

Untitled

a guest Jan 13th, 2009 471 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #pragma once
  2.  
  3. #include <vector>
  4. #include <cmath>
  5.  
  6. #include "Vector2.hpp"
  7.  
  8. namespace IntersectionFunctions
  9. {
  10.         struct IntersectionObject
  11.         {
  12.                 std::vector<Vector2> points;
  13.  
  14.                 void InsertSolution(float x, float y)
  15.                 {
  16.                         points.push_back(Vector2(x, y));
  17.                 }
  18.  
  19.                 void InsertSolution(Vector2 v)
  20.                 {
  21.                         points.push_back(v);
  22.                 }
  23.  
  24.                 int NumberOfSolutions()
  25.                 {
  26.                         return points.size();
  27.                 }
  28.         };
  29.  
  30.         // Circle to Circle
  31.         IntersectionObject CircleToCircleIntersection(float x0_, float y0_, float r0_,
  32.                                                                                                   float x1_, float y1_, float r1_)
  33.         {
  34.                 IntersectionObject result;
  35.                 float a, dist, h;
  36.                 Vector2 d, r, v2;
  37.  
  38.                 // d is the vertical and horizontal distances between the circle centers
  39.                 d = Vector2(x1_ - x0_, y1_ - y0_);
  40.  
  41.                 //distance between the circles
  42.                 dist = d.Length();
  43.  
  44.                 // Check for equality and infinite intersections exist
  45.                 if (dist == 0 && r0_ == r1_)
  46.                 {
  47.                         return result;
  48.                 }
  49.  
  50.                 //Check for solvability
  51.                 if (dist > r0_ + r1_)
  52.                 {
  53.                         // no solution. circles do not intersect
  54.                         return result;
  55.                 }
  56.                 if (dist < abs(r0_ - r1_))
  57.                 {
  58.                         // no solution. one circle is contained in the other
  59.                         return result;
  60.                 }
  61.                 if (dist == r0_ + r1_)
  62.                 {
  63.                         //one solution
  64.                         result.InsertSolution((x0_ - x1_) / (r0_ + r1_) * r0_ + x1_, (y0_ - y1_) / (r0_ + r1_) * r0_ + y1_);
  65.                         return result;
  66.                 }
  67.  
  68.                 /* 'point 2' is the point where the line through the circle
  69.                  * intersection points crosses the line between the circle
  70.                  * centers.
  71.                  */
  72.  
  73.                 // Determine the distance from point 0 to point 2
  74.                 a = ((r0_ * r0_) - (r1_ * r1_) + (dist * dist)) / (2.0f * dist);
  75.  
  76.                 // Determine the coordinates of point 2
  77.                 v2 = Vector2(x0_ + (d.x * a / dist), y0_ + (d.y * a / dist));
  78.  
  79.                 // Determine the distance from point 2 to either of the intersection points
  80.                 h = sqrt((r0_ * r0_) - (a * a));
  81.  
  82.                 // Now determine the offsets of the intersection points from point 2
  83.                 r = Vector2(-d.y * (h / dist), d.x * (h / dist));
  84.  
  85.                 // Determine the absolute intersection points
  86.                 result.InsertSolution(v2 + r);
  87.                 result.InsertSolution(v2 - r);
  88.  
  89.                 return result;
  90.         }
  91.  
  92.         //Line to Circle
  93.         IntersectionObject LineToCircleIntersection(float x1_, float y1_, float x2_, float y2_,
  94.                                                                                                 float x3_, float y3_, float r3_)
  95.         {
  96.                 IntersectionObject result;
  97.                 Vector2 v1, v2;
  98.                 // Vector from point 1 to point 2
  99.                 v1 = Vector2(x2_ - x1_, y2_ - y1_);
  100.                 // Vector from point 1 to the circle's center
  101.                 v2 = Vector2(x3_ - x1_, y3_ - y1_);
  102.  
  103.                 float dot = v1.x * v2.x + v1.y * v2.y;
  104.                 Vector2 proj1 = Vector2(((dot / (v1.LengthSq())) * v1.x), ((dot / (v1.LengthSq())) * v1.y));
  105.                 Vector2 midpt = Vector2(x1_ + proj1.x, y1_ + proj1.y);
  106.  
  107.                 float distToCenter = (midpt.x - x3_) * (midpt.x - x3_) + (midpt.y - y3_) * (midpt.y - y3_);
  108.                 if (distToCenter > r3_ * r3_) return result;
  109.                 if (distToCenter == r3_ * r3_)
  110.                 {
  111.                         result.InsertSolution(midpt);
  112.                         return result;
  113.                 }
  114.                 float distToIntersection;
  115.                 if (distToCenter == 0)
  116.                 {
  117.                         distToIntersection = r3_;
  118.                 }
  119.                 else
  120.                 {
  121.                         distToCenter = sqrt(distToCenter);
  122.                         distToIntersection = sqrt(r3_ * r3_ - distToCenter * distToCenter);
  123.                 }
  124.                 float lineSegmentLength = 1 / v1.Length();
  125.                 v1 *= lineSegmentLength;
  126.                 v1 *= distToIntersection;
  127.  
  128.                 result.InsertSolution(midpt + v1);
  129.                 result.InsertSolution(midpt - v1);
  130.  
  131.                 return result;
  132.         }
  133.  
  134.         // Circle to Line
  135.         IntersectionObject CircleToLineIntersection(float x1_, float y1_, float r1_,
  136.                                                                                                 float x2_, float y2_, float x3_, float y3_)
  137.         {
  138.                 return LineToCircleIntersection(x2_, y2_, x3_, y3_, x1_, y1_, r1_);
  139.         }
  140.  
  141.         // LineSegment to Circle
  142.         IntersectionObject LineSegmentToCircleIntersection(float x1_, float y1_, float x2_, float y2_,
  143.                                                                                                            float x3_, float y3_, float r3_)
  144.         {
  145.                 IntersectionObject result;
  146.                 Vector2 v1, v2;
  147.                 // Vector from point 1 to point 2
  148.                 v1 = Vector2(x2_ - x1_, y2_ - y1_);
  149.                 // Vector from point 1 to the circle's center
  150.                 v2 = Vector2(x3_ - x1_, y3_ - y1_);
  151.  
  152.                 float dot = v1.x * v2.x + v1.y * v2.y;
  153.                 Vector2 proj1 = Vector2(((dot / (v1.LengthSq())) * v1.x), ((dot / (v1.LengthSq())) * v1.y));
  154.  
  155.                 Vector2 midpt = Vector2(x1_ + proj1.x, y1_ + proj1.y);
  156.                 float distToCenter = (midpt.x - x3_) * (midpt.x - x3_) + (midpt.y - y3_) * (midpt.y - y3_);
  157.                 if (distToCenter > r3_ * r3_) return result;
  158.                 if (distToCenter == r3_ * r3_)
  159.                 {
  160.                         result.InsertSolution(midpt);
  161.                         return result;
  162.                 }
  163.                 float distToIntersection;
  164.                 if (distToCenter == 0)
  165.                 {
  166.                         distToIntersection = r3_;
  167.                 }
  168.                 else
  169.                 {
  170.                         distToCenter = sqrt(distToCenter);
  171.                         distToIntersection = sqrt(r3_ * r3_ - distToCenter * distToCenter);
  172.                 }
  173.                 float lineSegmentLength = 1 / v1.Length();
  174.                 v1 *= lineSegmentLength;
  175.                 v1 *= distToIntersection;
  176.  
  177.                 Vector2 solution1 = midpt + v1;
  178.                 if ((solution1.x - x1_) * v1.x + (solution1.y - y1_) * v1.y > 0 &&
  179.                     (solution1.x - x2_) * v1.x + (solution1.y - y2_) * v1.y < 0)
  180.                 {
  181.                         result.InsertSolution(solution1);
  182.                 }
  183.                 Vector2 solution2 = midpt - v1;
  184.                 if ((solution2.x - x1_) * v1.x + (solution2.y - y1_) * v1.y > 0 &&
  185.                     (solution2.x - x2_) * v1.x + (solution2.y - y2_) * v1.y < 0)
  186.                 {
  187.                         result.InsertSolution(solution2);
  188.                 }
  189.                 return result;
  190.         }
  191.  
  192.         // Circle to LineSegment
  193.         IntersectionObject CircleToLineSegmentIntersection(float x1_, float y1_, float r1_,
  194.                                                                                                            float x2_, float y2_, float x3_, float y3_)
  195.         {
  196.                 return LineSegmentToCircleIntersection(x2_, y2_, x3_, y3_, x1_, y1_, r1_);
  197.         }
  198.  
  199.         // Ray to Circle
  200.         IntersectionObject RayToCircleIntersection(float x1_, float y1_, float x2_, float y2_,
  201.         float x3_, float y3_, float r3_)
  202.         {
  203.                 IntersectionObject result;
  204.                 Vector2 v1, v2;
  205.                 // Vector from point 1 to point 2
  206.                 v1 = Vector2(x2_ - x1_, y2_ - y1_);
  207.                 // Vector from point 1 to the circle's center
  208.                 v2 = Vector2(x3_ - x1_, y3_ - y1_);
  209.  
  210.                 float dot = v1.x * v2.x + v1.y * v2.y;
  211.                 Vector2 proj1 = Vector2(((dot / (v1.LengthSq())) * v1.x), ((dot / (v1.LengthSq())) * v1.y));
  212.  
  213.                 Vector2 midpt = Vector2(x1_ + proj1.x, y1_ + proj1.y);
  214.                 float distToCenter = (midpt.x - x3_) * (midpt.x - x3_) + (midpt.y - y3_) * (midpt.y - y3_);
  215.                 if (distToCenter > r3_ * r3_) return result;
  216.                 if (distToCenter == r3_ * r3_)
  217.                 {
  218.                         result.InsertSolution(midpt);
  219.                         return result;
  220.                 }
  221.                 float distToIntersection;
  222.                 if (distToCenter == 0)
  223.                 {
  224.                         distToIntersection = r3_;
  225.                 }
  226.                 else
  227.                 {
  228.                         distToCenter = sqrt(distToCenter);
  229.                         distToIntersection = sqrt(r3_ * r3_ - distToCenter * distToCenter);
  230.                 }
  231.                 float lineSegmentLength = 1 / v1.Length();
  232.                 v1 *= lineSegmentLength;
  233.                 v1 *= distToIntersection;
  234.  
  235.                 Vector2 solution1 = midpt + v1;
  236.                 if ((solution1.x - x1_) * v1.x + (solution1.y - y1_) * v1.y > 0)
  237.                 {
  238.                         result.InsertSolution(solution1);
  239.                 }
  240.                 Vector2 solution2 = midpt - v1;
  241.                 if ((solution2.x - x1_) * v1.x + (solution2.y - y1_) * v1.y > 0)
  242.                 {
  243.                         result.InsertSolution(solution2);
  244.                 }
  245.                 return result;
  246.         }
  247.  
  248.         // Circle to Ray
  249.         IntersectionObject CircleToRayIntersection(float x1_, float y1_, float r1_,
  250.         float x2_, float y2_, float x3_, float y3_)
  251.         {
  252.                 return RayToCircleIntersection(x2_, y2_, x3_, y3_, x1_, y1_, r1_);
  253.         }
  254.  
  255.         // Line to Line
  256.         IntersectionObject LineToLineIntersection(float x1_, float y1_, float x2_, float y2_,
  257.                                                                                           float x3_, float y3_, float x4_, float y4_)
  258.         {
  259.                 IntersectionObject result;
  260.                 float r, s, d;
  261.                 // Make sure the lines aren't parallel
  262.                 if ((y2_ - y1_) / (x2_ - x1_) != (y4_ - y3_) / (x4_ - x3_))
  263.                 {
  264.                         d = (((x2_ - x1_) * (y4_ - y3_)) - (y2_ - y1_) * (x4_ - x3_));
  265.                         if (d != 0)
  266.                         {
  267.                                 r = (((y1_ - y3_) * (x4_ - x3_)) - (x1_ - x3_) * (y4_ - y3_)) / d;
  268.                                 s = (((y1_ - y3_) * (x2_ - x1_)) - (x1_ - x3_) * (y2_ - y1_)) / d;
  269.  
  270.                                 result.InsertSolution(x1_ + r * (x2_ - x1_), y1_ + r * (y2_ - y1_));
  271.                         }
  272.                 }
  273.                 return result;
  274.         }
  275.  
  276.         // LineSegment to LineSegment
  277.         IntersectionObject LineSegmentToLineSegmentIntersection(float x1_, float y1_, float x2_, float y2_,
  278.                                                                                                                         float x3_, float y3_, float x4_, float y4_)
  279.         {
  280.                 IntersectionObject result;
  281.                 float r, s, d;
  282.                 //Make sure the lines aren't parallel
  283.                 if ((y2_ - y1_) / (x2_ - x1_) != (y4_ - y3_) / (x4_ - x3_))
  284.                 {
  285.                         d = (((x2_ - x1_) * (y4_ - y3_)) - (y2_ - y1_) * (x4_ - x3_));
  286.                         if (d != 0)
  287.                         {
  288.                                 r = (((y1_ - y3_) * (x4_ - x3_)) - (x1_ - x3_) * (y4_ - y3_)) / d;
  289.                                 s = (((y1_ - y3_) * (x2_ - x1_)) - (x1_ - x3_) * (y2_ - y1_)) / d;
  290.                                 if (r >= 0 && r <= 1)
  291.                                 {
  292.                                         if (s >= 0 && s <= 1)
  293.                                         {
  294.                                                 result.InsertSolution(x1_ + r * (x2_ - x1_), y1_ + r * (y2_ - y1_));
  295.                                         }
  296.                                 }
  297.                         }
  298.                 }
  299.                 return result;
  300.         }
  301.  
  302.         // LineSegment to Line
  303.         IntersectionObject LineSegmentToLineIntersection(float x1_, float y1_, float x2_, float y2_,
  304.                                                                                                          float x3_, float y3_, float x4_, float y4_)
  305.         {
  306.                 IntersectionObject result;
  307.                 float r, s, d;
  308.                 // Make sure the lines aren't parallel
  309.                 if ((y2_ - y1_) / (x2_ - x1_) != (y4_ - y3_) / (x4_ - x3_))
  310.                 {
  311.                         d = (((x2_ - x1_) * (y4_ - y3_)) - (y2_ - y1_) * (x4_ - x3_));
  312.                         if (d != 0)
  313.                         {
  314.                                 r = (((y1_ - y3_) * (x4_ - x3_)) - (x1_ - x3_) * (y4_ - y3_)) / d;
  315.                                 s = (((y1_ - y3_) * (x2_ - x1_)) - (x1_ - x3_) * (y2_ - y1_)) / d;
  316.                                 if (r >= 0 && r <= 1)
  317.                                 {
  318.                                         result.InsertSolution(x1_ + r * (x2_ - x1_), y1_ + r * (y2_ - y1_));
  319.                                 }
  320.                         }
  321.                 }
  322.                 return result;
  323.         }
  324.  
  325.         // Line to LineSement
  326.         IntersectionObject LineToLineSegmentIntersection(float x1_, float y1_, float x2_, float y2_,
  327.                                                                                                          float x3_, float y3_, float x4_, float y4_)
  328.         {
  329.                 return LineSegmentToLineIntersection(x3_, y3_, x4_, y4_, x1_, y1_, x2_, y2_);
  330.         }
  331.  
  332.         // Ray to LineSegment
  333.         IntersectionObject RayToLineSegmentIntersection(float x1_, float y1_, float x2_, float y2_,
  334.                                                                                                         float x3_, float y3_, float x4_, float y4_)
  335.         {
  336.                 IntersectionObject result;
  337.                 float r, s, d;
  338.                 // Make sure the lines aren't parallel
  339.                 if ((y2_ - y1_) / (x2_ - x1_) != (y4_ - y3_) / (x4_ - x3_))
  340.                 {
  341.                         d = (((x2_ - x1_) * (y4_ - y3_)) - (y2_ - y1_) * (x4_ - x3_));
  342.                         if (d != 0)
  343.                         {
  344.                                 r = (((y1_ - y3_) * (x4_ - x3_)) - (x1_ - x3_) * (y4_ - y3_)) / d;
  345.                                 s = (((y1_ - y3_) * (x2_ - x1_)) - (x1_ - x3_) * (y2_ - y1_)) / d;
  346.                                 if (r >= 0)
  347.                                 {
  348.                                         if (s >= 0 && s <= 1)
  349.                                         {
  350.                                                 result.InsertSolution(x1_ + r * (x2_ - x1_), y1_ + r * (y2_ - y1_));
  351.                                         }
  352.                                 }
  353.                         }
  354.                 }
  355.                 return result;
  356.         }
  357.  
  358.         // LineSegment to Ray
  359.         IntersectionObject LineSegmentToRayIntersection(float x1_, float y1_, float x2_, float y2_,
  360.                                                                                                         float x3_, float y3_, float x4_, float y4_)
  361.         {
  362.                 return RayToLineSegmentIntersection(x3_, y3_, x4_, y4_, x1_, y1_, x2_, y2_);
  363.         }
  364.  
  365.         // Ray to Line
  366.         IntersectionObject RayToLineIntersection(float x1_, float y1_, float x2_, float y2_,
  367.                                                                                          float x3_, float y3_, float x4_, float y4_)
  368.         {
  369.                 IntersectionObject result;
  370.                 float r, s, d;
  371.                 // Make sure the lines aren't parallel
  372.                 if ((y2_ - y1_) / (x2_ - x1_) != (y4_ - y3_) / (x4_ - x3_))
  373.                 {
  374.                         d = (((x2_ - x1_) * (y4_ - y3_)) - (y2_ - y1_) * (x4_ - x3_));
  375.                         if (d != 0)
  376.                         {
  377.                                 r = (((y1_ - y3_) * (x4_ - x3_)) - (x1_ - x3_) * (y4_ - y3_)) / d;
  378.                                 s = (((y1_ - y3_) * (x2_ - x1_)) - (x1_ - x3_) * (y2_ - y1_)) / d;
  379.                                 if (r >= 0)
  380.                                 {
  381.                                         result.InsertSolution(x1_ + r * (x2_ - x1_), y1_ + r * (y2_ - y1_));
  382.                                 }
  383.                         }
  384.                 }
  385.                 return result;
  386.         }
  387.  
  388.         // Line to Ray
  389.         IntersectionObject LineToRayIntersection(float x1_, float y1_, float x2_, float y2_,
  390.                                                                                          float x3_, float y3_, float x4_, float y4_)
  391.         {
  392.                 return RayToLineIntersection(x3_, y3_, x4_, y4_, x1_, y1_, x2_, y2_);
  393.         }
  394.  
  395.         // Ray to Ray
  396.         IntersectionObject RayToRayIntersection(float x1_, float y1_, float x2_, float y2_,
  397.                                                                                         float x3_, float y3_, float x4_, float y4_)
  398.         {
  399.                 IntersectionObject result;
  400.                 float r, s, d;
  401.                 // Make sure the lines aren't parallel
  402.                 if ((y2_ - y1_) / (x2_ - x1_) != (y4_ - y3_) / (x4_ - x3_))
  403.                 {
  404.                         d = (((x2_ - x1_) * (y4_ - y3_)) - (y2_ - y1_) * (x4_ - x3_));
  405.                         if (d != 0)
  406.                         {
  407.                                 r = (((y1_ - y3_) * (x4_ - x3_)) - (x1_ - x3_) * (y4_ - y3_)) / d;
  408.                                 s = (((y1_ - y3_) * (x2_ - x1_)) - (x1_ - x3_) * (y2_ - y1_)) / d;
  409.                                 if (r >= 0)
  410.                                 {
  411.                                         if (s >= 0)
  412.                                         {
  413.                                                 result.InsertSolution(x1_ + r * (x2_ - x1_), y1_ + r * (y2_ - y1_));
  414.                                         }
  415.                                 }
  416.                         }
  417.                 }
  418.                 return result;
  419.         }
  420. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top