10

Is there any solution to calculate with a QGIS expression the largest empty circle of a point layer as shown in the image below?

Maybe there is some solution combining or improving the functions pole of inaccessibility, convex hull in this way:

pole_of_inaccessibility(convex_hull(collect($geometry, 9999)), 9999)

I have tried this solution but the pole of inaccessibility concept is not the same as the largest empty circle concept.

enter image description here

Clarifications and possible solution:

A proposed solution would be the following:

Consider that the features extent would be defined by the detection of the most isolated points. This calculation can be done by reusing the following function that appears in one of the answers in the post Creating the minimum convex hull that contains certain percentage of points in QGIS:

array_sum ( array_foreach ( overlay_nearest( @layer, $geometry, limit:=2 ), length ( make_line ( $geometry, @element ) ) ) )

enter image description here

The next step would be to find the Minimum Delimiting Geometry with circle geometry formed by the most isolated point. This can be represented using Geometry Generator and the following function:

case when "DISTA" > mean("DISTA") then minimal_circle( collect_geometries ( overlay_nearest ( 'PG', $geometry, limit:=2 ) ) ) else $geometry end

enter image description here

Finally, we would have to manually eliminate the cases that do not correspond to the desired objective.

I think it is an unelegant solution and I am still not convinced by the fact that the last step is manual.

Could someone provide an improvement to this view or, perhaps, a new approach?

Vince
  • 20,017
  • 15
  • 45
  • 64
Acperience
  • 1,112
  • 1
  • 10
  • 11
    How do you define which circle is still "within" the point layer and which one is outside? I could define you an enormous circle from two points at the outer rim and say "the circles center is about 2000 miles away". – Erik Dec 20 '22 at 12:50
  • I really don't know what to answer to this question. Sorry. The idea to get a large empty circle of point as a concept is to detect and visualize the largest free space or area without occurrences – Acperience Dec 20 '22 at 13:25
  • 6
    The largest free space is by definition outside the extent of your features, hence you would need to put some thought into it. I have two ideas how to get something you might want to achieve, but that depends on your definition of "within". – Erik Dec 20 '22 at 13:33
  • Thank you very much. I understand what you mean. Then I try to describe the problem and the definition of "within": For this case, as a definition of "within", it would be the representation of the circle with the maximum possible radius that can be constructed in the free space, with the condition that the features are outside of it. Hope this definition could help to become clearer and more focused to resolve the problem. – Acperience Dec 20 '22 at 13:48
  • 2
    Still unclear. To ask @Erik's question in a different way: what is the maximum extent of the circle of "free space"? What is the outer limit for the circle? Let's imagine the points cover the area inside a city (say: New York). A possible solution would be a circle reching from London to the northeasternmost point in YNC. However, this is probably not what you're looking for. You're looking for a circle that stay inside the extent of the point layer? – Babel Dec 20 '22 at 14:58
  • I understand the question and understand the need to isolate this geometric unknown to find a solution. Perhaps it is necessary, in a first step, to take into consideration the layer extent of point features to find the most distant point among all, and then create a new layer from the buffer having as limit (radius) the distance to the nearest point. I am not very sure about this procedure. I just tried to find a logic to solve the question. On the other hand, now I understand that maybe it can not be solved with a single expression, and it is necessary to do some intermediate geoprocessings. – Acperience Dec 20 '22 at 18:03
  • As others have mentioned you need to define within. A solution might be...Rasterize your points, generate a proximity raster. That proximity raster value with the greatest value is the center of a circle with a radius equal to the value? – GBG Dec 20 '22 at 19:21
  • Please use the [edit] button beneath your question to revise it with any requested clarifications. – PolyGeo Dec 20 '22 at 19:23
  • 1
    The question I believe is really what is your actual goal and constraint in terms of 'within'? Your circle must have a purpose and meaning, therefore some constraints. In my answer below, if you add some Buffer to the Voronoi step this will extend it beyond the Point bounding box. You could then clip it with any other polygon you want provided that you have a defined constraint. – Kasper Dec 20 '22 at 19:47
  • 1
    Maybe this helps? https://gis.stackexchange.com/a/419850/88814 – Babel Dec 20 '22 at 20:24

1 Answers1

9

What you can do is the following:

  1. create Voronoi polygons from your 'points' (will provide equal distance lines from points) - Processing Toolbox/Voronoi
  2. create a convex hull from your points (will allow to bound the circle centers within your point layer in the following step) - Processing Toolbox/Minimum Bounding Geometry/Convex Hull
  3. clip 1 with 2 (clipped Voronoi layer) - Processing Toolbox/Clip
  4. extract vertices from 3 to get all potential circle centers (this is a point layer called 'Vertices' in my example) - Processing Toolbox/Extract vertices

With these steps, we now have all the potential circle centers, bound to the point convex hull. You might skip step 2 and 3 if your circle centers are allowed to go up to the extents of the points bounding box. If you have another formal definition of where you want to limit your cirles to, you might need to adapt this first part

Then you can style this 'Vertices' layer with a Geometry generator of type Polygon, with the following rule that will find the largest possible circle:

case when 
maximum(distance(geometry($currentfeature),collect_geometries(
         array_foreach(generate_series(1,12, 1),geometry(get_feature_by_id('points',@element)))))) = distance(geometry(
        $currentfeature),collect_geometries(
         array_foreach(generate_series(1,12, 1),geometry(get_feature_by_id('points',@element)))))

       then 

    make_circle($geometry,distance($geometry,collect_geometries(
     array_foreach( generate_series(1,12, 1), geometry(get_feature_by_id('points',@element))))))

    end

The case when checks if the circle radius from the current target center is equal to the maximum radius (largest circle)

after the then this generates the circle: centered on the target center, with a radius equal to the (minimum) distance between this center and all the original points

The one hard coded part in my example is 12 which is the number of points in the original layer.

You can replace 12 by aggregate(layer:='points',aggregate:='count',expression:='id') which will dynamically return the number of geometries in the points layer

enter image description here

Same process with another point layout: enter image description here

Kasper
  • 3,192
  • 1
  • 2
  • 19