Okay, I'm stumped. I've been working on an algorithm to make triangles to compose a complete polygon(object). First, i read data from a file and make a list of points. Points contain x,y coordinates. Then, i send the list of points to be parsed into a list of lines. Lines contain pointA, pointB and an equation Ax+By = C The values for A,B,C are stored as doubles. Then, i send the list of lines to be tested. If none of the lines intersect each other, it's a valid list. Then I try to make triangles from the list of lines. My algorithm, if it can call it that, tries to make new lines that don't intersect any of the old lines. I know I've reached the end when the number of total lines equals the (number of lines at beginning*2-3) There are several possible problems but I bring only one up right now. The problem occurs when the algorithm tries to add lines outside of the shape defined by the initial group of lines. It's not suppose to do that. For example: these points -1.0,-1.0; 0.0,0.0; -1.0,1.0; 1.0,1.0; 1.0,-1.0; create these lines -1.0,-1.0->0.0,0.0 0.0,0.0->-1.0,1.0 -1.0,1.0->1.0,1.0 1.0,1.0->1.0,-1.0 1.0,-1.0->-1.0,-1.0 If you would draw it, it would look like backwards K. __ \ | /_| When i send it through the algorithm it creates the following line: -1.0,-1.0->-1.0,1.0 This line is actually outside the original set of lines. It should make the following lines. 0.0,0.0->1.0,1.0 0.0,0.0->1.0,-1.0 Any suggestions on a way to fix this or on an algorithm that could figure this out.

Hi,

if I understand you correctly, you are trying to do a triangulation of an arbitrary polygon defined by it's vertices in a given order (seems to be CW).

If so, you might want to look at these links for info:
wikipedia article on polygon triangulation
an optimal algorithm in greater detail

Cheers!

Can anyone explain those posts in english.
Or can someone give me a step by step.
I can work on the code.

Maybe this will help to understand the algorithm. It has a step-by-step description of an algorithm that runs in O(nlogn) time.

Okay, I think that I'm starting to understand, but how do I prove the a point is inside a triangle. It's been a while since I took a math class.

edit:
Well, I suppose of the the new segment intersects one of the original segments.

[Edited by - TruckMack33 on December 9, 2008 6:16:23 PM]

Remember, Google is your friend: point inside triangle
However, that test isn't necessary for implementing the algorithm, iirc.