0
$\begingroup$

I have a huge map which is similar to bellow, enter image description here

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.

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

0

Reset to default

You must log in to answer this question.