Hodgepodge

Introduction

Counting points inside and outside an irregular shapes is a problem. How can the counting process be automated to avoid tedious hand counting?

The algorithm below is a possible solution. (I make no pretense it is original.)

My Algorithm

Assumptions

the irregular shape can be described/defined by known
lines segments, curve segments, etc.

the irregular shape is inside an encompassing shape

the irregular shape's maximum and minimum points are known
and defining a "bounding box"

the "bound box" is a rectangle
(not required but calculations are easier)

the coordinates of the center of the encompassing shape are known
(being in the center is not actually required but the
calculations can be easier)

a line from any random point never crosses an encompassing shape edge
(not actually required but the calculations are easier)

the encompassing shape is a rectangle
(not required but is easier)

the center of the encompassing shape is known to be
inside or outside of the irregular shape
(the algorithm is for inside - modify as needed)

The algorithm (pseudo code)

# generate random points and count edge crossings inside_point_count = 0 # inside irregular shape total_point_count = 0 # inside encompassing shape max_point_count = (large number) ibbox = [edges of irregular shape's bounding box] ishape = [edges of irregular shape] eshape_center = [center of encompassing shape] loop: if total_point_count > max_point_count: break point = generate_random_point("in the encompassing shape") total_point_count += 1 if the random_point is outside ibbox: continue line = (line from random_point to eshape_center) crossing_count = (line crossings of the ishape edges) if the eshape_center is inside ishape: if crossing_count is an even number: # including zero inside_point_count += 1 else: if line crossing_count is an odd number: inside_point_count += 1