Return to Question

Imagine I have an arbitrary concave polygon. I need to find/generate a point inside of it, efficiently.

RandomPoint@Polygon@points is relatively fast only for simple such polygons.

n=1;(* toy polygon complexity *) points=Join[Transpose[{Range[2*n+1]*5,Drop[Flatten@ConstantArray[{0,45},n+1],-1]}],Transpose[{Reverse@Range[2*n+1]*5-5,Drop[Flatten@ConstantArray[{55,10},n+1],-1]}]]; insidepoint=RandomPoint@Polygon@points;//RepeatedTiming Show[ Graphics@Thread@Line@Transpose[{points,RotateLeft@points}], Graphics@{Red,PointSize[Medium],Point@insidepoint} ] 

n=1

n=100

{0.233274, Null}

n=1000

{2.84268, Null}

So, for complex polygons,RandomPoint@Polygon is very, very slow.

Is there a method to find a point inside a convex polygon efficiently, no matter the complexity?

Imagine I have an arbitrary concave polygon. I need to find/generate a point inside of it, efficiently.

RandomPoint@Polygon@points is relatively fast only for simple such polygons.

n=1;(* toy polygon complexity *) points=Join[Transpose[{Range[2*n+1]*5,Drop[Flatten@ConstantArray[{0,45},n+1],-1]}],Transpose[{Reverse@Range[2*n+1]*5-5,Drop[Flatten@ConstantArray[{55,10},n+1],-1]}]]; insidepoint=RandomPoint@Polygon@points;//RepeatedTiming Show[ Graphics@Thread@Line@Transpose[{points,RotateLeft@points}], Graphics@{Red,PointSize[Medium],Point@insidepoint} ] 

n=1

n=100

{0.233274, Null}

n=1000

{2.84268, Null}

So, for complex polygons,RandomPoint@Polygon is very, very slow.

Is there a method to find a point inside a convex polygon efficiently, no matter the complexity?

UPD.

timings

Imagine I have an arbitrary concave polygon. I need to find/generate a point inside of it, efficiently.

RandomPoint@Polygon@points is relatively fast only for simple such polygons.

n=1;(* toy polygon complexity *) points=Join[Transpose[{Range[2*n+1]*5,Drop[Flatten@ConstantArray[{0,45},n+1],-1]}],Transpose[{Reverse@Range[2*n+1]*5-5,Drop[Flatten@ConstantArray[{55,10},n+1],-1]}]]; insidepoint=RandomPoint@Polygon@points;//RepeatedTiming Show[ Graphics@Thread@Line@Transpose[{points,RotateLeft@points}], Graphics@{Red,PointSize[Medium],Point@insidepoint} ] 

n=1

n=100

{0.233274, Null}

n=1000

{2.84268, Null}

So, for complex polygons,RandomPoint@Polygon is very, very slow.

Is there a method to find a point inside a convex polygon efficiently, no matter the complexity?

Imagine I have an arbitrary concave polygon. I need to find/generate a point inside of it, efficiently.

RandomPoint@Polygon@points is relatively fast only for simple such polygons.

n=1;(* toy polygon complexity *) points=Join[Transpose[{Range[2*n+1]*5,Drop[Flatten@ConstantArray[{0,45},n+1],-1]}],Transpose[{Reverse@Range[2*n+1]*5-5,Drop[Flatten@ConstantArray[{55,10},n+1],-1]}]]; insidepoint=RandomPoint@Polygon@points;//RepeatedTiming Show[ Graphics@Thread@Line@Transpose[{points,RotateLeft@points}], Graphics@{Red,PointSize[Medium],Point@insidepoint} ] 

n=1

n=100

{0.233274, Null}

n=1000

{2.84268, Null}

So, for complex polygons,RandomPoint@Polygon is very, very slow.

Is there a method to find a point inside a convex polygon efficiently, no matter the complexity?