CODEWITHSUNDEEP
mathgrid2dgeometrypoints
JonaSc
JonaSc

Reputation: 315

Given a set of circles, how can I efficiently find the points only enclosed by one of them?

Given a set of centre points in a 2D-Grid and a common radius, I now want to mark all other points (or rather cells) inside of any of the circles formed by a centre point and the radius.

Finding all points inside one of the circles can be done by finding these points in one quarter and applying symmetry.

However, once some of the points have been marked, I now want to omit marking them again for the sake of efficiency. Therefore, all already "inflated" centre points within relevant distance of the next centre point to be drawn have already marked points which our also enclosed by the next circle. (That is, the magnitude of the vector from our point to each of them is smaller than the diameter).

How can I find the set of points within the next circle which have not been marked before?

The figure below shows an example of what I want to omit. Given three points, I draw a circle around each of them and mark each cell inside the circles with a colour in order blue, red, yellow. As you can see, large parts of the circles are overlapping, therefore some of the cells have been marked with each colour.

An example: Once coloured,

Upvotes: 1

Views: 219

Answers (1)

samgak
samgak

Reputation: 24417

For a given row in your grid, with a given Y value, you can write a function to calculate whether there are any points inside a circle on that row, and if so the starting and ending X co-ordinate of the interval where the row crosses the circle. In C++-like psuedo-code:

bool getRowCircleInterval(float fRowY, float fCenterX, float fCenterY, float fRadius, float &fStartX, float &fStartY)
{
     if((fRowY < fCenterY - fRadius) || (fRowY > fCenterY + fRadius))
         return false; // circle does not intersect this row

     float fYDiff = fCenterY - fRadius;
     float fIntervalWidth = sqrt((fRadius * fRadius) - (fYDiff * fYDiff));

     fStartX = fCenterX - fIntervalWidth;
     fEndX = fCenterX + fIntervalWidth;

     return true;
}

For each row in the range fCenterY - fRadius to fCenterY + fRadius for the circle you want to draw:

  • Call this function passing the newest circle to get an interval.
  • Repeatedly call the function again for each circle you have already drawn passing in the same row Y co-ordinate. If it returns true, intersect the returned interval with the existing interval and chop off that part of the existing interval that intersects. Repeat until either no interval is left or you have processed all the previous circles.
  • If the final interval remaining after processing all previous circles is non-empty, fill in all grid cells in the interval range for the row.

When converting the floating point X values to integer grid cell indices, you will need to use a consistent fill convention. For example you could divide by the grid cell with then convert to integer, and then fill in all points in the range of start X to end X inclusive. In that case, when you are checking two intervals for an overlap, if the new interval is being clipped by a previous interval, the new interval will be exclusive of the previous interval's endpoints.

Upvotes: 1

Related Questions