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

# Path finding algorithm

Go to solution Solved by flashang,

## Question 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: ```    def get_platform_information(self):
platforms = self.platforms.items()

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

platform_hashes = list(map(lambda x: x, 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 == hash_of_next_platform, sorted_platforms_with_y)))
next_platform_data = platform_above

# 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! 🤚

## 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.

🙂

• 1
##### 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, line2, line2) ||
isBetween(line2, line1, line1)
) {
return true;
}
return false;
}

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

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

console.log(result);```

• 1
##### 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.

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account. ×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.