Jump to content
Welcome, welcome! Come in and register, and have some developer coffee. 👨‍💻 ×
  • 0

Path finding algorithm


Go to solution Solved by flashang,

Question

image.png

Hey GG kakis,

I need help on checking if a line/platform is directly above another line/platform. The left number on the left represent the start of a platform, X1 and the number at the end is the X2 cood of the platform.

 

How do I:

1) Check if X(39, 77) is above X(36, 73).

2) X(83. 121) isAbove X(36, 73) returns false although it is above the platform. To fit the condition, it must be horizontally overlapped with the above platform.

 

Here are some of the possible combinations of platforms:

image.png

 

    def get_platform_information(self):
        platforms = self.platforms.items()

        sorted_platforms_with_y = sorted(platforms, key=lambda k: k[1].end_y, reverse=True)  # sort list with y, descendingly

        platform_hashes = list(map(lambda x: x[0], sorted_platforms_with_y)) #Each platform is identified with a hash
                
        # Find and assign top platform for each individual platform
        for index, hash in enumerate(platform_hashes):
            current_platform_data = self.platforms[hash]
            current_platform_data.information = []

            # Storing possible top platform
            # Since it is sorted descendingly, we first assume the next element in the list is the one above it
            platform_above = None
            hash_of_next_platform = None
            
            for innerIndex, innerHash in enumerate(platform_hashes):
              # Skip self
                if innerHash != hash:
                  #If platform is not the topmost
                  if index != len(platform_hashes) - 1:
                        hash_of_next_platform = platform_hashes[innerIndex + 1]
                      	
                        if hash_of_next_platform and hash != hash_of_next_platform and innerIndex > index:
                          # Extracting next platform data
                          platform_above = (list(filter(lambda x: x[0] == hash_of_next_platform, sorted_platforms_with_y)))[0]
                          next_platform_data = platform_above[1]
                          
                          # Stuck here
                          if (
                                (current_platform_data.end_x <= next_platform_data.end_x
                                 and next_platform_data.start_x >= current_platform_data.start_x) and
                                (next_platform_data.end_x - current_platform_data.end_x > 0)
                            
                                or

                                (current_platform_data.start >= next_platform_data.start_x
                                 and next_platform_data.end_x <= current_platform_data.end_x)
                                or
                                (current_platform_data.start_x >= next_platform_data.start_x) and \
                                (current_platform_data.end_x <= next_platform_data.end_x)

                                or
                                (next_platform_data.start_x >= current_platform_data.start_x) and \
                                (next_platform_data.end_x <= current_platform_data.end_x)
                          )
                          	hash_of_next_platform = innerHash
                            break
                          # This check will grab platforms that are not horizontally overlapped with it
                          
                          else:
                        	hash_of_next_platform = None

 

Appreciate some light. Thanks! 🤚

 

Link to post
Share on other sites

3 answers to this question

Recommended Posts

  • 1
  • Solution

Try to do a simple compare.

 


dataList = [ {"x1":36, "x2":73}, {"x1":83, "x2":121}, 
    {"x1":39, "x2":77}, {"x1":87, "x2":125}, 
    {"x1":59, "x2":96} ]


def overlap( item, arr ):
    for x in arr :
        if item == x:
            continue # assume there is no duplicate in arr

        #1 a.x1 <= b.x1 <= a.x2
        if item['x1'] <= x['x1'] and x['x1'] <= item['x2'] :
            print( item, ' is overlap with ', x , ' case 1' )

        #1 a.x1 <= b.x2 <= a.x2
        if item['x1'] <= x['x2'] and x['x2'] <= item['x2'] :
            print( item, ' is overlap with ', x , ' case 2' )

        #3 b.x1 <= a.x1 <= b.x2
        if x['x1'] <= item['x1'] and item['x1'] <= x['x2'] :
            print( item, ' is overlap with ', x , ' case 3' )

        #4 b.x1 <= a.x2 <= b.x2
        if x['x1'] <= item['x2'] and item['x2'] <= x['x2'] :
            print( item, ' is overlap with ', x , ' case 4' )


for i in dataList :
    print( 'check ', i )
    overlap( i, dataList )

print( '' )
print( 'dataList : ', dataList )

 

result :

check  {'x1': 36, 'x2': 73}
{'x1': 36, 'x2': 73}  is overlap with  {'x1': 39, 'x2': 77}  case 1
{'x1': 36, 'x2': 73}  is overlap with  {'x1': 39, 'x2': 77}  case 4
{'x1': 36, 'x2': 73}  is overlap with  {'x1': 59, 'x2': 96}  case 1
{'x1': 36, 'x2': 73}  is overlap with  {'x1': 59, 'x2': 96}  case 4
check  {'x1': 83, 'x2': 121}
{'x1': 83, 'x2': 121}  is overlap with  {'x1': 87, 'x2': 125}  case 1
{'x1': 83, 'x2': 121}  is overlap with  {'x1': 87, 'x2': 125}  case 4
{'x1': 83, 'x2': 121}  is overlap with  {'x1': 59, 'x2': 96}  case 2
{'x1': 83, 'x2': 121}  is overlap with  {'x1': 59, 'x2': 96}  case 3
check  {'x1': 39, 'x2': 77}
{'x1': 39, 'x2': 77}  is overlap with  {'x1': 36, 'x2': 73}  case 2
{'x1': 39, 'x2': 77}  is overlap with  {'x1': 36, 'x2': 73}  case 3
{'x1': 39, 'x2': 77}  is overlap with  {'x1': 59, 'x2': 96}  case 1
{'x1': 39, 'x2': 77}  is overlap with  {'x1': 59, 'x2': 96}  case 4
check  {'x1': 87, 'x2': 125}
{'x1': 87, 'x2': 125}  is overlap with  {'x1': 83, 'x2': 121}  case 2
{'x1': 87, 'x2': 125}  is overlap with  {'x1': 83, 'x2': 121}  case 3
{'x1': 87, 'x2': 125}  is overlap with  {'x1': 59, 'x2': 96}  case 2
{'x1': 87, 'x2': 125}  is overlap with  {'x1': 59, 'x2': 96}  case 3
check  {'x1': 59, 'x2': 96}
{'x1': 59, 'x2': 96}  is overlap with  {'x1': 36, 'x2': 73}  case 2
{'x1': 59, 'x2': 96}  is overlap with  {'x1': 36, 'x2': 73}  case 3
{'x1': 59, 'x2': 96}  is overlap with  {'x1': 83, 'x2': 121}  case 1
{'x1': 59, 'x2': 96}  is overlap with  {'x1': 83, 'x2': 121}  case 4
{'x1': 59, 'x2': 96}  is overlap with  {'x1': 39, 'x2': 77}  case 2
{'x1': 59, 'x2': 96}  is overlap with  {'x1': 39, 'x2': 77}  case 3
{'x1': 59, 'x2': 96}  is overlap with  {'x1': 87, 'x2': 125}  case 1
{'x1': 59, 'x2': 96}  is overlap with  {'x1': 87, 'x2': 125}  case 4

dataList :  [{'x1': 36, 'x2': 73}, {'x1': 83, 'x2': 121}, {'x1': 39, 'x2': 77},
{'x1': 87, 'x2': 125}, {'x1': 59, 'x2': 96}]

you may use "break" in every if to skip the other compare.

🙂

 

  • Love 1
Link to post
Share on other sites
  • 0

Hey you can try something like this. This is in JavaScript though but it's quite straight forward to be ported over to Python:

const sampleData = [
	[[3, 6], [1, 5]],
  [[1, 3], [2,7]],
  [[3, 5], [1,8]],
  [[1, 8], [3,5]],
];


let isBetween = (number, min, max) => {
  return number >= min && number <= max;
}

let isOverlap = (line1 , line2) => {
  if (
  	isBetween(line1[0], line2[0], line2[1]) ||
    isBetween(line2[0], line1[0], line1[1])
   ) {
   	return true;
   }
   return false;
}


const result = [];
sampleData.forEach((linePair) => {
  const line1 = linePair[0];
  const line2 = linePair[1];

  result.push(
    {
      linePair,
      isOverlap: isOverlap(line1, line2)
    }
  );
});

console.log(result);

 

  • Like 1
Link to post
Share on other sites
  • 0
On 4/12/2021 at 9:42 PM, flashang said:

Try to do a simple compare.

 


dataList = [ {"x1":36, "x2":73}, {"x1":83, "x2":121}, 
    {"x1":39, "x2":77}, {"x1":87, "x2":125}, 
    {"x1":59, "x2":96} ]


def overlap( item, arr ):
    for x in arr :
        if item == x:
            continue # assume there is no duplicate in arr

        #1 a.x1 <= b.x1 <= a.x2
        if item['x1'] <= x['x1'] and x['x1'] <= item['x2'] :
            print( item, ' is overlap with ', x , ' case 1' )

        #1 a.x1 <= b.x2 <= a.x2
        if item['x1'] <= x['x2'] and x['x2'] <= item['x2'] :
            print( item, ' is overlap with ', x , ' case 2' )

        #3 b.x1 <= a.x1 <= b.x2
        if x['x1'] <= item['x1'] and item['x1'] <= x['x2'] :
            print( item, ' is overlap with ', x , ' case 3' )

        #4 b.x1 <= a.x2 <= b.x2
        if x['x1'] <= item['x2'] and item['x2'] <= x['x2'] :
            print( item, ' is overlap with ', x , ' case 4' )


for i in dataList :
    print( 'check ', i )
    overlap( i, dataList )

print( '' )
print( 'dataList : ', dataList )

 

result :

check  {'x1': 36, 'x2': 73}
{'x1': 36, 'x2': 73}  is overlap with  {'x1': 39, 'x2': 77}  case 1
{'x1': 36, 'x2': 73}  is overlap with  {'x1': 39, 'x2': 77}  case 4
{'x1': 36, 'x2': 73}  is overlap with  {'x1': 59, 'x2': 96}  case 1
{'x1': 36, 'x2': 73}  is overlap with  {'x1': 59, 'x2': 96}  case 4
check  {'x1': 83, 'x2': 121}
{'x1': 83, 'x2': 121}  is overlap with  {'x1': 87, 'x2': 125}  case 1
{'x1': 83, 'x2': 121}  is overlap with  {'x1': 87, 'x2': 125}  case 4
{'x1': 83, 'x2': 121}  is overlap with  {'x1': 59, 'x2': 96}  case 2
{'x1': 83, 'x2': 121}  is overlap with  {'x1': 59, 'x2': 96}  case 3
check  {'x1': 39, 'x2': 77}
{'x1': 39, 'x2': 77}  is overlap with  {'x1': 36, 'x2': 73}  case 2
{'x1': 39, 'x2': 77}  is overlap with  {'x1': 36, 'x2': 73}  case 3
{'x1': 39, 'x2': 77}  is overlap with  {'x1': 59, 'x2': 96}  case 1
{'x1': 39, 'x2': 77}  is overlap with  {'x1': 59, 'x2': 96}  case 4
check  {'x1': 87, 'x2': 125}
{'x1': 87, 'x2': 125}  is overlap with  {'x1': 83, 'x2': 121}  case 2
{'x1': 87, 'x2': 125}  is overlap with  {'x1': 83, 'x2': 121}  case 3
{'x1': 87, 'x2': 125}  is overlap with  {'x1': 59, 'x2': 96}  case 2
{'x1': 87, 'x2': 125}  is overlap with  {'x1': 59, 'x2': 96}  case 3
check  {'x1': 59, 'x2': 96}
{'x1': 59, 'x2': 96}  is overlap with  {'x1': 36, 'x2': 73}  case 2
{'x1': 59, 'x2': 96}  is overlap with  {'x1': 36, 'x2': 73}  case 3
{'x1': 59, 'x2': 96}  is overlap with  {'x1': 83, 'x2': 121}  case 1
{'x1': 59, 'x2': 96}  is overlap with  {'x1': 83, 'x2': 121}  case 4
{'x1': 59, 'x2': 96}  is overlap with  {'x1': 39, 'x2': 77}  case 2
{'x1': 59, 'x2': 96}  is overlap with  {'x1': 39, 'x2': 77}  case 3
{'x1': 59, 'x2': 96}  is overlap with  {'x1': 87, 'x2': 125}  case 1
{'x1': 59, 'x2': 96}  is overlap with  {'x1': 87, 'x2': 125}  case 4

dataList :  [{'x1': 36, 'x2': 73}, {'x1': 83, 'x2': 121}, {'x1': 39, 'x2': 77},
{'x1': 87, 'x2': 125}, {'x1': 59, 'x2': 96}]

you may use "break" in every if to skip the other compare.

🙂

 

Thanks Flash, going to mark this as answer as the previous answer is in JavaScript. 

Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...