tags:

views:

279

answers:

1
+1  Q: 

constructing the contour of a 2d figure(in particular a triangulation)

Hi,

How would I go about constructing the contour of 2d figure which is formed of only triangles and it can have holes and the external contour can be concave/convex and the holes can also be concave/convex.

From what I'm reading over here it seems that It's exactly the inverse of the triangulation problem. Do you know any articles treating this ?

It seems I'm missing a headstart or some article treating exactly this type of problem.

Are octrees/quadtrees relevant to this ?

+4  A: 

I guess that you have data in the form of sets of three points, which constitute a "filled" triangle, that these triangles are adjoined along edges, and that all vertices that will be corners of the complete shape are also vertices of all the triangles that touch this point. You would then just have to find all edges that are not doubled, i.e. do not belong to two adjoined triangles.

Svante  2009-01-25 17:45:07
ok,and we're left with a set of points.connecting them to find out the result of the problem is nontrivial,or is it ?
xxxxxxx  2009-02-24 16:35:27
I am not sure if I understand you, spx2, but after eliminating all doubled edges, you are left with the ones that constitute the contour.
Svante  2009-02-24 17:02:36
@Svante, I think he wants to know how to get the points of the contour in order instead of start-end pairs. Also, consider inputs which may result in multiple contours?
Vulcan Eager  2010-04-20 05:41:31

related questions

How do I find the Excel column name that corresponds to a given integer?
Calculating a cutting list with the least amount of off cut waste.
Red-Black Trees
How to maintain a recursive invariant in a MySQL database?
RFC calculation in Java need help with algorithm
Best word wrap algorithm?
How do you separate game logic from display?
Most effective way for float and double comparison
Choosing a multiplier for a (string) hash function
Optimizing a search algorithm in C
Find the best combination from a given set of multiple sets
What "already invented" algorithm did you invent?
Designing a Calendar system like Google Calendar
How to overload std::swap()
Looking for algorithm that reverses the sprintf() function output
Merge Sort a Linked List
Puzzle: Find largest rectangle (maximal rectangle problem)
graph serialization
Peak detection of measured signal
Big O, how do you calculate/approximate it?
What problems can be solved, or tackled more easily, using graphs and trees?
Followup: "Sorting" colors by distinctiveness
Efficiently get sorted sums of a sorted list
Function for creating color wheels
Fastest way to get value of pi