Faces

[Pilchard123]

That looks funny. It should have told you P was above BC, if you are using the example picture above...

EDIT: ...on the previous page.

EDIT2: And it should be bwlow CA. Workin on't.

[Pilchard123]

You must have gone wrong somewhere. I've just done it on paper and got the following results:

P is above AB (correct from picture)
P is above BC (also correct from picture)
P is below CA (also correct from picture)

Did you do those on paper or in code? If you did them in code, I'll have a look if you post it or PM me just the code to check the point's position.

[annikk.exe]

Ah maybe I got it wrong, I just did it by eye.

The point is, you can know whether P is above or below all the lines...  but that does not intrinsically tell you whether P is inside or outside the triangle.  How to do that last step?

[Pilchard123]

I think this is finished, but would need checking.

If P is above any line coming from the uppermost point of the triangle, it is outside of the face. Likewise, if it is below a line from the lowest point, it is outside. If it is neither of these things, it MAY be in the face.
If P is either above or below BOTH lines coming from the leftmost point, it is outside. If P is above or below both lines from the rightmost point, it is outside. Otherwise, if MAY be in the face.

If both these say that the point MAY be in the face, it IS in the face. However, if there are horizontal or vertical lines in the triangle, the following checks must be performed. In the case where there is only either a horizontal or only a vertical line, the other check may be ommited.

If there is a horizontal line AB and point O, then if O is above AB, P is outside if P is below AB.
If O is below AB, then P is out when above AB. Otherwise, it MAY be in the face.

If there is a vertical line AB in the triangle, and the remaining point O is to the left of it, P will be outside the triangle if P is to the right of the line.
If O is to the right of AB, then P is ouside if it is left of AB. Otherwise, it MAY be in the face.

[annikk.exe]

What is point O?  What does that represent?


There is a problem with this approach if (Px - Qx) = 0.  Then we'd get a divide by zero problem.


Also, this approach will work for triangles only, I think?  Ultimately it needs to be extendable to n-sided 2D polygons.

[annikk.exe]

Sorry by the way, I'm only bringing more questions and problems to the table rather than solutions... :p  I very much appreciate having your input to the discussion, it helps a lot.

[Pilchard123]

Point O is the point NOT in either a horizontal or vertical line in a triangle. Im,agine a triangle with points at A(0,0)  B(0, 10) and C(5, 5). The line AB is vertical, and could cause problems with determining the leftmost point, as both A and B are at the same X coordinate. C is the same as O in my previous post. Am I making sense?

Also, I dealt with (Px - Qx) = 0 in this post. It's right at the end.

SPECIAL CASE: If (Px - Qx) is equal to zero, then the line is vertical, and calculating the gradient will result in (Py - Qy)/0. Not good. In this case, simply check what the X value of the point is in relation to the line and that will tell you which side of the line it is on. For horizontal lines (Py - Qy) = 0, there is not such error, and the long method can be used.

As for n-sided polygons, I haven't done them because I thought you were going to just use triangles. To be honest, triangles would be easier to work with as they don't deform. Why do you think most graphics/modeling stuff uses them? To determine whether a point is in an n-sided polygon, divide the polygon into triangles and check if it is any of them. The smallest number of triangles an n-gon can be divided into is n-2, and this is acheived by joining points as follows.

V0 - V2
V0 - V3
V0 - V4
...
...
...
V0 - V(n-1)

I'm sorry for effectively saying "just do it my way", but I don't know any other way to do this.

[annikk.exe]

No, that's ok.  Splitting larger polygons into triangles might be the way to go.

So for polygons, consider this:





How do we split that into triangles?

Also, if we draw a triangle between E, F, and A, we could say that P lies inside that triangle.  However, it still doesn't lie inside the polygon.  What to do in this eventuality?  Moreover, how do we detect this situation has occurred?  Measure the angle between AF and EF?

[Pilchard123]

Thow a hissy fit because that's not a convex shape.

Not sure really.

You could check every time you create a polygon whether each point would be inside the shape formed by the other points, and if it does, join that point to one that is at a position (n +- 2) from it to form two separate polygons and continue from there. However, this could be very computationaly expensive, so making many, simple shapes would be cheaper. That's actually another reason triangles are used (I think). They MUST be convex.

[annikk.exe]

An engine based purely on triangles is a possibility.
Hmm, I will think about this for a while...

[annikk.exe]

Ok, possible breakthrough incoming.
Take a look at this!! http://alienryderflex.com/polygon/

Apparently the thing I've drawn is called a "complex polygon" because it has concave components.
Turns out there IS a method of determining whether the point lies inside the polygon or not.  :>

[annikk.exe]

Right, what we do is we draw a horizontal line through P.

Then, we count how many times it crosses an edge.  We also count when we hit P.

[annikk.exe]

Consider these other diagrams for further evidence that this approach works:




The point has an Odd number, therefore it must be outside the n-sided polygon.



The point has an Even number, therefore it must be inside the n-sided polygon.



Can anyone think of a 2D shape composed only of straight lines for which this approach will not work?

[Pilchard123]

When it grases the corner of two intersecting lines. But then, I've read the page you linked and know that that's okay because of how it works in code. I think this one would be better than mine as it will allow for holes in the middle of the polygon, where mine wouldn't.

Also, 3 is odd.

[annikk.exe]

Thusly armed, I know that the only information required to declare a face should be the edges of which it is composed.

So a face is composed of at least 3 edges.
An edge is composed of exactly 2 vertices.
Vertices have coordinates.


With this structure clear, I will proceed to declare a face as a Matrix Column, with the row entries containing the ID's of the edges involved.

Code: [Select]

face = {}
for i = 0,numberoffaces do
face[i] = {}
end
Right, time to square this up with the rest of the plan..