-1

I'm extremely new to Python and trying to figure out the most efficient way to randomly select a point within a polygon. The image I attached is representative of the scenario - my first attempt took nearly 30 seconds to generate a list of all pixel (x,y) coordinates contained in the gray area (I think I used matplotlib).

enter image description here

Based on other similar questions and suggestions I saw here, I am currently generating a rough bounding box of the polygon, setting min(x) and min(y) values based on the bounding box, and running a series of checks to see if I've landed in a valid area. Should I bother trying to generate a precise valid point list or is "dump and test" going to be faster?

John Kugelman
  • 349,597
  • 67
  • 533
  • 578
jivky
  • 3
  • 1
  • Your title says you want to randomly select points, but the text says *"generate a list of all pixel (x,y) coordinates contained in the white area"*. Do you want a random sample of points, or all points? Also, what is the input format? Is the polygon always a union of squares? – kaya3 Mar 13 '23 at 01:33
  • @kaya3 I want to randomly select a point within the valid (gray - my post has been edited) area. I don't know if it is faster to calculate all valid values and randomly select one, or just start picking randomly and test to see if I'm in the valid area. In my case, the polygon is always a union of squares and/or rectangles with interior voids. – jivky Mar 13 '23 at 01:41
  • Do you specifically want points with integer coordinates? Do you need a uniform distribution? – kaya3 Mar 13 '23 at 01:43
  • @kaya3, just integer coordinates. I only need to select one valid point. This polygon changes every time I select a point, so this is not a one-off process. – jivky Mar 13 '23 at 01:46
  • 1
    The simplest way is to just choose a random rectangle and then choose a random point in that rectangle. This will be biased towards points where the rectangles overlap, but maybe it is sufficient for your use-case? – kaya3 Mar 13 '23 at 01:47
  • @kaya3 It should be purely random, but in any case that approach doesn't solve the issue of the interior voids. If you generate a slew of random points in the void, it somewhat defeats the purpose of having done any calculation at all. But in the end, maybe all of this washes out when comparing approaches over thousands or millions of iterations. That's really the question. – jivky Mar 13 '23 at 01:53
  • The interior voids really just mean that each rectangle is four rectangles. By "purely random" do you mean "uniformly random"? – kaya3 Mar 13 '23 at 01:55
  • If you generated a complete list of valid points, how long would the list be? – Mark Ransom Mar 13 '23 at 02:34
  • @kaya3 that may be philosophically difficult to answer. The more uniform, the less random. but for my case, I think you can assume yes, what you mean by uniform randomness is what I'm after. – jivky Mar 13 '23 at 02:52
  • @MarkRansom for this example, the complete list would be roughly 100,000 coordinates. – jivky Mar 13 '23 at 02:53
  • It's not a philosophical question, and more uniform does not mean less random. A uniform distribution is one where all outcomes are equally likely. – kaya3 Mar 13 '23 at 02:55
  • The sample image you provided is about 33% gray. Will that be typical? If so you could expect about 1 of every 3 randomly chosen points to be in bounds. – Mark Ransom Mar 13 '23 at 04:02
  • @MarkRansom I think 25%-33% is pretty typical. It sounds promising, until you factor in the overhead of having performed the initial rough culling of data points outside the polygon bounding box, and then the validation check of your random point. I know there are many ways of doing polygon math in python, so its difficult to know if any are worth pursuing as a more computationally efficient option. – jivky Mar 13 '23 at 04:23

1 Answers1

0

You say that your typical polygon will have from 25% to 33% of the bounding box consisting of valid area. Worst case, if you select a random point within that bounding box, you have a 25% chance of it being good. Choose 4 points, and your odds go up to 68%. By the time you've tried 17, you're 99% likely to have found a good one.

Checking a point to see if it's within a polygon can be pretty efficient. See the question What's the fastest way of checking if a point is inside a polygon in python for some possibilities. A robust algorithm won't have any trouble dealing with polygons having holes as shown in your question. Since all the edges of your polygon are horizontal or vertical lines it might be possible to do even better, but it might not be worth it.

This will almost certainly be faster than generating the 100000 or so valid points within the polygon, just to choose one.

Mark Ransom
  • 299,747
  • 42
  • 398
  • 622
  • thank you! I think you're correct, as most of my other research ended up pointing me towards some kind of monte carlo-esque approach. – jivky Mar 14 '23 at 03:47