-1

I am looking for the best (efficient algorithm for calculating the area of 2D polygon (especially for triangle given three points). I search on the web and I found the following link, but still I'm not sure that they are efficient in terms of memory cost or not (since my mesh is huge). I am wondering if there is any tricks in c++ (I'm newbie in c++) which could be applied on them:

here are the links:

(stackoverflow) How to determine if a point is in a 2D triangle?

http://www.softwareandfinance.com/Visual_CPP/Triangle_Area_Perimeter.html

It's worth to mention that the final target is to find out if a point is inside (NOT on the border) the polygon.

thanks for any help.

Community
  • 1
  • 1
user2090491
  • 568
  • 2
  • 5
  • 15
  • For triangles, have you tries [Heron's formula](http://en.wikipedia.org/wiki/Heron%27s_formula)? – Some programmer dude Aug 26 '13 at 08:42
  • How would you use the area to check if the point is not on the border? – Karthik T Aug 26 '13 at 08:42
  • @ Karthik, I mean that I am looking for an algorithm that only return true, if the point is completely inside the triangle not outside or on the edges. – user2090491 Aug 26 '13 at 08:45
  • 2
    If you just want to find out if a point is inside a polygon, then you don't really need to calculate the area of the polygons. There are other algorithms for that (even though I don't know them personally). – Some programmer dude Aug 26 '13 at 08:48
  • @ Joachim, thanks I know there are many mathematical ways to calculate the area, but since my mesh is quite big, I need something which is also efficient when It comes to programming. – user2090491 Aug 26 '13 at 08:48
  • 1
    @user2090491: You do not need to compute the area of a polygon to find out whether a point is completely inside. In fact, I don't even have a clue how that could help you in any way. – arne Aug 26 '13 at 08:50
  • thanks guys, I know there should be some algorithms to do so; and that 's the reason that I posted this question... – user2090491 Aug 26 '13 at 08:56
  • @user2090491 Make a [special case for the triangle](http://mathworld.wolfram.com/TriangleInterior.html) and read [the Wikipedia page "Point in polygon"](http://en.wikipedia.org/wiki/Point_in_polygon) for a general algorithm. – Carsten Aug 26 '13 at 09:00
  • 1
    What on earth is the question here? You keep asking about areas of a polygon, which is given by Heron's formula, but you keep saying it is to solve a pointing-triangle problem, which has nothing to do with the area, which you've been told several times. -1 – user207421 Aug 26 '13 at 10:08
  • sounds like you're implementing an (inefficient but standard) algorithm for delaunay triangulation (or voronoi tesselation) ... – Walter Aug 26 '13 at 10:55
  • @EJP I do not understand why you are so aggressive, I know know know know that I don't need the area to calculate the point in Triangle. BUT as the MSalters answered below the efficient algorithm to do this job needs to calculate area. and ALSO nobody forced you to make a comment. – user2090491 Aug 26 '13 at 15:51

1 Answers1

1

Joachim Pileborg suggested in comments that the area isn't needed, but that misses the point: there's an efficient algorithm which does require an intermediate value, that just so happens to be 2*Area.

However, in this case the problem is actually the input domain: a mesh of triangles. That means almost every vertex borders on two triangles. It's not like "point P lies on the left of edge E, so it's not in triangle T". There are a large set of triangles Ti, some of which lie on the left, some of which lie on the right, and one directly on either side of a given edge.

Given that complexity, you should pre-process the mesh. Partition it in some manageable chunks, e.g. 16x16, and note for each triangle in which chunks it lies. Any point P lies in exactly one chunk, so you need to test perhaps 1% of triangles (a single triangle may lie in multiple chunks, but the average is low).

(You rarely if ever need to do just a single point-to-mesh match, so preprocessing is justified. And pre-calculate the area while you're at it.)

MSalters
  • 173,980
  • 10
  • 155
  • 350