Check if two polygons overlap: Difference between revisions

=={{header|jq}}==

'''Adapted from [[#Wren]]'''

{{works with|jq}}

'''Also works with gojq, the Go implementation of jq'''

In the following:

* a vertex is represented by a pair of x, y coordinates in the plane;

* a polygon is represented as a list of vertices;

* a projection is represented by a JSON object {min, max}

<syntaxhighlight lang="jq">

# Input: a vector

# Output: perpendicular

def perp: [- .[1], .[0]];

# dot product of this and $v, assumed to be of the same dimension

def dot($v):

. as $this

| reduce range(0; $this|length) as $i (0; . + ($this[$i] * $v[$i] ));

def getAxes:

. as $poly

| reduce range(0; $poly|length) as $i ([];

$poly[$i] as $vertex1

| $poly[if $i+1 == ($poly|length) then 0 else $i+1 end] as $vertex2

| [$vertex1[0] - $vertex2[0], $vertex1[1] - $vertex2[1]] as $edge

| . + [$edge | perp]);

# emit {min, max}

def projectOntoAxis($axis):

. as $poly

| { max: - infinite, min: infinite }

| reduce range(0; $poly|length) as $i (.;

($axis | dot( $poly[$i] )) as $p

| if $p < .min then .min = $p else . end

| if $p > .max then .max = $p else . end ) ;

def projectionsOverlap($proj1; $proj2):

if $proj1.max < $proj2.min then false

elif $proj2.max < $proj1.min then false

else true

end;

def polygonsOverlap($poly1; $poly2):

first ( (($poly1, $poly2) | getAxes[]) as $axis

| ($poly1 | projectOntoAxis($axis)) as $proj1

| ($poly2 | projectOntoAxis($axis)) as $proj2

| if (projectionsOverlap($proj1; $proj2) | not) then 0 else empty end)

// 1

| . == 1;

def poly1: [[0, 0], [0, 2], [1, 4], [2, 2], [2, 0]];

def poly2: [[4, 0], [4, 2], [5, 4], [6, 2], [6, 0]];

def poly3: [[1, 0], [1, 2], [5, 4], [9, 2], [9, 0]];

def task:

"poly1 = \(poly1)",

"poly2 = \(poly2)",

"poly3 = \(poly3)",

"",

"poly1 and poly2 overlap? \(polygonsOverlap(poly1; poly2))",

"poly1 and poly3 overlap? \(polygonsOverlap(poly1; poly3))",

"poly2 and poly3 overlap? \(polygonsOverlap(poly2; poly3))"

;

task

</syntaxhighlight>

{{output}}

As for [[#Wren]]