# How to check whether a point is inside the black regions or not?

I have a huge map which is similar to bellow,

Problem:

I want to find feasible path between two points in the map. Since size of map is huge it takes enormous time to calculate the path. The knowledge I have is that black regions are defined by a set of polytopes.

Is there faster way to determine whether a given point is inside a black regions or not? I am asking this because path path planning algorithm takes time to decide given point is obstacle-free or not due size of map.

• Store the black regions in a quadtree so that you cut down on the number of black regions you need to test. Commented Mar 24, 2022 at 8:43
• @JaapScherphuis I will try and let you know thank youu Commented Mar 24, 2022 at 8:46
• All your black "dots" look pretty similar. You say they are generated as polytopes ; do you have any idea about the vectors generating them ? Commented Mar 24, 2022 at 9:54
• @JaapScherphuis I tried quadtree and KD-tree but still it takes huge time Commented Mar 24, 2022 at 11:42
• @JeanMarie I am not sure I understand you, polytope are generated as set of points which define the verticies Commented Mar 24, 2022 at 11:43