algorithm - Find the arc of the intersection between circle and rectangle -


i need find largest arc created intersection of circle , rectangle. have center of circle, radius , coordinates of rectangle, , need find angle of intersection points center of circle.

problem diagram

i have code works, computes solution iterating points of circumference, , wondering if there's more elegant way calculate solution using trigonometry instead of "brute force".

that's code:

import 'dart:math';  class circlethesquare {   final point     _circlecenter;   final int       _circleradius;   final rectangle _box;     circlethesquare(this._circlecenter, this._circleradius, this._box);     map<string, double> arc {     map res = new map();      double angle = .0;     double anglein;     double angleout;     double increment = 1.0;      while (true) {       if (angle > 360.0 && anglein == null) {         break;       }        // finds point of intersection (next points inside        // of rectangle).       if (!_isoutside(angle) && _isoutside(angle - increment)) {         anglein = angle;       }        // finds next intersection (next points outside        // of rectangle).       if (anglein != null &&           _isoutside(angle + increment) && !_isoutside(angle)) {          angleout = angle;          // adds arc result there's not previous largest arc.         if (res["in"] == null ||             angleout - anglein > res["arc"]) {            res["in"]  = anglein;           res["arc"] = angleout - anglein;         }         anglein = null;         angleout = null;       }       angle += increment;     }      // if there's no intersections.      // -- simplicity, assume     //    rectangle , circle intersect or circle      //    inside of rectangle).     if (res["in"] == null) {       res = {"in" : 0.0, "arc" : 360.0};     }      return res;   }     bool _isoutside(double a) {     var res;      double cx = _circlecenter.x + (_circleradius * cos(a * (pi / 180)));     double cy = _circlecenter.y + (_circleradius * sin(a * (pi / 180)));      bool hout = cx < _box.left || cx > _box.left + _box.width;     bool vout = cy < _box.top || cy > _box.top + _box.height;      if (hout || vout) {       res = true;     } else {       res = false;     }      return res;   } }   main() {   circlethesquare = new circlethesquare(new point(250, 250), 100,                                           new rectangle(0,0,500,500));    print(a.arc); // {in: 0.0, arc: 360.0}    circlethesquare b = new circlethesquare(new point(450, 250), 100,                                           new rectangle(0,0,500,500));    print(b.arc); // {in: 60.0, arc: 240.0}    circlethesquare c = new circlethesquare(new point(420, 420), 100,                                           new rectangle(0,0,500,500));    print(c.arc); // 4 intersections, returns largest arc:                           // {in: 127.0, arc: 196.0} } 

  1. shift coordinates make circle zero-centered (box.left = box.left - circlecenter.x etc) simplicity
  2. find intersections of circle sides of rectangle. example, left side solve (box.left)^2 + y^2 = radius^2, check point lies on side, add intersection point list
  3. sort intersection points angle (probably, automatically provided side check order), find largest angle interval arcs inside rectangle

Comments

Popular posts from this blog

android - Get AccessToken using signpost OAuth without opening a browser (Two legged Oauth) -

org.mockito.exceptions.misusing.InvalidUseOfMatchersException: mockito -

google shop client API returns 400 bad request error while adding an item -