I hope this is the right section for this.
Here's what I have, if this isn't sufficient info let me know. I have a basic line struct, made up of two Vector2 coordinates, Start and End.
Here is a visual representation of lines making triangles and then making a rectangle.
http://imageupper.co...354333708244635
What I would like to do is remove the lines that are interior to the outer part of the shape. Now obviously I have all the data making up the lines and it would be trivial to do it manually, but I need a formula that can handle this for me for the sake of time consumption it would take.
To be clear, what I'm considering exterior and interior; if the outward most points were N,S,E,W, I want the lines connecting N to E & W, S to E & W. The two interior triangles making the smaller square, all of that can go.
And yes the end result would be eight Line structs, with two touching lines between N to E and etc.
0
I need to remove these interior lines.
Started by Ghost Clock, Nov 30 2012 10:02 PM
11 replies to this topic
Sponsor:
#2 Crossbones+ - Reputation: 398
Posted 02 December 2012 - 12:19 PM
The best approach I can think of is to use a flood-fill algorithm to determine which lines "touch" exterior space, and then remove everything else. But it really depends on what you consider exterior space. For instance, let's say that there was a small hole in the side of one of the exterior triangles. Would the interior smaller triangles then be considered exterior?
#3 Members - Reputation: 1840
Posted 02 December 2012 - 04:36 PM
The interior lines belong to (exactly) 2 triangles, the exterior lines only belong to a single triangle. That should be enough to start you off.
"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley
#4 Members - Reputation: 625
Posted 02 December 2012 - 04:44 PM
One way to identify the exterior shell of your set of points (so we're assuming there are not any 'holes' that should be considered exterior to the volume).
a) Identify a point on the exterior of the line set.
b) Walk around the exterior of the line set till you get back to start.
This identifies all the lines required to define the exterior; and then ones that you can remove are all those not belonging to the exterior.
For a) you can choose the lexicographically minimal point (a, b) < (c, d) iff a < c || (a == c &amp;&amp; b < d)
For b) you need to be able to; from any given point of the exterior identify the next point of the exterior. This comes in two cases; the initial case where you have 2 exterior lines to choose and you have to pick one of them (for this, abuse that your start point is lexicographically minimal), and in the other case you can make use of the point of the exterior you have just came from to order the outgoing edges.
Presume that we choose, as a result of the first case of b) the point that is clockwise around the exterior (We'll come back to this after).
If you label the previous point 'p' and the current point 'c'; then you can order the outgoing edges based on their relative rotation from the vector (c - p) http://www.zimagez.com/zimage/screenshot-021212-223758.php here, we want to pick vertex v0.
We can do this by computing the perp-dot products of (v[i] - c) with (c - p) normalised by the length of (v[i] - c); and choosing the minimal (or maximal depending on coordinate system); since the perp-dot of two vectors u,v is |u||v|sin(theta). We can also avoid any division if sorting of the outgoing edges uses a comparison function instead of a key.
Back to the first case of b); choosing the second vertex of exterior we can use the same technique, and use the vector (1, 0) instead of (c - p) above. This is valid given that our first vertex was lexicographically minimal since the clockwise direction of the next vertex can in the worst case be in the direction (1, 0) and there cannot exist any vertex of the set that would give us a 'negative' perp-dot since that point would need to have a lower y-coordinate and would have been chosen as the lexicographically minimal one.
^^ this is very similar to gift wrapping algorithm for computing a convex hull and is exactly equivalent if we join every vertex to every other one using this algorithm.
a) Identify a point on the exterior of the line set.
b) Walk around the exterior of the line set till you get back to start.
This identifies all the lines required to define the exterior; and then ones that you can remove are all those not belonging to the exterior.
For a) you can choose the lexicographically minimal point (a, b) < (c, d) iff a < c || (a == c &amp;&amp; b < d)
For b) you need to be able to; from any given point of the exterior identify the next point of the exterior. This comes in two cases; the initial case where you have 2 exterior lines to choose and you have to pick one of them (for this, abuse that your start point is lexicographically minimal), and in the other case you can make use of the point of the exterior you have just came from to order the outgoing edges.
Presume that we choose, as a result of the first case of b) the point that is clockwise around the exterior (We'll come back to this after).
If you label the previous point 'p' and the current point 'c'; then you can order the outgoing edges based on their relative rotation from the vector (c - p) http://www.zimagez.com/zimage/screenshot-021212-223758.php here, we want to pick vertex v0.
We can do this by computing the perp-dot products of (v[i] - c) with (c - p) normalised by the length of (v[i] - c); and choosing the minimal (or maximal depending on coordinate system); since the perp-dot of two vectors u,v is |u||v|sin(theta). We can also avoid any division if sorting of the outgoing edges uses a comparison function instead of a key.
Back to the first case of b); choosing the second vertex of exterior we can use the same technique, and use the vector (1, 0) instead of (c - p) above. This is valid given that our first vertex was lexicographically minimal since the clockwise direction of the next vertex can in the worst case be in the direction (1, 0) and there cannot exist any vertex of the set that would give us a 'negative' perp-dot since that point would need to have a lower y-coordinate and would have been chosen as the lexicographically minimal one.
^^ this is very similar to gift wrapping algorithm for computing a convex hull and is exactly equivalent if we join every vertex to every other one using this algorithm.
Edited by luca-deltodesco, 02 December 2012 - 04:48 PM.
#5 Members - Reputation: 625
Posted 02 December 2012 - 04:51 PM
Paradigm shifter, that only works if the lines always form triangles..
eg: http://www.zimagez.com/zimage/screenshot-021212-225045.php
here, your solution would choose to remove the crossed-out red line. My algorithm would give us the green polygon.
eg: http://www.zimagez.com/zimage/screenshot-021212-225045.php
here, your solution would choose to remove the crossed-out red line. My algorithm would give us the green polygon.
#6 Members - Reputation: 1840
Posted 02 December 2012 - 04:54 PM
Yeah, I am assuming he has a triangulation of the lines rather than arbitrary polygons, or just a list of lines. Triangulation would probably be a good first step though.
"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley
#7 Members - Reputation: 625
Posted 02 December 2012 - 06:24 PM
Your step doesn't really need a triangulation. Eitherway given purely a set of lines you need to determine what the triangles are in the first place; and that same step can be used to simply determine the sub-polygons which would then lead to the same rule of an internal line has more than one sub-polygon using it and the triangulation step is pointless.
Eitherway, I don't see how you could determine those internal sub-polygons any faster than just traversing the exterior directly.
Eitherway, I don't see how you could determine those internal sub-polygons any faster than just traversing the exterior directly.
#8 Members - Reputation: 625
Posted 02 December 2012 - 07:55 PM
For fun, I implemented my solution in Haxe and checked it worked with a somewhat degenerate case as well of having a dangling vertex connected outside the main exterior set
http://pastebin.com/uyu2ZehA
http://pastebin.com/uyu2ZehA
Edited by luca-deltodesco, 02 December 2012 - 08:02 PM.
#9 Members - Reputation: 625
Posted 02 December 2012 - 08:07 PM
Further examples shown with results in red (additional number being number of times in total that vertex appears in output)
http://www.zimagez.com/zimage/screenshot-031212-021000.php
http://www.zimagez.com/zimage/screenshot-031212-021000.php
Edited by luca-deltodesco, 02 December 2012 - 08:10 PM.
#11 Members - Reputation: 130
Posted 03 December 2012 - 07:58 PM
Sorry for the late response, busy weekend.
I thought about that while in bed but wasn't sure what the best way of doing that would be but I think I can work with what you've given me and have it working tonight.
The data is coming to me triangulated and is for multiple purposes, "identifying the exterior lines" for my purposes would be a better way of putting what I wanted to do moreso than "removing these interior lines".
a) Identify a point on the exterior of the line set.
b) Walk around the exterior of the line set till you get back to start.
This identifies all the lines required to define the exterior; and then ones that you can remove are all those not belonging to the exterior.
I thought about that while in bed but wasn't sure what the best way of doing that would be but I think I can work with what you've given me and have it working tonight.
Correct, I should have mentioned this.Yeah, I am assuming he has a triangulation of the lines rather than arbitrary polygons, or just a list of lines.
The data is coming to me triangulated and is for multiple purposes, "identifying the exterior lines" for my purposes would be a better way of putting what I wanted to do moreso than "removing these interior lines".
Edited by Ghost Clock, 03 December 2012 - 07:59 PM.
#12 Members - Reputation: 625
Posted 03 December 2012 - 09:07 PM
Well in that case (Having a triangulation) then you can just use paradigm's solution of removing all lines that are shared between 2 triangles. My solution is for the general case of having a set of points and lines that are connected (Or can be used on disconnected components also with some extension).
