About contain judgment between polygons

[naomei]

I have prepared two code sandboxes.
Both are tests with two similar polygons.
(Displaying with canvas debugging and outputting the result to the console)

test1
https://codesandbox.io/s/detect-collisions-test1-87iruj

test2
https://codesandbox.io/s/detect-collisions-test2-6ll0zd

We would expect similar results for either aInB or BinA , but they are not.

I think test2 seems to be the correct result,
test1 seems to be an unexpected result.

what is this happening?

[Prozi]

@naomei thank you for opening an issue

thing is, the inner broken line is represented as it is drawn
it is not purely a broken line inside a polygon

see https://www.splashlearn.com/math-vocabulary/wp-content/uploads/2022/08/Regular-Polygon-1.png

also. what is the difference in code between test1 and test2? i dont see it at first glance

[naomei]

@Prozi

Thank you for all your prompt answers.
I may have made a big mistake in your solution.

Do you mean that the points array given to the createPolygon function "must be closed to be a polygon"?

When using canvas debugging, "even an unclosed polygon will be drawn closed", so I thought "if you give it an unclosed polygon, it is treated internally as a closed polygon".

Is this correct?

[naomei]

@Prozi

I made another sample.
This time the polygons are completely closed data.

https://codesandbox.io/s/detect-collisions-test3-581stx

There are lines within the complete polygon.
What is happening that makes this code result in false instead of true? 🤔

if (system.checkCollision(line, area)) {
  console.log(system.response.aInB);
}

[Prozi]

@naomei this is indeed strange. i will debug this case in upcoming days.

thank you

[Prozi]

(missclicked close so I reopened as this is an open issue)

[Prozi]

@naomei please see https://codesandbox.io/s/detect-collisions-test3-forked-ieps9z?file=/src/App.tsx

when I apply rounding to points of polygon, the result is as it should be

this seems related to #45 as the solution there is the same (see #45 (comment))

I will investigate further in the upcoming days

[Prozi]

Ok the aInB and bInA are not perfectly calculated for concave (non convex) polygons

http://www.sunshine2k.de/coding/java/Polygon/Convex/convexpoly.gif

I will think about fixing this issue

[naomei]

@Prozi

when I apply rounding to points of polygon, the result is as it should be

Thank you very much.
I got the right result.

May I ask one more question?
In the case of the polygon below, I believe it would be treated as an illegal polygon.

But what is the solution if I want to treat this decision correctly?

In my project, I have the ability to click on the screen to create a polygon, which I need to compare to the polygon.
Because of the click to create polygons, there are inevitably cases where crossed and incorrect polygons are created, such as the one above.

Very much appreciate your help so far!

[Prozi]

dear @naomei the main issue

(approximation of aInB and bInA)

has been hopefully fixed/featured correctly since v6.8.0

please see https://codesandbox.io/s/detect-collisions-test3-forked-gxfjzp?file=/package.json

[Prozi]

about the other issue please try to do a sandbox using v6.8.0 thank you

[Prozi]

replying to your second case with triangles

don't worry about polygon being concave or convex, with this library, we are dissecting non-convex polygons into convex ones, and performing checks for that

the only issue is that aInB and bInA were approximated very roughly because of lack of math and my time to write it

also AFAIR the concave polygons came after 3.4.0 version so they were kind of added from scratch (no support for them in sat.js - the muscle of this library)

in the worst case scenario I guess you could use RayCasting https://prozi.github.io/detect-collisions/classes/System.html#raycast but the goal here is to make this work without any hacks on your side. this way the open-source community will be able to take advantage of it (the code will be free to more people)

[Prozi]

seems to work https://codesandbox.io/s/detect-collisions-test3-forked-26nijj?file=/src/App.tsx

[naomei]

@Prozi

has been hopefully fixed/featured correctly since v6.8.0

Thank you very much.
We have confirmed that it is working fine.

Also, thanks for the answer to my other question.
I will try to come up with a solution using raycast.

This isssue is resolved and will be close 🙏

[naomei]

@Prozi

I came up with my own method of judging using raycasting.
Please advise me if you have a better method.

First, before using raycasting determine that the boxes overlap each other by comparing the size and position of the bboxes.

Then, I thought of the following way to use raycast.

The problem with this is that depending on the state of the polygons, raycasting from the four corners alone may not be sufficient... 🤔
(Fly a ray from 4 points at the corners as well as from 8 points with an additional midpoint?)

I couldn't think of a better way than this, what do you think?

[naomei]

However, in the case of this shape, the above method proved impossible.
It creates a blind spot and the ray cannot reach it.
(Very difficult...)

[Prozi]

if you would provide me the arrays of points used for those polygons it will make it easier to debug thank you

also, what you're looking for is, if I understand correctly, checking if that circle collides with polygon, did I understood that right?

[Prozi]

about the raycasting I dont understand why this is required

but I would recommend maybe scanlines - horizontal raycasts on the Y of each of polygons points I guess

[naomei]

@Prozi

also, what you're looking for is, if I understand correctly, checking if that circle collides with polygon, did I understood that right?

No, it's not just a combination of circles and polygons.
In my project, in addition to the polygons described here, I need to determine whether they are circles, rectangles, or lines.

if you would provide me the arrays of points used for those polygons it will make it easier to debug thank you

#48 (comment)

For example, the points of the polygon above are:

[
  { x: 68, y: 0 },
  { x: 0, y: 168 },
  { x: 214, y: 151 },
  { x: 130, y: 260 },
  { x: 68, y: 0 },
];

And first, I want to achieve "perfect contain judgment" for this polygon and a simple circle.
As you explained, I don't think I can make a perfect judgment right now.

about the raycasting I dont understand why this is required
but I would recommend maybe scanlines - horizontal raycasts on the Y of each of polygons points I guess

Sorry, maybe I don't fully understand raycasting.
How can I use raycast to solve this?

[Prozi]

oh now I understand your problem

https://stackblitz.com/edit/detect-collisions?file=src%2FApp.js

in the case you describe the checkCollision/checkAInB returns false hayaa

Ok I will try to investigate what to do with such case

for the raycasting I was thinking of

const polygons = []
const polygon = system.createPolygon({}, points);
polygons.push(polygon); // and more
polygons.forEach(polygon => {
  polygon.calcPoints.forEach(point => {
    const hit = system.raycast(point, { ...point, x: point - 100 })
    if (hit && hit.body.type === BodyType.Circle) {
      // OH NOW I SEE THE PROBLEM AGAIN :)
    }
  })
})

[naomei]

@Prozi
Thank you for reply.

Tried another approach and it all seems to work fine.
(Performance is not very good and may have issues)

I tried a color difference comparison using getImageData.
A and B are filled when judging

1. B-only ImageData
2. ImageData when drawing A and B

Compare these.
If A is completely contained in B, there should be no difference.

// Fast comparison using for
function arraysEqual(arr1: any[], arr2: any[]) {
  if (arr1.length !== arr2.length) return false;
  for (let i = arr1.length; i--; ) {
    if (arr1[i] !== arr2[i]) return false;
  }
  
  return true;
}

// draw
context.beginPath();
bBody.draw(context);
context.fillStyle = "black";
context.fill();

// ImageData for B only
const BData = context.getImageData(0, 0, canvasSize, canvasSize);

context.beginPath();
aBody.draw(context);
context.fill();

// ImageData for A+B
const ABData = context.getImageData(0, 0, canvasSize, canvasSize);

// compare
console.log(arraysEqual(BData.data, ABData.data));

I know it's not the correct implementation...