| --- Log opened Sun Aug 15 00:00:35 2010 |
| 00:19 | | ToxicFrog [ToxicFrog@ServerAdministrator.Nightstar.Net] has quit [[NS] Quit: Reboot for new kernel.] |
| 00:22 | | SmithKurosaki [Smith@Nightstar-cc72cefe.dsl.teksavvy.com] has quit [Client closed the connection] |
| 00:32 | | SmithKurosaki [Smith@Nightstar-cc72cefe.dsl.teksavvy.com] has joined #code |
| 00:48 | | celticminstrel [celticminstre@Nightstar-f8b608eb.cable.rogers.com] has joined #code |
| 01:02 | | ToxicFrog [ToxicFrog@ServerAdministrator.Nightstar.Net] has joined #code |
| 01:02 | | mode/#code [+o ToxicFrog] by Reiver |
| 01:37 | | AnnoDomini [annodomini@Nightstar-ace84000.adsl.tpnet.pl] has quit [Ping timeout: 121 seconds] |
| 01:39 | | AnnoDomini [annodomini@Nightstar-eb14b6b6.adsl.tpnet.pl] has joined #code |
| 01:39 | | mode/#code [+o AnnoDomini] by Reiver |
| 01:51 | <@Vornicus> | Ok. Problem restated: given a connected, planar graph and an additional node not on any of the edges, determine what nodes are "visible" from the additional node. |
| 01:51 | <@Derakon> | Right. |
| 01:51 | <@Derakon> | And we'd gotten as far as defining how to determine which edges in the graph were on the outside. |
| 01:54 | <@Vornicus> | Solution so far: draw line from target node to closest node; select the first edge that you arrive at by going clockwise around the closest node starting at that line. Follow that edge to the next node, go around that one clockwise starting at the edge you follow. Stop when... you cross an edge a second time, going in the same direction. |
| 01:56 | <@Vornicus> | Cull edges, now, that go left-to-right as we see them from the target node. |
| 01:56 | <@Derakon> | A moment. |
| 01:56 | <@Derakon> | edges = dict([(hull[i], hull[(i + 1) % 3]) for i in xrange(3)]) |
| 01:56 | <@Derakon> | That line amuses me. |
| 01:57 | <@Vornicus> | That line makes a directed graph. |
| 01:57 | <@Derakon> | Yes. |
| 01:58 | <@Derakon> | It's not quite sufficient for my needs. |
| 01:59 | <@Vornicus> | edges = dict([(hull[i], (hull[(i + 1) % 3], hull[(i - 1) % 3])) for i in xrange(3)]) |
| 02:00 | <@Derakon> | Yeah, but that was sufficiently unreadable that I went to a for loop. |
| 02:01 | <@Derakon> | This "walk around the exterior" thing is pretty annoying. Do you think it'd be much harder to just maintain a list of the nodes on the outside of the hull, and keep it up-to-date when I add edges? |
| 02:02 | <@Vornicus> | It would require the same sort of thing. |
| 02:02 | <@Derakon> | Bah. |
| 02:02 | <@Vornicus> | Also, remember that "exterior" is a relative thing. This method works even if the node is technically /interior/ |
| 02:03 | <@Derakon> | Won't ever be a problem for this algorithm though. |
| 02:03 | | celticminstrel [celticminstre@Nightstar-f8b608eb.cable.rogers.com] has left #code [] |
| 02:05 | | * Derakon tries to figure out a clean way to write "sort by clockwise distance from this value". |
| 02:07 | <@Derakon> | Here's what I have currently: http://paste.ubuntu.com/478160/ |
| 02:07 | <@Vornicus> | atan2 of the difference, subtract the target, modulus, sort, skip the first unless it's the only one cuz it backtracks. |
| 02:07 | <@Derakon> | That's just constructing the convex hull. |
| 02:08 | <@Derakon> | But the for loop in 14-20 seems like it could be shortened to a single sort statement, much like lines 3-4. |
| 02:08 | <@Vornicus> | This isn't the "convex" hull - it's the hull. |
| 02:09 | <@Vornicus> | (and a lot of the shit in this algorithm is to handle the non-convex case.) |
| 02:09 | <@Derakon> | Because of how the algorithm works it should always be convex, yes? |
| 02:09 | <@Vornicus> | No. |
| 02:10 | <@Vornicus> | Imagine a graph built in approximately a c shape. |
| 02:10 | <@Derakon> | And...? |
| 02:11 | <@Derakon> | We start with a convex hull -- a triangle. |
| 02:11 | <@Vornicus> | huh? |
| 02:11 | <@Derakon> | Every time we add a new node, we also add edges with it. |
| 02:11 | <@Derakon> | The edges we add should ensure that the graph is still convex. |
| 02:11 | <@Vornicus> | /all/ the edges? |
| 02:11 | <@Derakon> | How do you mean, all the edges? |
| 02:11 | <@Vornicus> | Do you add every possible edge that keeps the graph planar. |
| 02:12 | <@Derakon> | You add the edges that can be added between the new node and the existing nodes, that can be added without rendering the graph nonplanar. |
| 02:13 | <@Derakon> | The rough description of the algorithm is here: http://www.s-hull.org/ |
| 02:13 | <@Vornicus> | If not, then we have to continue. If you know, absolutely, that the graph will be convex? THen you can skip everything after "cull edges that go left-to-right and then any nodes that don't appear there" |
| 02:13 | <@Derakon> | I think I'd better read the GPL'd code before I continue too much further... |
| 02:14 | <@Vornicus> | And, actually, even then, there's a step missing: you cull edges that appear /before/ the repeated edge. |
| 02:15 | <@Vornicus> | (because you accidentally ended up picking an occluded starting node, there is at least one edge that is on the interior. |
| 02:15 | <@Derakon> | How could the node that is closest to the outside node be occluded? |
| 02:15 | <@Derakon> | ...nevermind. |
| 02:15 | <@Vornicus> | Der: that is closest /to the target node/ |
| 02:15 | <@Derakon> | target node <=> outside node. |
| 02:16 | <@Vornicus> | consider target a <1,0>, then a triangle of <0,-1>, <0,1>, and <-0.2,0> will have the closest node being the one on the far side. |
| 02:16 | <@Derakon> | Right, hence why I said nevermind. |
| 02:17 | <@Derakon> | Though it occurs to me that in that case, you would not have <-.2, 0> in your starting hull. |
| 02:17 | <@Vornicus> | No? |
| 02:17 | <@Derakon> | The circumcircle it makes with the points on the Y axis is bigger than that made by those two points and <1, 0>. |
| 02:17 | <@Vornicus> | True. |
| 02:17 | <@Derakon> | Unless of course <-.2, 0> was the randomly-chosen starting point. |
| 02:18 | <@Derakon> | Even then you might end up with <-.2, 0>, <0, -1>, and <1, 0>. |
| 02:18 | <@Derakon> | Not certain though. |
| 02:19 | | * Derakon eyes the S-hull code, winces at the variable names. |
| 02:19 | <@Derakon> | Is it really necessary to have utterly undocumented member fields 'r' and 'c'? |
| 02:22 | <@Vornicus> | Always. |
| 02:23 | <@Vornicus> | I put them in every class definition, ever. |
| 02:23 | | * Derakon has Vorn shot~ |
| 02:23 | <@Vornicus> | But what're their types? They're probably radius and center. |
| 02:23 | <@Derakon> | Floats. |
| 02:24 | <@Derakon> | The comment for the entire thing is "point structure for s_hull only. has to keep track of triangle ids as hull evolves." |
| 02:24 | <@Derakon> | This was clearly written by a mathematician. :( |
| 02:25 | <@Derakon> | Okay, determination if an edge is left-to-right. I should be able to do this with a handedness check. |
| 02:25 | <@Derakon> | E.g. external node A, interior nodes X and Y. |
| 02:25 | <@Derakon> | If angle A-X-Y is left-handed, then cull it. |
| 02:30 | <@Derakon> | for a, b in [(n, hullNodes[(i + 1) % len(hullNodes)]) for i, n in enumerate(hullNodes)]: |
| 02:36 | | * Vornicus actually gets the closed form right on circumcircle. This isn't a horrible matrix solve and quadratic formula, either. Idunno /what/ the mathworld article was smoking. |
| 02:39 | <@Derakon> | Nnnnnnot quite: http://derakon.dyndns.org/~chriswei/temp2/nonplanar.png |
| 02:39 | <@Derakon> | (On the plus side, my "draw edges" function worked on the first try~) |
| 02:39 | <@Vornicus> | Picked the wrong edge, looks like. |
| 02:40 | <@Derakon> | Yeah, my "is edge left-to-right" code is broken, I suspect. |
| 02:44 | <@Derakon> | Another failure: http://derakon.dyndns.org/~chriswei/temp2/nonconvex.png |
| 02:44 | <@Vornicus> | Found /a/ correct edge, but not all of them. |
| 02:44 | <@Derakon> | Right. |
| 02:45 | <@Vornicus> | Remember: you can't stop before going all the way around - you have to go all the way around or you'll miss the ones widdershins of your closest node. |
| 02:46 | <@Derakon> | Ahh, yeah, my loop condition is "while node I am considering is not in nodes I have already checked", which may be off by one. |
| 02:47 | <@Derakon> | ...actually, it looks like I'm only checking two edges for that second node, so my convex hull construction must be flawed. |
| 02:48 | <@Vornicus> | Remember to skip the 0 angle |
| 02:49 | <@Vornicus> | (if you look down all the edges, one of them will be the backtrack edge, which will conveniently come up exactly 0 on your angle subtraction) |
| 02:49 | <@Derakon> | Durrrrr. |
| 02:49 | <@Derakon> | Thanks. |
| 02:50 | <@Vornicus> | (you skip that one. In the full algorithm, you only skip it if it's not the only edge.) |
| 02:54 | <@Derakon> | ...I think I need to back off for a bit. I'm getting a little bleary. |
| 03:13 | <@Derakon> | Okay, my problem now is that I'm not calculating "next closest clockwise neighbor" properly. |
| 03:16 | | PinkFreud [WhyNot@NetworkAdministrator.Nightstar.Net] has joined #code |
| 03:18 | <@Vornicus> | Okay. You are: 1. generating angles from your current node to all neighbors, and also to the previous neighbor, separately? |
| 03:18 | <@Derakon> | Yes. |
| 03:18 | <@Derakon> | But give me a moment, I am trying something that is for the moment broken but may help once I fix it. |
| 03:18 | <@Vornicus> | 2. you are then subtracting the previous neighbor's angless? |
| 03:18 | <@Derakon> | Okay, here. http://paste.ubuntu.com/478182/ |
| 03:19 | <@Derakon> | The thing that broke it even worse was adding lines 16-17. |
| 03:19 | <@Derakon> | (Previously angles were in the range [-pi, pi]) |
| 03:19 | <@Derakon> | Hm, formatting fail. |
| 03:19 | <@Derakon> | http://paste.ubuntu.com/478183/ |
| 03:20 | <@Derakon> | This version connects the first new node to all three nodes in the triangle, hence the brokenness. |
| 03:26 | | * Derakon flips his output images upside-down. "Ahh, much better." |
| 03:26 | <@Derakon> | Now the unit circle is right-side up. ¬.¬ |
| 03:28 | <@Vornicus> | whut |
| 03:28 | <@Derakon> | SDL output puts the origin in the upper-left corner. |
| 03:28 | <@Derakon> | This was screwing with my mind, so I inverted everything. |
| 03:29 | <@Derakon> | (Upside-down means the unit circle goes counterclockwise instead of clockwise) |
| 03:30 | | Bobsentme [aa47fc22@Nightstar-4fab16c5.mibbit.com] has joined #code |
| 03:30 | < Bobsentme> | Anyone here code iPhone / iPad apps? I'm taking a class in the fall, and wondering if I'm setting myself up to fail. |
| 03:32 | <@Derakon> | Sorry, afraid I can't help you. |
| 03:34 | < Bobsentme> | thanks for responding, though. |
| 03:36 | <@Derakon> | Progress! http://derakon.dyndns.org/~chriswei/temp2/aha.png |
| 03:36 | <@Derakon> | Or, as the S-hull paper would say, Porgress! |
| 03:37 | <@Derakon> | But sadly... http://derakon.dyndns.org/~chriswei/temp2/boo.png |
| 03:38 | <@Vornicus> | :( |
| 03:38 | <@Derakon> | (267,447) is the newly-added vertex, of course. |
| 03:38 | <@Vornicus> | Yeah, figured that. |
| 03:38 | <@Derakon> | Looks like before it was added, the hull wasn't actually convex. :\ |
| 03:39 | <@Vornicus> | Because you're not actually adding /all/ of them. |
| 03:39 | <@Derakon> | Oh yeah, when 471,241 was added an edge was skipped. |
| 03:39 | <@Vornicus> | 471,241 should be connecting to 17,240 |
| 03:43 | <@Derakon> | Durrr... |
| 03:43 | <@Derakon> | if angle < 2 * math.pi: |
| 03:43 | <@Derakon> | angle += 2 * math.pi |
| 03:43 | <@Derakon> | (First "2 * math.pi" should be "0") |
| 03:43 | <@Vornicus> | whups |
| 03:43 | <@Derakon> | http://derakon.dyndns.org/~chriswei/temp2/boo2.png |
| 03:43 | <@Derakon> | ¬.¬ |
| 03:44 | <@Vornicus> | Aha! |
| 03:44 | <@Vornicus> | Plau. tjat pme we |
| 03:44 | <@Vornicus> | ' |
| 03:44 | <@Vornicus> | Dammitall |
| 03:44 | | * Derakon pats Vorn. |
| 03:44 | <@Vornicus> | Okay, that one we've covered. |
| 03:44 | <@Derakon> | Yeah, I should be pruning 264,229 out. |
| 03:45 | <@Vornicus> | As you can see: 264,229 is closer to 267,447 than the other two. |
| 03:45 | <@Derakon> | (This is a surprisingly good test case for being the result of seeding the RNG with 1) |
| 03:45 | <@Vornicus> | What you do is you keep going around until it demands you visit one you've already visited... at which point you cull everything that comes /before/ the first occurrence of that. |
| 03:46 | <@Derakon> | Hm. Actually, this is a "walking the wrong way" problem. |
| 03:46 | <@Derakon> | I'm going 264,229 => 17,240 => 471,241. |
| 03:46 | <@Vornicus> | whut |
| 03:46 | <@Derakon> | Yeah. |
| 03:47 | <@Vornicus> | Ah, make sure you're using 264 as your start for the vector to 267,447. |
| 03:47 | <@Vornicus> | (as opposed to the other direction) |
| 03:47 | <@Derakon> | ...that broke the previous test case. |
| 03:48 | < Bobsentme> | If I may ask, what is it you're trying to draw? |
| 03:48 | <@Derakon> | I'm trying to generate the Delaunay triangulation of a graph. |
| 03:48 | <@Derakon> | The images are just visualizations of the data I'm working with. |
| 03:48 | < Bobsentme> | Ah. |
| 03:48 | < Bobsentme> | See, I know that was english, but it was over my head. *wanders off to look it up, don't mind me.* |
| 03:48 | <@Derakon> | Vorn: here's the program. The relevant loop starts at 125. http://paste.ubuntu.com/478190/ |
| 03:49 | <@Derakon> | The Delaunay triangulation is a graph (a collection of edges) that connects a set of nodes (locations in 2D space) such that no edge crosses another edge, every polygon is a triangle, and the angles between each edge are as widely-spaced as possible. |
| 03:58 | < Bobsentme> | So, the problem is the line that runs from 17,240 to 471,241. |
| 03:58 | | * Derakon is going to disappear for a bit. |
| 03:59 | <@Vornicus> | Jeezus. |
| 03:59 | | * Bobsentme apologizes? |
| 04:00 | <@Vornicus> | Der, this code is frightening. |
| 04:00 | < Bobsentme> | Ah. Was afraid i was bringing down the room. |
| 04:01 | | * Bobsentme thought the code a bit fascinating. |
| 04:03 | | Tarinaky [Tarinaky@Nightstar-f349ca6d.plus.com] has joined #code |
| 04:04 | <@Vornicus> | Bobsentme: actually, the 17, 240 line is supposed to be drawn, as far as I can tell -- the code hasn't gotten far enough to delete it at this stage. |
| 04:04 | <@Vornicus> | The incorrect line is the vertical one that crosses that one. |
| 04:08 | | Thaqui [Thaqui@27B34E.D54D49.F53FA1.6A113C] has joined #code |
| 04:13 | < Bobsentme> | Ah |
| 04:15 | < Bobsentme> | And there's no way to tell the code "This many nodes have already connected to node X, so skip". |
| 04:16 | <@Derakon> | Theoretically an arbitrary number of nodes can connect to a given node. |
| 04:16 | <@Derakon> | (I'm back) |
| 04:16 | <@Derakon> | Vorn: well, if you have suggestions for making it cleaner, let me know. |
| 04:40 | <@Derakon> | Okay, problem with my convex walk appears to be as follows: |
| 04:40 | <@Derakon> | Go to 264,229. |
| 04:40 | <@Derakon> | From there, correctly go to 17,240. |
| 04:41 | | cpux [cpux@Nightstar-20a84089.dyn.optonline.net] has quit [Ping timeout: 121 seconds] |
| 04:41 | <@Derakon> | Angle from 17,240 to 264,229 is 6.239. |
| 04:41 | <@Derakon> | Angle from 17,240 to 471,241 is .047. |
| 04:41 | <@Derakon> | I'm reading this as a very small clockwise distance, when it should be instead pretty huge. |
| 04:42 | <@Derakon> | (Er. Angle to 471,241 is .0022; computed angular distance is .047.) |
| 04:48 | <@Vornicus> | For some reason your thing's going counterclockwise. |
| 04:48 | <@Derakon> | I think I've figured out what that problem was, but fixing it broke something else... |
| 04:49 | | * Derakon is back at the step-1 case. Fortunately that one is simple to examine. |
| 04:51 | <@Vornicus> | Cripes. This thing is a pain. |
| 04:52 | <@Derakon> | Weird...I seem to be walking counterclockwise around the hull on step 1 and clockwise on step 2. |
| 05:02 | <@Derakon> | Okay, this is a novel failure mode. http://derakon.dyndns.org/~chriswei/temp2/notriangle.png |
| 05:02 | <@Derakon> | (But: progress!) |
| 05:03 | | * Bobsentme refrains from a "My, what big triangles you have" comment. |
| 05:04 | <@Derakon> | Check the lower-right, and note the shape that 623,70 is on. |
| 05:06 | < Bobsentme> | Is there a way to check what the last node hit was? |
| 05:06 | <@Derakon> | 623,70 is the last node I added to the connected set. |
| 05:07 | < Bobsentme> | Ok, one more newb question: Is that done in one continuous line, going from node to node, or does it calculate by 3 point sets? |
| 05:07 | <@Derakon> | I'm afraid your question is making assumptions which I don't know about, rendering it nonsensical to me. |
| 05:08 | < Bobsentme> | Ok. I'll gladly bow out now, as you're several steps ahead of me anyways. |
| 05:09 | <@Derakon> | This once again appears to be a problem of going around the hull in the wrong direction. Pah. |
| 05:09 | <@Derakon> | Ehh, I'll come back to this later. |
| 05:26 | | cpux [cpux@Nightstar-20a84089.dyn.optonline.net] has joined #code |
| 05:45 | | Rhamphoryncus [rhamph@Nightstar-bbc709c4.abhsia.telus.net] has joined #code |
| 05:47 | < Bobsentme> | For the record, Apple's SDK for the iOS is 2.49 gb. (and took 30 minutes to download from the Datacenter here at work!) |
| 05:53 | | Alek [omegaboot@Nightstar-c5f3565b.il.comcast.net] has quit [Ping timeout: 121 seconds] |
| 05:59 | | Alek [omegaboot@Nightstar-c5f3565b.il.comcast.net] has joined #code |
| 06:06 | | Bobsentme [aa47fc22@Nightstar-4fab16c5.mibbit.com] has quit [[NS] Quit: http://www.mibbit.com ajax IRC Client] |
| 06:28 | | * Derakon makes it one more level into the triangulation before breaking. |
| 06:28 | <@Derakon> | Two more to go! |
| 06:33 | <@Derakon> | ...oh, wait, no. This is broken rather earlier. Damnation. |
| 06:48 | <@Derakon> | Okay, Vorn, I've come to the conclusion that the "walk the convex hull" system is flawed. |
| 06:48 | <@Derakon> | Take a look at this: http://derakon.dyndns.org/~chriswei/temp2/angles.png |
| 06:49 | <@Derakon> | We start at 267,447. |
| 06:49 | <@Derakon> | We go down to 264,229, and then take as hard a left turn as we can. That takes us to 471,241. |
| 06:49 | <@Derakon> | Then we take as hard a left turn as we can from there. That takes us to 17,240. |
| 06:49 | <@Derakon> | Then we take as hard a left turn as we can from there. That takes us to 264,229. |
| 06:49 | <@Derakon> | You see the problem? |
| 06:51 | | Bobsentme [aa47fc22@Nightstar-4fab16c5.mibbit.com] has joined #code |
| 06:53 | <@Derakon> | Hm, this should be solvable if we find the closest node that we can connect to without rendering the graph nonplanar. |
| 06:55 | <@Vornicus> | Um. |
| 06:55 | <@Vornicus> | Hardest left turn from 17, 240 is 89, 87 |
| 06:56 | <@Derakon> | No, it isn't. |
| 06:56 | <@Vornicus> | Yes it is. |
| 06:56 | <@Derakon> | Coming in from 471,241 you make a sharp U-turn. |
| 06:56 | <@Vornicus> | Point at 471, 241 from 17, 240. |
| 06:56 | <@Derakon> | That's about as hard a left turn as you can get. |
| 06:56 | <@Vornicus> | then turn your finger ccw till you hit something. |
| 06:56 | <@Derakon> | I'm reading the angles the other way. |
| 06:56 | <@Derakon> | But functionally you get the same problem at 471,241 then. |
| 06:57 | <@Vornicus> | Okay, then if you're reading it /that/ way, then you shouldn't have gone to 471 in the first place. |
| 06:58 | <@Derakon> | It's the hardest left turn available that's clockwise from our incoming angle. |
| 06:58 | <@Derakon> | Anyway, check it: http://derakon.dyndns.org/~chriswei/temp2/booya.png |
| 06:59 | <@Derakon> | That's with the "pick the closest node I can attach to without intersecting existing edges" logic added. |
| 06:59 | <@Vornicus> | This may not give you a triangulation that can be delauntay'd |
| 07:00 | <@Derakon> | I went through it step-by-step and didn't see any mistakes. Granted this is a pretty simple graph. |
| 07:02 | | * Derakon tries a few more simple test cases, gets them all right. |
| 07:02 | <@Vornicus> | arg, wtf |
| 07:04 | <@Derakon> | This is looking pretty accurate to me so far. |
| 07:04 | <@Vornicus> | oh, fiddlesticks. I see now. |
| 07:04 | <@Vornicus> | By crossing that line, it makes the algorithm assume it's inside that thin triangle. |
| 07:05 | <@Derakon> | Right. |
| 07:05 | <@Derakon> | http://derakon.dyndns.org/~chriswei/temp2/booya2.png |
| 07:05 | <@Derakon> | That looks pretty cool. |
| 07:05 | <@Vornicus> | So there must instead be a better way to ... duh. If we're always outside, then 'most extreme angle' works |
| 07:06 | <@Derakon> | Now I just have to figure out the edge flipping logic! |
| 07:07 | <@Vornicus> | good luck. |
| 07:07 | | * Vornicus fights with his algorithm to see if he can figure out one that works inside, too. |
| 07:10 | <@Vornicus> | I love how that's just... glossed over on the page. |
| 07:10 | <@Derakon> | Yeah. |
| 07:11 | <@Derakon> | I mean, I get what they mean -- take two triangles that form a quadragon, and replace the interior edge with the only other possible interior edge -- but when to do it is completely skipped. |
| 07:12 | <@Derakon> | Also, if you think my code is messy...the reference implementation is 2576 lines of C. |
| 07:12 | <@Derakon> | And it looks like something I'd see at work. |
| 07:12 | <@Vornicus> | ;_; |
| 07:13 | <@Derakon> | Ahh, Wikipedia has a definition of a Delaunay triangle. |
| 07:13 | <@Derakon> | If the sum of the angles that are not on the interior edge is <= 180° then the triangle is Delaunay. |
| 07:15 | <@Vornicus> | Then the pair of triangles? |
| 07:16 | <@Derakon> | Er. Yes. |
| 07:16 | <@Derakon> | http://en.wikipedia.org/wiki/Delaunay_triangulation#Visual_Delaunay_definition:_ Flipping |
| 07:22 | <@Derakon> | firstAngle = math.acos(targetNode.sub(firstNeighbor).normalize().dot(firstNeighbor.sub(source Node).normalize())) |
| 07:22 | <@Vornicus> | wHEEEEE |
| 07:27 | <@Derakon> | ...one problem: I didn't write a dot-product function for Vector2D. O_o |
| 07:28 | <@Vornicus> | oh noes. |
| 07:34 | <@Derakon> | Well, my first attempt was a clear failure. |
| 07:34 | <@Derakon> | Flipping is not supposed to introduce edge intersections. ¬.¬ |
| 07:34 | <@Vornicus> | Slightly. |
| 07:39 | <@Derakon> | Okay, my angle calculation is broken. |
| 07:39 | <@Derakon> | I was going by http://www.euclideanspace.com/maths/algebra/vectors/angleBetween/index.htm |
| 07:43 | <@Derakon> | Eh, it's too late to keep working on this. |
| 07:46 | | Derakon is now known as Derakon[AFK] |
| 09:35 | | You're now known as TheWatcher |
| 09:45 | | Tarinaky [Tarinaky@Nightstar-f349ca6d.plus.com] has quit [Client closed the connection] |
| 09:50 | | McMartin [mcmartin@Nightstar-dd07698f.pltn13.sbcglobal.net] has quit [[NS] Quit: Software update] |
| 09:52 | | McMartin [mcmartin@Nightstar-dd07698f.pltn13.sbcglobal.net] has joined #code |
| 09:52 | | mode/#code [+o McMartin] by Reiver |
| 10:19 | <@Vornicus> | u = (a - b); v = (a - c); s = (a + b) / 2; t = (a + c) / 2; n_y = (u_x(v.t) - v_x(u.s)) / (u*v); n_x = (v_y(u.s) - u_y(v.t)) / (u*v) |
| 10:20 | <@Vornicus> | I have a stupid question. Why the hell does Mathworld give the equivalent of this in the form of a completely ridiculous trio of matrix determinantts. |
| 10:20 | | * Bobsentme has no answer. |
| 10:22 | <@TheWatcher> | To be as obtuse as possible. |
| 10:28 | <@Vornicus> | Actually I like Wikipedia's version even better, it's really pretty. |
| 10:30 | | * TheWatcher bleeghs, fiddles with concurrent cache access issues |
| 10:47 | <@Vornicus> | ...and I saw going to say, "harder to read" but then I saw how it transforms. They win. |
| 11:01 | | Rhamphoryncus [rhamph@Nightstar-bbc709c4.abhsia.telus.net] has quit [Client exited] |
| 11:04 | | Bobsentme [aa47fc22@Nightstar-4fab16c5.mibbit.com] has quit [[NS] Quit: http://www.mibbit.com ajax IRC Client] |
| 11:15 | <@Vornicus> | (theirs is: u = b - a; v = c - a; n_x = (v_y (u.u) - u_y (v.v)) / (2 u*v); n_y = (u_x (v.v) - v_x (u.u)) / (2 u*v) |
| 11:33 | | Tarinaky [Tarinaky@Nightstar-f349ca6d.plus.com] has joined #code |
| 11:52 | | Thaqui [Thaqui@27B34E.D54D49.F53FA1.6A113C] has quit [Connection closed] |
| 12:05 | | RichardBarrell [mycatverbs@Nightstar-689c9c54.cable.virginmedia.com] has joined #code |
| 12:33 | | cpux [cpux@Nightstar-20a84089.dyn.optonline.net] has quit [Client closed the connection] |
| 13:15 | | RichardBarrell [mycatverbs@Nightstar-689c9c54.cable.virginmedia.com] has quit [Ping timeout: 121 seconds] |
| 13:20 | | Vornicus [vorn@Nightstar-66efdaa0.ct.comcast.net] has quit [Ping timeout: 121 seconds] |
| 13:43 | | celticminstrel [celticminstre@Nightstar-f8b608eb.cable.rogers.com] has joined #code |
| 14:31 | | ToxicFrog [ToxicFrog@ServerAdministrator.Nightstar.Net] has quit [[NS] Quit: Dist-upgrade to OpenSUSE 11.2 in progress!] |
| 14:34 | | SmithKurosaki [Smith@Nightstar-cc72cefe.dsl.teksavvy.com] has quit [Client closed the connection] |
| 14:37 | | ToxicFrog [ToxicFrog@ServerAdministrator.Nightstar.Net] has joined #code |
| 14:37 | | mode/#code [+o ToxicFrog] by Reiver |
| 14:55 | | You're now known as TheWatcher[afk] |
| 15:49 | | Serah [Z@Nightstar-41ddd748.0.fullrate.dk] has quit [Ping timeout: 121 seconds] |
| 16:08 | | You're now known as TheWatcher |
| 16:12 | | cpux [cpux@Nightstar-20a84089.dyn.optonline.net] has joined #code |
| 18:12 | | cpux_ [cpux@Nightstar-20a84089.dyn.optonline.net] has joined #code |
| 18:13 | | cpux [cpux@Nightstar-20a84089.dyn.optonline.net] has quit [Ping timeout: 121 seconds] |
| 18:13 | | cpux_ is now known as cpux |
| 18:58 | | cpux_ [cpux@Nightstar-20a84089.dyn.optonline.net] has joined #code |
| 19:00 | | Thaqui [Thaqui@27B34E.D54D49.F53FA1.6A113C] has joined #code |
| 19:01 | | cpux [cpux@Nightstar-20a84089.dyn.optonline.net] has quit [Ping timeout: 121 seconds] |
| 19:01 | | cpux_ is now known as cpux |
| 19:27 | | Vornicus [vorn@Nightstar-66efdaa0.ct.comcast.net] has joined #code |
| 19:27 | | mode/#code [+o Vornicus] by Reiver |
| 19:38 | | * Derakon[AFK] runs into the old "iterating over a datastructure as you change it" problem. |
| 19:38 | | Derakon[AFK] is now known as Derakon |
| 19:38 | <@Derakon> | Specifically, the edge-flipping logic for the Delaunay triangulation. |
| 19:39 | <@Derakon> | My current logic is "for each triangle: for each other triangle: if triangles share an edge: try to flip them." |
| 19:39 | <@Derakon> | But after doing one flip, it's no longer valid to iterate over the triangles. |
| 19:45 | <@Derakon> | So I'm wondering if maybe I should be iterating over every edge instead? |
| 19:45 | <@Vornicus> | Yes, but instead of "iterating over every edge" just put edges in a queue. |
| 19:45 | <@Vornicus> | Pull an edge. If you flip it, push its four neighbors. |
| 19:46 | <@Derakon> | Are we assuming that we start with all interior edges in the queue? |
| 19:46 | <@Vornicus> | Yes. |
| 19:48 | <@Vornicus> | (to determine whether one's an interior edge, just use the convex hull.) |
| 19:49 | <@Derakon> | (Yeah) |
| 19:52 | <@Vornicus> | To find your triangle pairs, just find the two nodes that the edge-end nodes connect to. |
| 19:52 | <@Derakon> | There's a problem with that. |
| 19:52 | <@Vornicus> | ?? |
| 19:52 | <@Derakon> | The two nodes need to be on opposite sides of the edge. |
| 19:53 | <@Derakon> | E.g. consider the triangle (-1, 0) (1, 0) (0, 1). |
| 19:53 | <@Derakon> | You could add a node at (0, 2) and add two more triangles. |
| 19:53 | <@Vornicus> | True! |
| 19:53 | <@Derakon> | And then if you're looking at the edge (-1, 0) (1, 0) you might think that the nodes (0, 1) (0, 2) are valid for flipping. |
| 19:54 | <@Vornicus> | So, closest node. |
| 19:54 | <@Vornicus> | On each side. |
| 19:54 | <@Derakon> | I have a triangle-finder that seems to work, and so if I find two triangles that share an edge, I know they're a valid flip target. |
| 19:54 | <@Derakon> | But then those triangles get invalidated during iteration. |
| 20:01 | <@Derakon> | Mightn't it be easier to just start on the edge and walk clockwise and counterclockwise? |
| 20:04 | <@Derakon> | Ergh, not sure I'm getting this... |
| 20:04 | <@Derakon> | Okay, so. |
| 20:04 | <@Derakon> | Start with a queue of all interior edges in the graph. |
| 20:04 | <@Derakon> | Pop an edge off. |
| 20:04 | <@Derakon> | Get the two triangles that share that edge. |
| 20:04 | <@Derakon> | If the two triangles are Delaunay, then do nothing. |
| 20:05 | <@Derakon> | Otherwise, find that edge in the overall graph, remove it. |
| 20:05 | <@Derakon> | Replace it by its counterpart. |
| 20:05 | <@Derakon> | Push the other four edges of the two triangles into the queue. |
| 20:05 | <@Derakon> | Is that about it? |
| 20:05 | | celticminstrel [celticminstre@Nightstar-f8b608eb.cable.rogers.com] has left #code [] |
| 20:06 | <@Vornicus> | Yes. |
| 20:06 | <@Derakon> | ...geeze, this is 350 lines long and horribly messy. |
| 20:08 | | cpux_ [cpux@Nightstar-20a84089.dyn.optonline.net] has joined #code |
| 20:11 | | cpux [cpux@Nightstar-20a84089.dyn.optonline.net] has quit [Ping timeout: 121 seconds] |
| 20:11 | | cpux_ is now known as cpux |
| 20:12 | <@Vornicus> | No surprise, you've been hacking it together as you go. |
| 20:36 | | * Derakon aborts an attempt to co-opt his hull walking routine to get the adjacent triangles. |
| 20:38 | | cpux_ [cpux@Nightstar-20a84089.dyn.optonline.net] has joined #code |
| 20:38 | | cpux [cpux@Nightstar-20a84089.dyn.optonline.net] has quit [Ping timeout: 121 seconds] |
| 20:38 | | cpux_ is now known as cpux |
| 20:44 | < Tarinaky> | http://twitter.com/phil_nash/status/21159419598 |
| 20:52 | | cpux [cpux@Nightstar-20a84089.dyn.optonline.net] has quit [Ping timeout: 121 seconds] |
| 21:10 | | cpux [cpux@Nightstar-20a84089.dyn.optonline.net] has joined #code |
| 21:12 | | Tarinaky [Tarinaky@Nightstar-f349ca6d.plus.com] has quit [Client closed the connection] |
| 21:24 | | Stalker [Z@3A600C.A966FF.5BF32D.8E7ABA] has joined #code |
| 21:37 | | cpux [cpux@Nightstar-20a84089.dyn.optonline.net] has quit [[NS] Quit: ChatZilla 0.9.86 [Firefox 3.6.8/20100722155716]] |
| 21:38 | | cpux [cpux@Nightstar-20a84089.dyn.optonline.net] has joined #code |
| 22:52 | | Stalker [Z@3A600C.A966FF.5BF32D.8E7ABA] has quit [Ping timeout: 121 seconds] |
| 22:54 | | Thaqui [Thaqui@27B34E.D54D49.F53FA1.6A113C] has quit [Connection closed] |
| 23:17 | | AnnoDomini [annodomini@Nightstar-eb14b6b6.adsl.tpnet.pl] has quit [[NS] Quit: Out of the night and into the fight, it's BIXBY!] |
| 23:46 | | cpux is now known as shade_of_cpux |
| --- Log closed Mon Aug 16 00:00:36 2010 |