Finding a point that is interior to a sector

Question

SOLVED: See my answer.

I'm trying to find a point that is interior to an arc so when a floodfill occurs it does not accidentally fill an area outside the arc. As long as the absolute value of the distance between the two angles: start and end; are less than PI this works (There are a couple extreme edge cases where the drawn lines are so close that the point picked is part of those lines, but that's for a different day...).

The problem I'm having is when the absolute value of the distance between the start and end angles is greater than PI the flood occurs on the exterior of the arc instead of the interior. One example of many is: if the arc starts at 0 and ends at 3PI/2 the absolute value of the distance is 3PI/2, the flood occurs between the angles as if the absolute value distance were PI/2 and floods the entire screen except the pac-man-shaped arc.

EDIT:

To avoid confusion, here is the definition of an arc according to allegro (and trigonometry in general):

void arc(BITMAP *bmp, int x, y, fixed ang1, ang2, int r, int color);

Draws a circular arc [minus the initial/terminal sides or center point] with centre [sic] x, y and radius r, in an anticlockwise [sic] direction starting from the angle a1 and ending when it reaches a2....Zero is to the right of the centre [sic] point, and larger values rotate anticlockwise [sic] from there.

Square brackets are my notation.

I've already taken care of converting from allegro's (stupid) use of fixed integers to the proper radian values.

END EDIT

void Arc::Draw(BITMAP* dest, int color, bool filled, bool showCenter, bool showSides) {

    if(showSides || filled) {
        Line initial(GetX(), GetY(), GetZ(), GetStartPoint().GetX(), GetStartPoint().GetY(), GetZ(), false);
        initial.SetColor(color);

        Line terminal(GetX(), GetY(), GetZ(), GetEndPoint().GetX(), GetEndPoint().GetY(), GetZ(), false);
        terminal.SetColor(color);

        initial.Draw(dest, initial.GetColor(), false);
        terminal.Draw(dest, terminal.GetColor(), false);

    } else if(showCenter) {
        putpixel(dest, GetX(), GetY(), color);
    }

    //Draw arc first to prevent flood overflow.
    arc(dest, GetX(), GetY(), AngleConverter::RadianToFixed(_startAngle), AngleConverter::RadianToFixed(_endAngle), _radius, color);

    if(filled) {

        double distance = std::fabs(this->_endAngle - this->_startAngle);
        if(distance < a2de::A2DE_PI) {

            Line displace(GetStartPoint(), GetEndPoint(), false);
            Point displacePoint(displace.GetCenter());
            floodfill(dest, displacePoint.GetX(), displacePoint.GetY(), color);

        } else if(distance > a2de::A2DE_PI) {

            Line displace(GetStartPoint(), GetEndPoint(), false);
            Vector2D center_of_displacement(displace.GetCenter());
            Vector2D center_point(this->_center);
            Vector2D direction_of_center(center_of_displacement - center_point);

            double angle = std::atan2(direction_of_center.GetY(), direction_of_center.GetX());
            Vector2D flood_point = center_point - direction_of_center;
            flood_point += angle;

            double x = flood_point.GetX() > 0.0 ? std::ceilf(flood_point.GetX()) : std::floorf(flood_point.GetX());
            double y = flood_point.GetY() > 0.0 ? std::ceilf(flood_point.GetY()) : std::floorf(flood_point.GetY());
            floodfill(dest, x, y, color);

        } else {

            if(_startAngle == 0.0 || _endAngle == a2de::A2DE_2PI) {
                floodfill(dest, GetX(), GetY() - 1, color);
            } else if(_endAngle == 0.0 || _startAngle == a2de::A2DE_PI) {
                floodfill(dest, GetX(), GetY() + 1, color);
            }

        }

    }
}

Answer 1

SOLVED:

1) Calculate Center of Arc:

double e = GetEndAngle();
double s = GetStartAngle();
double d = e - s;

double arc_center_x = 0.0;
double arc_center_y = 0.0;
double offset = 0.0;
if(d < 0.0) {
    offset = PI;
}
arc_center_x = (GetPosition().GetX() + std::cos(((s + e) / 2.0) + offset) * GetRadius());
arc_center_y = (GetPosition().GetY() + -std::sin(((s + e) / 2.0) + offset) * GetRadius());
_center = Vector2D(x, y);

2) Calculate Line from that center to the position of the sector:

Line l(arc_center_x, arc_center_y, p_x, p_y);

3) Get the mid-point of that line which is always interior to the angles of the sector:

double x = l.GetCenter().GetX();
double y = l.GetCenter().GetY();

Answer 2

First, about your 'sic' comments. The circle center point is usually called the center also of arcs, and counter clockwise is the most common convention. Just as the x axis points to the right and the y axis up, and angles start at the positive x axis.

To find out if a point x,y is within a region defined in polar coordinates (r,eta) you just convert the point x_point,y_point into polar coordinates

r_point=sqrt((x_point-x_circle)^2 + (y_point-y_circle)^2 )
eta_point=atan2((y_point-y_circle) , (y_point-x_circle))

Use atan2, then you need not think about signs and pi-flips etc. what is the difference between atan and atan2 in c++?

Now, is the radious within the 'sector' ?
if (r_point<r_sector) ... 

If that's the case it's worth taking a look at the angular part: Subtract the star angle from both eta_point and the angular size of the sector

eta_point_new = eta_point - ang1
ang2_new = ang2 - ang1

Now, ang2_new is how big the sector is in the rotational direction, and eta_point_new is how far away the point is. If ang2_new is negative, it means the sector crossed the border of your angular coordinate, so you need to add 2pi to it. Then:

if (eta_point_new < ang2_new) 
   ... then the point is inside...

I'm sorry that I did not have time to test this or write it in proper C++, do with it what you like.

Answer 3

The positive rotation direction is counterclockwise. I am giving pseudocode, not a real C++ code.

To determine the angle of rotation, subtract start angle from end angle. Do not take the absolute value. Normalize to the interval [0, 2π).

rot_angle = end_angle - start_angle;

while (rot_angle < 0)   
  rot_angle += TWO_PI;

Now we need to take a point halfway between the center and the start point of the arc, and rotate it around the center by the one half of the total angle of rotation we have just found:

start_point = rotate (point (center.x+r, center.y), center, start_angle);
interior_point = rotate (midpoint (center, start_point), center, rot_angle/2);

To rotate a point pt about an origin o by an angle of theta:

point rotate (point pt, point o, double theta)
{
  return point(cos(theta) * (pt.x-o.x) - sin(theta) * (pt.y-o.y) + o.x,
               sin(theta) * (pt.x-o.x) + cos(theta) * (pt.y-o.y) + o.y);

}

For completeness:

point midpoint (point p1, point p2)
{
   return point((p1.x+p2.x)/2, (p1.y+p2.y)/2);
}