Check if two polygons overlap: Difference between revisions
Content added Content deleted
m (→{{header|Wren}}: Changed to Wren S/H) |
(Added Python implementation for the "Check if two polygons overlap" task) |
||
Line 649: | Line 649: | ||
poly2 and poly3 overlap? true |
poly2 and poly3 overlap? true |
||
</pre> |
</pre> |
||
=={{header|Python}}== |
|||
{{trans|Nim}} |
|||
<syntaxhighlight lang="python3"> |
|||
# overlapping polygons by xing216 |
|||
from math import inf |
|||
class Vector2: |
|||
def __init__(self, x: float, y: float) -> None: |
|||
self.x = x |
|||
self.y = y |
|||
def dot(self, other: 'Vector2') -> float: |
|||
return self.x * other.x + self.y * other.y |
|||
def __repr__(self) -> str: |
|||
return f'({self.x}, {self.y})' |
|||
class Projection: |
|||
min: float |
|||
max: float |
|||
def overlaps(self, proj2: 'Projection') -> bool: |
|||
if self.max < proj2.min or proj2.max < self.min: return False |
|||
return True |
|||
class Polygon: |
|||
def __init__(self, vertices: list[Vector2]) -> None: |
|||
self.vertices = vertices |
|||
self.axes = self.get_axes() |
|||
def get_axes(self) -> list[Vector2]: |
|||
axes = [] |
|||
for i, vertex1 in enumerate(self.vertices): |
|||
if i + 1 == len(self.vertices): vertex2 = self.vertices[0] |
|||
else: self.vertices[i + 1] |
|||
edge = (vertex1.x - vertex2.x, vertex1.y - vertex2.y) |
|||
axes.append(Vector2(-edge[1], edge[0])) |
|||
return axes |
|||
def projection_on_axis(self, axis: Vector2) -> Projection: |
|||
projection = Projection() |
|||
projection.min = inf |
|||
projection.max = -inf |
|||
for vertex in self.vertices: |
|||
p = axis.dot(vertex) |
|||
if p < projection.min: |
|||
projection.min = p |
|||
if p > projection.max: |
|||
projection.max = p |
|||
return projection |
|||
def overlaps(self, other: 'Polygon') -> bool: |
|||
for axes in [self.axes, other.axes]: |
|||
for axis in axes: |
|||
proj1 = self.projection_on_axis(axis) |
|||
proj2 = other.projection_on_axis(axis) |
|||
if not proj1.overlaps(proj2): return False |
|||
return True |
|||
poly1 = [(0.0, 0.0), (0.0, 2.0), (1.0, 4.0), (2.0, 2.0), (2.0, 0.0)] |
|||
poly2 = [(4.0, 0.0), (4.0, 2.0), (5.0, 4.0), (6.0, 2.0), (6.0, 0.0)] |
|||
poly3 = [(1.0, 0.0), (1.0, 2.0), (5.0, 4.0), (9.0, 2.0), (9.0, 0.0)] |
|||
polygons = (poly1, poly2, poly3) |
|||
polygons = [Polygon([Vector2(*vertex) for vertex in polygon]) for polygon in polygons] |
|||
for i, polygon in enumerate(polygons): |
|||
print(f'poly{i+1} = {polygon.vertices}') |
|||
print(f'poly1 and poly2 overlap? {polygons[0].overlaps(polygons[1])}') |
|||
print(f'poly1 and poly3 overlap? {polygons[0].overlaps(polygons[2])}') |
|||
print(f'poly2 and poly3 overlap? {polygons[1].overlaps(polygons[2])}') |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
poly1 = [(0.0, 0.0), (0.0, 2.0), (1.0, 4.0), (2.0, 2.0), (2.0, 0.0)] |
|||
poly2 = [(4.0, 0.0), (4.0, 2.0), (5.0, 4.0), (6.0, 2.0), (6.0, 0.0)] |
|||
poly3 = [(1.0, 0.0), (1.0, 2.0), (5.0, 4.0), (9.0, 2.0), (9.0, 0.0)] |
|||
poly1 and poly2 overlap? False |
|||
poly1 and poly3 overlap? True |
|||
poly2 and poly3 overlap? True |
|||
</pre> |
|||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
{{trans|Go}} |
{{trans|Go}} |