Algorithm to detect the point intersect the semi circle in android Java

Question

I have a points x and y and I need to check the point which intersect within a semi- pie.

I need an algorithm to find the point is intersect in the semi circle. for rectangle we have point contains method to check the point intersect the rectangle, but this doesn't work for semi circle segments with start and end angle.

I have created many semi pie segment, when I touch the pie segment, I need to check the point intersect of which segment.

Sorry, but I need a bit of clarification. Do you simply want to find all the points that reside inside a semicircle? How is the semicircle defined? — SMBiggs, Jan 28 '15 at 05:10
@Suresh if you know the center and radius of circle then get the distance between the point and center. If the distance is larger than radius i.e. does not intersect within else interest. — Ajit, Jan 28 '15 at 05:21
This is fine for full circle, I need to get the point intersect for semi circle, like a arc. — Suresh Balaraman, Jan 28 '15 at 05:58
I'll go with Ajit's solution but how is this semicircle positioned? if it is vertical or horizontal, it should be easy just to check for x and y value starting from the radius. — Apple, Jan 28 '15 at 06:11
I have placed the pie in many places , based on start and end angle — Suresh Balaraman, Jan 28 '15 at 06:15
Please don't copy and paste existing questions. That is not allowed. If you have a unique problem, please state it in your own words. Otherwise it's hard not to see this as just a duplicate of the question you copied. — BoltClock, Jan 28 '15 at 10:34

samgak · Accepted Answer · 2015-01-28T10:34:32.227

I'm assuming this is speed-critical, and also that you want to be able to specify the semi-circle as having a center and arbitrary start and end angles, so not just a semi-circle but a circular sector. For a semi-circle just make the start and end angles 180 degrees apart, or remove the test against endVector.

Make the test a two-step process. For a given point, first check that it is inside a rectangle enclosing the semi-circle. You can use your existing sort and binary search algorithm for this. If a point is not in the rectangle then reject the point, if it is then test against the semi-circle.

Also, outside of the loop, convert the values specifying the semi-circle into a form that will enable the tests to be done faster:

Convert the radius to radius squared. Compare the distance of a point from the center squared, to the radius squared. This saves a square root when computing the distance.
Convert the start and end angles of the semi-circle to a couple of 2D vectors, and then use these to check whether the point is inside the sector. Then you won't have to use any trig functions like atan2(y, x), which are slow, or do annoying fiddly comparisons to start and end angles and handling the case where angles wrap around from 360 to 0.

pseudo code:

 float radiusSquared;
 float startVectorX;
 float startVectorY;
 float endVectorX;
 float endVectorY;
 float centerX;
 float centerY;
 void convertSector(float radius, float startAngle, float endAngle)
 {
     radiusSquared = radius * radius;
     startVectorX = cos(startAngle);
     startVectorY = sin(startAngle);
     endVectorX = cos(endAngle);
     endVectorY = sin(endAngle);
 }

 boolean testPoint(float x, float y)
 {
     // check if point is within the radius:
     float distanceX = x - centerX;
     float distanceY = y - centerY;
     if((distanceX * distanceX) + (distanceY * distanceY)) > radiusSq)
         return false;

     // check if point is outside start radius vector using 2D dot-product with normal:
     if(((distanceX * -startVectorY) + (distanceY * startVectorX)) < 0.0f)
         return false;

     // check if point is outside end radius vector using 2D dot-product with normal:
     if(((distanceX * -endVectorY) + (distanceY * endVectorX)) > 0.0f)
         return false;

     return true;
 }

The above code will only work for sectors with an internal angle of <= 180 degrees. To test a point against sectors larger than that (i.e. Pac-Man like shapes), test if the point is inside the circle and then test that it is not inside the sector making up the remainder of the circle.

Algorithm to detect the point intersect the semi circle in android Java

1 Answers1